本系列的内容主要翻译自Postgresql官方博客，为了便于理解，对于其中部分涉及到的知识，我在查阅相关资料的基础上做了补充。

原文: Indexes in PostgreSQL — 4(Btree)

系列文章索引

我们已经讨论了PostgreSQL中的索引引擎，访问方法接口和其中的一个访问方法-哈希索引。这一章我们将讨论B树索引，这是最流行和最广泛使用的索引。这篇文章很长，请耐心阅读。

B树

结构

B树索引类型，作为”btree”访问方法的实现，适合那些可以排序的数据。就是说，必须为这些数据类型定义“大于”、“大于等于”、“小于”、“小于等于”、“等于”这些操作符。注意有时候可以对相同的数据进行不同的排序，这让我们回到了操作符族的概念。

B树的索引行被打包在页面里。在叶子节点，这些行包含的数据有索引的键和指向表中行数据的指针。在内部节点中，每一行都包含了索引的子页面和这个子页面的最小值。

B树有几个重要的特征：

  • B树是平衡的，这意味着，每一个叶子节点到跟节点的距离都是相等的。然后，搜索任意的值都要相同的时间。
  • B树是多分支的。每一个页面(通常是8KB)包含数百个TID。因此，B树的深度是非常小的，对于一个非常大的表，深度也就是4到5。
  • 索引中的数据是非递减排序的（在页面内和相邻的页面），相同级别的页面又被一个双向链表连接了起来。因此，我们只需要顺着链表就可以获得一个有序的数据，而不需要每次都返回到根节点。

下面是一个简单的索引一个integer字段的例子

索引最开始的一个页面是metapage，这个页面链接到了根节点。内部的节点位于根节点的下方，叶子节点位于最低一行。叶子节点向下的箭头代表指向表行(TID)的引用。

按相等搜索

我们先来看在树中用”索引字段=表达式”来搜索一个指定值。这里，我们来搜索49

搜索是从根节点开始的，我们需要决定下降到哪个子节点。根据根节点的值是(4,32,64)，我们可以计算出子节点的范围。49大于32小于64，因此我们需要下降到第2个子节点。下一步，同样的过程被递归执行，知道我们到达可以获取到TIDs的叶子节点。

实际上会有很多细节会让这些看起来简单的问题复杂化。例如，索引可以包含非唯一的键值，甚至可以有很多相等的键值，这些相等的键值可以超过一个页面。回到我们的例子，看起来我们应该从内部的49节点下降到这个值引用的叶子节点。但是，从图中可以看出，这个会让我们跳过前一个叶子节点的49。因此，一旦我们发现内部节点有一个精确匹配的值，我们必须从左下降一个位置，然后在底层中从左到右查看索引行来搜索对应的键值。

另一个复杂因素是在搜索过程中，其它进程可能会更改数据：可以重新构建树，可以拆分页面。所有算法都是为了这些能够并发执行而设计的，这些更改不会互相干扰，也尽可能的不使用额外的锁。但是我们这里不展开说这个。

这里简单提一下：正如前面所说的，PostgreSQL的B树内一个叶子节点都有以双向链接来链接两个相邻的页面。同时,B树中的每个页面都记录了这个页面的最大值。还以上面的搜索43为例，假设说当前搜索到了第二层，也就是(32,43,49)这个节点，按照前面所讲述的那样，应该下降到(43，49)这个节点。但是假设在下降的过程中，(32,43,49)节点发生了分裂，分裂成了(32,43,47,49)，对应的子节点也分裂成了(32,42)、(43,46)、(47,48)、(49,62)，这个时候，搜索下降到了(43,46)节点上，这个节点上没有49这个键值。但是由于这个节点上记录了分裂后的最大键值46，因此可以比较要搜索的值和这个页面上的最大值46，因为49比46大，因此就可以知道这个节点发生了分裂，搜索就可以沿着向右的指针去相邻的页面去查找49。

通过不等式搜索

当根据”索引字段<=表达式”或者”索引字段>=表达式”这样的条件进行搜索的时候，我们首先在索引树中根据”索引字段=表达式”来找到对应的表达式的值，然后以相应的的顺序顺着叶子节点遍历到最后。

