PostgreSQL索引详解4——btree索引

1、简介

B树索引类型可以说是使用的最广泛的索引了，在PostgreSQL中可以在任何数据类型上使用btree索引，支持排序，支持大于、小于、等于、大于或等于、小于或等于的搜索。

B树具有一些重要的特征：

• B树是平衡的，也就是说，每个叶页面与根都由相同数量的内部页面分隔开。因此，搜索任何值都需要花费相同的时间。
• B树是多分支的，即每个页面（通常为8 KB）包含许多（数百个）ctid。因此，B树的深度很小，对于非常大的表，实际上可以达到4–5的深度。
• 索引中的数据按非递减顺序排序（在页面之间和每个页面内部），并且同一级别的页面通过双向列表相互连接。因此，我们可以仅通过列表的一个方向或另一个方向获得有序数据集，而不必每次都返回到根。

一个简单的单字段的btree索引大致如上图所示，索引的第一页是一个元页，它引用索引根。内部节点位于根下方，叶子页面位于最底行。向下箭头表示从叶节点到表行（ctid）的引用。详细的结构我们后面再介绍。

2、使用实例

我们结合具体的场景来介绍btree索引是如何工作的。

2.1、等值查询
等值查询例如id=49这种：

首先搜索从根节点开始，我们需要确定要降到哪个子节点。由于知道根节点（4、32、64）中的键，因此我们可以计算出子节点中的值范围。由于32≤49 <64，所以我们需要下降到第二个子节点。接下来，递归重复相同的过程，直到我们到达一个叶节点，可以从该叶节点获得所需的ctid。

2.2、范围查询
范围查询可以分为两类：
–如id<=35:

如图所示，首先会搜索id=35的值(如果有的话)，然后按照适当的方向遍历叶页面直到结束。

–23<=id<64:

首先通过条件"id=23"找到一个值，然后遍历叶页面直到"id<64"被满足; 反之亦然：从第二个表达式开始，然后朝相反的方向走，直到到达第一个表达式。该图显示了条件23≤id<64的过程。

2.3、排序
要注意的是，无论哪种扫描类型(index scan、index only scan、bitmap scan)，使用btree索引都会返回有序的数据。所以，如果在排序列上存在索引，优化器会首先考虑是索引扫描，否则就是先顺序扫描然后排序。

–指定索引顺序：

bill@bill=>create index idx_t1 on t1(c1 desc);
CREATE INDEX

如上面这个索引，c1列中较大的值将出现在左侧的树中，而较小的值将出现在右侧。但是并不是说只有order by c1 desc才能使用索引，order by c1 asc也可以使用索引，因为我们可以从任意方向去遍历索引，那么在索引上指定顺序又有什么意义呢？

虽然我们可以从任意方向遍历索引去排序，但是如果在一个组合索引中我们要对不同的列一个升序一个降序去排序的话，这个时候指定索引的顺序就很有必要了。

–创建组合索引

bill@bill=>create index idx_t1 on t1(c1,c2);
CREATE INDEX

--对c1、c2列排序
bill@bill=>explain select * from t1 order by c1,c2;
                              QUERY PLAN                              
----------------------------------------------------------------------
 Index Scan using idx_t1 on t1  (cost=0.15..45.05 rows=2040 width=12)
(1 row)

可以看到这种排序是可以使用索引的，但是如果我们换种写法呢？

bill@bill=>explain select * from t1 order by c1 desc,c2 asc;
                         QUERY PLAN                          
-------------------------------------------------------------
 Sort  (cost=142.54..147.64 rows=2040 width=12)
   Sort Key: c1 DESC, c2
   ->  Seq Scan on t1  (cost=0.00..30.40 rows=2040 width=12)
(3 rows)

这种情况就没法使用索引去排序了，因此我们要指定索引的顺序才行：

bill@bill=>create index idx_t1 on t1(c1 desc,c2 asc);
CREATE INDEX
bill@bill=>explain select * from t1 order by c1 desc,c2 asc;
                              QUERY PLAN                              
----------------------------------------------------------------------
 Index Scan using idx_t1 on t1  (cost=0.15..45.05 rows=2040 width=12)
(1 row)

2.4、空值
PostgreSQL的btree索引是可以存储null值的(oracle中不可以)。并支持按条件IS NULL和IS NOT NULL进行搜索。

bill@bill=>explain select * from t1 where c1 is null;
                              QUERY PLAN                              
----------------------------------------------------------------------
 Bitmap Heap Scan on t1  (cost=1.53..8.97 rows=10 width=12)
   Recheck Cond: (c1 IS NULL)
   ->  Bitmap Index Scan on idx_t1  (cost=0.00..1.53 rows=10 width=0)
         Index Cond: (c1 IS NULL)
(4 rows)

在索引中null值存储在索引的一端，取决于创建索引时指定nulls first还是nulls last。
如果查询包括排序，则这一点很重要：如果SELECT命令在其ORDER BY子句中指定的NULL顺序与构建索引指定的顺序相同（NULLS FIRST或NULLS LAST），则可以使用索引，否则将无法使用索引。
不过在数据库中null是无法和其它值进行比较的，例如：

bill@bill=>select null < 10;
 ?column? 
----------
 
(1 row)

而pg的btree索引中却可以存储null值，这和btree的设计有点相悖，不过因为NULL在数据库中起着非常重要的作用，这一设计还是十分有用的。

3、属性

3.1、btree访问方法的属性：

bill=# select a.amname, p.name, pg_indexam_has_property(a.oid,p.name)
bill-# from pg_am a,
bill-#      unnest(array['can_order','can_unique','can_multi_col','can_exclude']) p(name)
bill-# where a.amname = 'btree'
bill-# order by a.amname;
 amname |     name      | pg_indexam_has_property 
--------+---------------+-------------------------
 btree  | can_order     | t
 btree  | can_unique    | t
 btree  | can_multi_col | t
 btree  | can_exclude   | t
(4 rows)

可以看到，B树可以排序数据并支持唯一性——这是为我们提供此类属性的唯一访问方法。也允许使用多列索引，但是其他访问方法（尽管不是全部）都可以支持此类索引。

3.2、btree索引的属性：

bill=# select p.name, pg_index_has_property('t_a_idx'::regclass,p.name)
bill-# from unnest(array[
bill(#        'clusterable','index_scan','bitmap_scan','backward_scan'
bill(#      ]) p(name);
     name      | pg_index_has_property 
---------------+-----------------------
 clusterable   | t
 index_scan    | t
 bitmap_scan   | t
 backward_scan | t
(4 rows)

btree索引可以支持index_