下图描述了n<=35的过程

“大于”和“小于”搜索的过程和这个差不多，但是会丢弃那个相等的值。

根据范围搜索

当根据范围条件“表达式1 <= 索引字段 <= 表达式2”搜索的时候，我们会先根据条件“索引字段=表达式1”来找到对应的值，然后顺着叶子节点往下走直到满足“索引字段<=表达式2”为止；反之亦然。

下面描述了 23 <= n <= 64的过程

例子

让我们来看一个查询计划的例子吧。和原来一样，我们使用一个demo数据库，这次我们使用aircrafts_data表。它只包含了9行，因此计划器不会使用索引，因为整个表可以放到一页里。但是为了讲明白我们的目的，这张表还是很有趣的。

1
select * from aircrafts_data;
1
2
3
4
5
6
7
8
9
10
11
12
13
 aircraft_code |                           model                            | range 
---------------+------------------------------------------------------------+-------
 773           | {"en": "Boeing 777-300", "ru": "Боинг 777-300"}            | 11100
 763           | {"en": "Boeing 767-300", "ru": "Боинг 767-300"}            |  7900
 SU9           | {"en": "Sukhoi Superjet-100", "ru": "Сухой Суперджет-100"} |  3000
 320           | {"en": "Airbus A320-200", "ru": "Аэробус A320-200"}        |  5700
 321           | {"en": "Airbus A321-200", "ru": "Аэробус A321-200"}        |  5600
 319           | {"en": "Airbus A319-100", "ru": "Аэробус A319-100"}        |  6700
 733           | {"en": "Boeing 737-300", "ru": "Боинг 737-300"}            |  4200
 CN1           | {"en": "Cessna 208 Caravan", "ru": "Сессна 208 Караван"}   |  1200
 CR2           | {"en": "Bombardier CRJ-200", "ru": "Бомбардье CRJ-200"}    |  2700
(9 rows)

1
2
3
create index on aircrafts_data(range);

set enable_seqscan = off;

我下载的示例中，原文中使用的是aircrafts表。但是我下载的例子中，aircrafts是视图不是表。

(或者可以精确的用“create index on aircrafts using btree(range)”，但是B-tree是默认的索引)

根据相等搜索：

1
explain(costs off) select * from aircrafts_data  where range = 3000;
1
2
3
4
5
                         QUERY PLAN                          
-------------------------------------------------------------
 Index Scan using aircrafts_data_range_idx on aircrafts_data
   Index Cond: (range = 3000)
(2 rows)

根据不等式搜索

1
explain(costs off) select * from aircrafts_data where range < 3000;
1
2
3
4
5
                           QUERY PLAN                           
----------------------------------------------------------------
 Index Scan using aircrafts_data_range_idx on aircrafts_data ml
   Index Cond: (range < 3000)
(2 rows)

根据范围搜索

1
explain(costs off) select * from aircrafts_data where range between 3000 and 5000;
1
2
3
4
5
                         QUERY PLAN                          
-------------------------------------------------------------
 Index Scan using aircrafts_data_range_idx on aircrafts_data
   Index Cond: ((range >= 3000) AND (range <= 5000))
(2 rows)

排序

让我们再强调一次，对于任何类型的扫描(index、index-only和位图)，”btree”访问方法都返回有序的数据。这些在前面的图中都能看出来。

因此，如果表中有一个建立在排序条件上的索引，优化器将会考虑两个选项：索引扫描整个表-这个很容易返回排序的数据；顺序扫描整个表，然后对结果进行排序。

排序顺序

在创建索引的时候，我们可以精确的指定排序的顺序。例如，我们通过下面的方法来按照航班的range降序进行索引

1
create index on aircrafts_data(range desc);

在这种情况下，较大的值会出现左侧的树中，较小的树会出现在右侧的树中。如果我们可以从任意一个方向来遍历索引的值，为什么还要指定排序的顺序呢？

我们先来创建一个多列索引

这个地方没有直接使用原文中的例子，因为数据库的版本(原文中是9.6版本，我是用的是最新的13版本)以及Demo的示例数据都有了变化，原文中的运行结果已经无法在新版本中复现。但是下面的例子同样可以说明问题。

1
create index on aircrafts_data(aircraft_code,range);

然后我们可以使用这个索引来获取两列降序的数据

1
select aircraft_code,range from aircrafts_data order by aircraft_code,range;
1
2
3
4
5
6
7
8
9
10
11
12
 aircraft_code | range 
---------------+-------
 319           |  6700
 320           |  5700
 321           |  5600
 733           |  4200
 763           |  7900
 773           | 11100
 CN1           |  1200
 CR2           |  2700
 SU9           |  3000
(9 rows)
1
explain(costs on) select aircraft_code,range from aircrafts_data order by aircraft_code,range;
1
2
3
4
                                                     QUERY PLAN                                                     
--------------------------------------------------------------------------------------------------------------------
 Index Only Scan using aircrafts_data_aircraft_code_range_idx on aircrafts_data  (cost=0.14..12.27 rows=9 width=20)
(1 row)

我们也可以执行一个查询输出降序的结果

1
explain(costs on) select aircraft_code,range from aircrafts_data order by aircraft_code desc,range desc;
1
2
3
4
                                                         QUERY PLAN                                                          
-----------------------------------------------------------------------------------------------------------------------------
 Index Only Scan Backward using aircrafts_data_aircraft_code_range_idx on aircrafts_data  (cost=0.14..12.27 rows=9 width=20)
(1 row)

但是如果我们想获取获取一列升序一列降序的数据呢。

1
explain(costs on) select aircraft_code,range from aircrafts_data order by aircraft_code asc,range desc;
1
2
3
4
5
6
7
                                                        QUERY PLAN                                                        
--------------------------------------------------------------------------------------------------------------------------
 Sort  (cost=12.41..12.44 rows=9 width=20)
   Sort Key: aircraft_code, range DESC
   ->  Index Only Scan using aircrafts_data_aircraft_code_range_idx on aircrafts_data  (cost=0.14..12.27 rows=9 width=20)
(3 rows)

注：这个地方和原文中的输出不一致，原文中这个地方的执行计划是顺序扫描，这里是使用了索引查询，然后又进行了排序。

从上面的计划中可以看出，是先执行了索引扫描，因为我们指定的返回顺序和索引中的顺序不一致，因此对结果又重新进行了排序，增加了重新排序的时间成本。

在这种情况下，如果想要加快查询速度，在创建索引的时候可以指定排序的顺序

1
create index on aircrafts_data(aircraft_code asc,range desc);
1
explain(costs on) select aircraft_code,range from aircrafts_data order by aircraft_code desc,range asc;
1
2
3
4
                                                          QUERY PLAN                                                          
------------------------------------------------------------------------------------------------------------------------------
 Index Only Scan Backward using aircrafts_data_aircraft_code_range_idx1 on aircrafts_data  (cost=0.14..12.27 rows=9 width=20)
(1 row)
列的顺序

使用多列索引的另一个问题是索引中列的顺序。对于B树来说，这个顺序非常重要。页中的数据将按照第一个字段在前，然后是第二个字段这样的顺序来组织的。

如下图所示，在创建索引的时候指定的是 aircrafts_v(class,model)，其B树的内部结构如下图所示

实际上这么小的索引肯定都放在根页面里的，但是这里为了能够清楚一点，将其分布在了几个页面里。

很明显可以看出，像”class = 3”或者”class = 3 and model = ‘Boeing 777-300’”这样的搜索会非常高效。

但是，使用”model = ‘Boeing 777-300’”这样的谓词搜索效率就会降低：从根节点开始，我们无法决定下降到哪一个节点，因此，我们必须全部下降。这不意味着索引不能这么使用-但是这样是有问题的。假如说我们有3个种类的飞机，每个飞机中有大量的型号。那么我们将不得不搜索大约1/3的索引。这可能比全表扫描有效，也可能没有。

如果我们创建索引的时候改变一下顺序，即aircrafts_v(model,class)，那么索引就会变成下面的样子。

使用这个索引，谓词”model = ‘Boeing 777-300’”的搜索效率就会大大提升。当然，对于谓词”class = 3”的搜索就没有帮助了。

NULLs

“btree”访问方法会索引NULL值，同时支持IS NULL和IS NOT NULL

让我们看一下flight表，这个表中有NULL值。

1
create index on flights(actual_arrival);
1
explain(costs off) select * from flights where actual_arrival is null;
1
2
3
4
5
6
7
                      QUERY PLAN                       
-------------------------------------------------------
 Bitmap Heap Scan on flights
   Recheck Cond: (actual_arrival IS NULL)
   ->  Bitmap Index Scan on flights_actual_arrival_idx
         Index Cond: (actual_arrival IS NULL)
(4 rows)

NULL值位于叶节点的一端或者另一端取决于索引是怎么创建的(NULLS FIRST或者NULLS LAST).如果查询中包含排序，那么这一点就比较重要了：如果SELECT命令在其子句ORDER BY指定的NULL顺序和创建索引指定的NULL顺序一致的话，该索引就能生效了。

在下面的例子中，索引和ORDER子句指定的NULL顺序是一致的，因此索引是生效的。

1
explain(costs off) select * from flights order by actual_arrival NULLS LAST;
1
2
3
4
                       QUERY PLAN                       
--------------------------------------------------------
 Index Scan using flights_actual_arrival_idx on flights
(1 row)

这个例子，索引和ORDER子句指定的NULL顺序不一致的，因此索引不能生效。

1
explain(costs off) select * from flights order by actual_arrival NULLS FIRST;
1
2
3
4
5
6
               QUERY PLAN               
----------------------------------------
 Sort
   Sort Key: actual_arrival NULLS FIRST
   ->  Seq Scan on flights
(3 rows)

如果上面的语句想使用索引，就必须在创建索引的时候指定NULL顺序

1
create index flights_nulls_first_idx on flights(actual_arrival NULLS FIRST);

NULL值需要单独处理时因为NULL是不可排序的，就是说，NULL和其它值的比较的结果是没有定义的。

1
2
3
\pset null NULL

select null < 42;
1
2
3
4
 ?column?
----------
 NULL
(1 row)

正如前面所说的，B树的核心就是为了那些可以排序的数据使用的。那么不能排序的NULL值显然是和B树的概念背道而驰。但是，NULL值太重要了，重要的以至于我们不得不专门为NULL值设置例外。

由于可以对NULL进行索引，因此，即使没有任何条件的查询也可以使用索引（因为索引中肯定包含所有的表行的信息）。如果查询的数据需要排序，而索引的顺序和其要获取的排序相同的话，计划员可能会选择使用索引，因为这个就不需要进行单独的排序了。

属性

接下来我们来看一下”Btree”访问方法属性。

1
2
3
4
5
6
7
8
 amname |     name      | pg_indexam_has_property 
--------+---------------+-------------------------
 btree  | can_order     | t
 btree  | can_unique    | t
 btree  | can_multi_col | t
 btree  | can_exclude   | t
 btree  | can_include   | t
(5 rows)

正如我们看到的，B-tree支持数据排序、唯一性约束-目前只有B树访问方法支持这两个属性。也支持多列索引，其它访问方法可能也支持这个。我们下次将讨论对EXCLUDE约束的支持，这并不是没有原因的。

1
2
3
4
5
6
     name      | pg_index_has_property
---------------+-----------------------
 clusterable   | t
 index_scan    | t
 bitmap_scan   | t
 backward_scan | t

B树索引支持两种获取值的技术：索引扫描和位图扫描。访问方法可以“向前”或者“向后遍历树”。clusterable的作用在第二节-索引属性有提到。简单来说就是支持根据索引的顺序对指定的表进行物理上的重排序。

1
2
3
4
5
6
7
8
9
10
11
        name        | pg_index_column_has_property 
--------------------+------------------------------
 asc                | t
 desc               | f
 nulls_first        | f
 nulls_last         | t
 orderable          | t
 distance_orderable | f
 returnable         | t
 search_array       | t
 search_nulls       | t

前4个属性解释了某个特定的列的值支持的排序。在上面的例子中，值支持按升序和nulls_last排序。但是正如前面演示的那样，其它的排序也是可以支持的。

search_array 表示索引支持下面这样的表达式

1
explain(costs off) select * from aircrafts where aircraft_code in ('733','763','773');
1
2
3
4
5
                                  QUERY PLAN                                   
-------------------------------------------------------------------------------
 Index Scan using aircrafts_data_aircraft_code_range_idx1 on aircrafts_data ml
   Index Cond: (aircraft_code = ANY ('{733,763,773}'::bpchar[]))
(2 rows)

“returnable”属性表示支持仅索引扫描，这是因为索引的行存储索引值本身。这里有必要讲一下基于 B 树的覆盖索引

具有额外行的唯一索引

正如前面讨论的那样，一个覆盖索引包含了查询中需要的值，因此几乎不需要访问表本身。唯一索引也可以用作覆盖索引。

但是假设如果我们想要向唯一索引中添加所需要的额外的列，那么这个新的组合索引可能就不能保证原来的唯一约束了。这时候就需要在同一个列上建立两个索引，一个是唯一索引，用来做完整性约束；另外一个是非唯一索引，用来支持覆盖的。

这一段稍微绕一些。具体来说，就是，我们本来是想保证字段a不能重复，那么就需要对a建立一个唯一索引，这个唯一索引可以保证a不会重复。但是假设我们在查询的时候，需要同时查询a和b，如果这时候我们想使用覆盖索引，那么就需要把b也添加到索引中,即建立一个唯一联合索引。但是这时候a的唯一性就无法保证了。因为此时，(1,2)和(1,3)都是合法的，但是显然，没有保证a的唯一性。为了解决这个问题，就需要对a建立两个索引，一个只有a的用来保证唯一性的索引，一个用来做覆盖索引的非唯一索引。建立两个索引显然增加了维护索引的开销。

在原文作者的公司里，有一个大牛改进了”btree”方法，可以让额外的、非唯一的列可以包含在唯一索引中，这个补丁在PostgreSQL 11的时候被提交。

我目前使用的版本是postgreSQL 13。

下面我们来看一下例子：

1
\d bookings;
1
2
3
4
5
6
7
8
9
10
                        Table "bookings.bookings"
    Column    |           Type           | Collation | Nullable | Default 
--------------+--------------------------+-----------+----------+---------
 book_ref     | character(6)             |           | not null | 
 book_date    | timestamp with time zone |           | not null | 
 total_amount | numeric(10,2)            |           | not null | 
Indexes:
    "bookings_pkey" PRIMARY KEY, btree (book_ref)
Referenced by:
    TABLE "tickets" CONSTRAINT "tickets_book_ref_fkey" FOREIGN KEY (book_ref) REFERENCES bookings(book_ref)

在这个表中，有一个常规的B树主键索引。我们新创建一个带有额外列的唯一索引

1
create unique index bookings_pkey2 on bookings(book_ref) INCLUDE (book_date);

然后，用我们新创建的索引替换原来的索引

1
2
3
4
5
6
7
8
9
begin;

alter table bookings drop constraint bookings_pkey cascade;

alter table bookings add primary key using index bookings_pkey2;

alter table tickets add foreign key (book_ref) references bookings (book_ref);

commit;
1
\d bookings
1
2
3
4
5
6
7
8
9
10
                        Table "bookings.bookings"
    Column    |           Type           | Collation | Nullable | Default 
--------------+--------------------------+-----------+----------+---------
 book_ref     | character(6)             |           | not null | 
 book_date    | timestamp with time zone |           | not null | 
 total_amount | numeric(10,2)            |           | not null | 
Indexes:
    "bookings_pkey2" PRIMARY KEY, btree (book_ref) INCLUDE (book_date)
Referenced by:
    TABLE "tickets" CONSTRAINT "tickets_book_ref_fkey" FOREIGN KEY (book_ref) REFERENCES bookings(book_ref)

现在这个索引就可以既作为唯一索引，又可以作为覆盖索引了。例如：

1
explain(costs off) select book_ref, book_date from bookings where book_ref = '059FC4';
1
2
3
4
5
                    QUERY PLAN                    
--------------------------------------------------
 Index Only Scan using bookings_pkey2 on bookings
   Index Cond: (book_ref = '059FC4'::bpchar)
(2 rows)
1
select * from bookings limit 1;
1
2
3
4
 book_ref |       book_date        | total_amount 
----------+------------------------+--------------
 00000F   | 2017-07-05 00:12:00+00 |    265700.00
(1 row)
1
insert into bookings values('00000F','2018-07-05 00:12:00+00',265700.00);
1
2
ERROR:  duplicate key value violates unique constraint "bookings_pkey2"
DETAIL:  Key (book_ref)=(00000F) already exists.

感谢Docker可以让我快速启动一个postgresql 10的数据库实例，在这个实例里，测试一下下面的命令

1
select version()
1
2
3
4
5
                                                              version                                                               
------------------------------------------------------------------------------------------------------------------------------------
 PostgreSQL 10.17 (Debian 10.17-1.pgdg90+1) on x86_64-pc-linux-gnu, compiled by gcc (Debian 6.3.0-18+deb9u1) 6.3.0 20170516, 64-bit
(1 row)

1
create unique index bookings_pkey2 on bookings(book_ref) INCLUDE (book_date);
1
2
ERROR:  syntax error at or near "INCLUDE"
LINE 1: ...unique index bookings_pkey2 on bookings(book_ref) INCLUDE (b...

可以看出，向唯一索引中添加额外的索引在10以及10以前的版本中都是不支持的

索引的创建

众所周知，但是也很重要的一个事情是，对于大型表，最好是在没有索引的情况下先加载数据，在加载数据完成后再去创建对应的索引。这样速度不仅快，而且很可能创建的索引也会变小。

这是因为Btree索引树的创建过程比按行把值插入树是一个更加高效的过程。粗略的来说，创建过程会先对表中所有可用的数据进行排序，然后创建这些数据的叶节点，然后内部的页面在这些叶子节点上逐渐向上构建，直到整个树收敛到根部为止。

补充一下新数据插入过程：当一个存在的叶子页面不能放下新的元组，就会有一个新的叶子页面被增加到B树索引中。页面拆分操作会把一部分数据移到新的页面上，从而为原来将要溢出的数据腾出空间。页面拆分也要在父页面上插入新的子页面的连接，从而导致父页面也可能会发生分裂。页面拆分用一种递归的方式向上级联。当根页面也不能放下新的下级连接的时候，就会发生根节点拆分。这将会通过在原来的根页面的上一级创建一个新的根页面来增加一个新的层级。

该过程的速度取决于可用RAM的大小，这个大小取决于“maintenance_work_mem”的限制。对于唯一索引来说，除了“maintenance_work_mem”，还要为其分配”work_mem”大小的内存。

比较语义

前面我们提到过对于哈希索引来说，PostgreSQL必须直到对于不同的数据类型运用哪个哈希函数。同样的，PostgreSQL也必须直到怎么去比较值，这个被用来排序、分组、合并连接等等。PostgreSQL不会把这些信息绑定在操作符名字上(例如 > < =)，因为用户可以定义自己的数据类型，并且可以给不同的操作符对应不同的名字。”btree”访问方法使用的运算符族定义了运算符的名称。

例如，这些比较运算符用于“bool_ops”运算符系列：

1
2
3
4
5
6
7
8
9
10
select   amop.amopopr::regoperator as opfamily_operator,
         amop.amopstrategy
from     pg_am am,
         pg_opfamily opf,
         pg_amop amop
where    opf.opfmethod = am.oid
and      amop.amopfamily = opf.oid
and      am.amname = 'btree'
and      opf.opfname = 'bool_ops'
order by amopstrategy;
1
2
3
4
5
6
7
8
  opfamily_operator  | amopstrategy 
---------------------+--------------
 <(boolean,boolean)  |            1
 <=(boolean,boolean) |            2
 =(boolean,boolean)  |            3
 >=(boolean,boolean) |            4
 >(boolean,boolean)  |            5
(5 rows)

在这里，我们可以看到5个比较运算符。但是正如前面所说的那样，我们不应该依赖它们的名称。但是为了知道每个运算符对应的比较，pg引入了策略编号的概念。每个策略编号对应一个比较

  • 1 — less
  • 2 — less or equal
  • 3 — equal
  • 4 — greater or equal
  • 5 — greater

一些操作符族包含多个运算符来实现同一个策略，例如，“integer_ops”为策略1包含了下面的操作符

1
2
3
4
5
6
7
8
9
10
select   amop.amopopr::regoperator as opfamily_operator
from     pg_am am,
         pg_opfamily opf,
         pg_amop amop
where    opf.opfmethod = am.oid
and      amop.amopfamily = opf.oid
and      am.amname = 'btree'
and      opf.opfname = 'integer_ops'
and      amop.amopstrategy = 1
order by opfamily_operator;
1
2
3
4
5
6
7
8
9
10
11
12
  opfamily_operator   
----------------------
 <(integer,bigint)
 <(smallint,smallint)
 <(integer,integer)
 <(bigint,bigint)
 <(bigint,integer)
 <(smallint,integer)
 <(integer,smallint)
 <(smallint,bigint)
 <(bigint,smallint)
(9 rows)

由于这个原因，优化器可以不需要类型转换就可以比较同一个运算符系列中包含的不同类型的值。

新数据类型的支持

这篇文章提供了为创建一个复数类型，并创建其对应的操作符类用来支持该类型数据的排序的示例。这个例子使用的是C语言，在要求效率的情况下，这是一个很合理的选择。但是作为演示目的，下面我们使用纯SQL语句来实现，以便更好的理解比较语义。

我们先创建一个具有实部和虚部的复数类型：

1
create type complex as (re float, im float);

然后我们创建一个包含此数据类型的表，然后增加一些数据。

1
2
3
create table numbers(x complex);
 
insert into numbers values ((0.0,10.0)),((4.0,3.0)),((3.0,1.0)),((2.0,3.0)),((5.0,6.0)),((2.0,8.0));

现在问题是，在没有定义怎么排序的情况下，数据库怎么对复数类型进行排序

事实证明，PG已经为我们新的数据类型定义了默认的排序操作符

1
select * from numbers order by x;
1
2
3
4
5
6
7
8
9
   x    
--------
 (0,10)
 (2,3)
 (2,8)
 (3,1)
 (4,3)
 (5,6)
(6 rows)

默认情况下，复合类型的排序是按照其内部字段的顺序进行的：第一个字段先被比较，然后是第2个，一次类推。这个和逐字符比较字符串的方式大致差不多。但是我们可以定义新的排序方式，例如，将复数看作是向量，并按照其模数（长度）进行排序。模数的计算是其坐标平方和的平方根。为了这么做，我们先定义一个函数来计算模数。

1
2
3
create function modulus(a complex) returns float as $$
    select sqrt(a.re*a.re + a.im*a.im);
$$ immutable language sql;

然后我们使用这个辅助函数来定义5个比较运算函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
create function complex_lt(a complex, b complex) returns boolean as $$
    select modulus(a) < modulus(b);
$$ immutable language sql;

create function complex_le(a complex, b complex) returns boolean as $$
    select modulus(a) <= modulus(b);
$$ immutable language sql;

create function complex_eq(a complex, b complex) returns boolean as $$
    select modulus(a) = modulus(b);
$$ immutable language sql;

create function complex_ge(a complex, b complex) returns boolean as $$
    select modulus(a) >= modulus(b);
$$ immutable language sql;

create function complex_gt(a complex, b complex) returns boolean as $$
    select modulus(a) > modulus(b);
$$ immutable language sql;

然后需要创建对应的运算符。为了说明他们不需要叫 “>” “<”之类的名字(即PostgreSQL不会根据操作符的名字来判断其是不是比较操作)，我们为这些操作符起一些奇怪的名字。

1
2
3
4
5
6
7
8
9
create operator #<#(leftarg=complex, rightarg=complex, procedure=complex_lt);

create operator #<=#(leftarg=complex, rightarg=complex, procedure=complex_le);

create operator #=#(leftarg=complex, rightarg=complex, procedure=complex_eq);

create operator #>=#(leftarg=complex, rightarg=complex, procedure=complex_ge);

create operator #>#(leftarg=complex, rightarg=complex, procedure=complex_gt);

此时，我们可以比较值了

1
select (1.0,1.0)::complex #<# (1.0,3.0)::complex;

除了5个运算符以外，”btree”还必须定义一个辅助函数。如果第一个值小于、等于或者大于第2个值，它必须返回-1、0或者1

1
2
3
4
5
6
create function complex_cmp(a complex, b complex) returns integer as $$
    select case when modulus(a) < modulus(b) then -1
                when modulus(a) > modulus(b) then 1 
                else 0
           end;
$$ language sql;

辅助函数是访问方法在内部需要使用的方法/函数。例如，在B树上搜索某个值的时候，需要确定下降到当前内部页面的哪个子节点上。就需要用辅助函数来将搜索的值和内部页面上的各个索引值进行比较了。

现在就可以创建操作符类了。（创建操作符类会自动创建一个同名的操作符族）

1
2
3
4
5
6
7
8
9
create operator class complex_ops
default for type complex
using btree as
    operator 1 #<#,
    operator 2 #<=#,
    operator 3 #=#,
    operator 4 #>=#,
    operator 5 #>#,
    function 1 complex_cmp(complex,complex);

现在排序按照我们期待的那样工作了

1
select * from numbers order by x;
1
2
3
4
5
6
7
8
9
   x    
--------
 (3,1)
 (2,3)
 (4,3)
 (5,6)
 (2,8)
 (0,10)
(6 rows)

当然它也支持Btree索引了。

内部

我们可以使用”pageinspect”拓展来查看B-tree的内部结构

1
create extension pageinspect;
1
select * from bt_metap('ticket_flights_pkey');
1
2
3
4
 magic  | version | root | level | fastroot | fastlevel | oldest_xact | last_cleanup_num_tuples | allequalimage 
--------+---------+------+-------+----------+-----------+-------------+-------------------------+---------------
 340322 |       4 |  196 |     2 |      196 |         2 |           0 |                      -1 | t
(1 row)

这里面最有趣的就是索引级别了，上百万的数据行只需要2级就可以了(不包含根)

第164个块（页面）的统计信息

1
select type, live_items, dead_items, avg_item_size, page_size, free_size from bt_page_stats('ticket_flights_pkey',164);
1
2
3
4
 type | live_items | dead_items | avg_item_size | page_size | free_size 
------+------------+------------+---------------+-----------+-----------
 l    |        204 |          0 |            31 |      8192 |       812
(1 row)

也可以看到块（页面）内部的数据

1
select itemoffset, ctid, itemlen, left(data,56) as data from bt_page_items('ticket_flights_pkey',164) limit 5;
1
2
3
4
5
6
7
8
9
 itemoffset |    ctid    | itemlen |                           data                           
------------+------------+---------+----------------------------------------------------------
          1 | (454,1)    |      24 | 1d 30 30 30 35 34 33 32 33 32 38 31 33 31 00 00
          2 | (2039,110) |      32 | 1d 30 30 30 35 34 33 32 33 32 38 30 38 30 00 00 44 52 00
          3 | (1925,87)  |      32 | 1d 30 30 30 35 34 33 32 33 32 38 30 38 30 00 00 91 79 00
          4 | (519,51)   |      32 | 1d 30 30 30 35 34 33 32 33 32 38 30 38 30 00 00 2a 7a 00
          5 | (358,22)   |      32 | 1d 30 30 30 35 34 33 32 33 32 38 30 38 31 00 00 13 0c 00
(5 rows)

第一行数据和技术相关，指定了这一块所有元素的上限(这个我在本篇文章开头的并发搜索中提到过)。数据本身从第二行开始，即最左边的子节点的数据是163，接着是232，一次往后类推。

现在，遵循良好的传统，阅读代码和README是有意义的。

另外一个很有用的拓展是amcheck，这个插件在pg 10及以上版本可以使用。这个拓展能够检查B树中数据的逻辑一致性，使我们能够提前检测故障。