PostgreSQL的B-tree索引的使用细说
|
B-tree索引适合用于存储排序的数据。对于这种数据类型需要定义大于、大于等于、小于、小于等于操作符。
通常情况下，B-tree的索引记录存储在数据页中。叶子页中的记录包含索引数据（keys）以及指向heap tuple记录（即表的行记录TIDs）的指针。内部页中的记录包含指向索引子页的指针和子页中最小值。
B-tree有几点重要的特性：
1、B-tree是平衡树，即每个叶子页到root页中间有相同个数的内部页。因此查询任何一个值的时间是相同的。
2、B-tree中一个节点有多个分支，即每页（通常8KB）具有许多TIDs。因此B-tree的高度比较低，通常4到5层就可以存储大量行记录。
3、索引中的数据以非递减的顺序存储（页之间以及页内都是这种顺序），同级的数据页由双向链表连接。因此不需要每次都返回root，通过遍历链表就可以获取一个有序的数据集。 等值查询
例如通过"indexed-field = expression"形式的条件查询49这个值。 root节点有三个记录：(4,32,64)。从root节点开始进行搜索，由于32≤ 49 < 64，所以选择32这个值进入其子节点。通过同样的方法继续向下进行搜索一直到叶子节点，最后查询到49这个值。
实际上，查询算法远不止看上去的这么简单。比如，该索引是非唯一索引时，允许存在许多相同值的记录，并且这些相同的记录不止存放在一个页中。此时该如何查询？我们返回到上面的的例子，定位到第二层节点(32,43,49)。如果选择49这个值并向下进入其子节点搜索，就会跳过前一个叶子页中的49这个值。因此，在内部节点进行等值查询49时，定位到49这个值，然后选择49的前一个值43，向下进入其子节点进行搜索。最后，在底层节点中从左到右进行搜索。
(另外一个复杂的地方是，查询的过程中树结构可能会改变，比如分裂)
非等值查询
通过"indexed-field ≤ expression" (or "indexed-field ≥ expression")查询时，首先通过"indexed-field = expression"形式进行等值（如果存在该值）查询，定位到叶子节点后，再向左或向右进行遍历检索。 范围查询
范围查询"expression1 ≤ indexed-field ≤ expression2"时，需要通过 "expression1 ≤ indexed-field =expression2"找到一匹配值，然后在叶子节点从左到右进行检索，一直到不满足"indexed-field ≤ expression2" 的条件为止；或者反过来，首先通过第二个表达式进行检索，在叶子节点定位到该值后，再从右向左进行检索，一直到不满足第一个表达式的条件为止。 下面是一个查询计划的实例。通过demo database中的aircraft表进行介绍。该表有9行数据，由于整个表只有一个数据页，所以执行计划不会使用索引。为了解释说明问题，我们使用整个表进行说明。
demo=# select * from aircrafts; aircraft_code | model | range ---------------+---------------------+------- 773 | Boeing 777-300 | 11100 763 | Boeing 767-300 | 7900 SU9 | Sukhoi SuperJet-100 | 3000 320 | Airbus A320-200 | 5700 321 | Airbus A321-200 | 5600 319 | Airbus A319-100 | 6700 733 | Boeing 737-300 | 4200 CN1 | Cessna 208 Caravan | 1200 CR2 | Bombardier CRJ-200 | 2700 (9 rows) demo=# create index on aircrafts(range); demo=# set enable_seqscan = off;
（更准确的方式：create index on aircrafts using btree(range)，创建索引时默认构建B-tree索引。）
等值查询的执行计划：
demo=# explain(costs off) select * from aircrafts where range = 3000; QUERY PLAN --------------------------------------------------- Index Scan using aircrafts_range_idx on aircrafts Index Cond: (range = 3000) (2 rows)
非等值查询的执行计划：
demo=# explain(costs off) select * from aircrafts where range < 3000; QUERY PLAN --------------------------------------------------- Index Scan using aircrafts_range_idx on aircrafts Index Cond: (range < 3000) (2 rows)
范围查询的执行计划：
demo=# explain(costs off) select * from aircrafts where range between 3000 and 5000; QUERY PLAN ----------------------------------------------------- Index Scan using aircrafts_range_idx on aircrafts Index Cond: ((range >= 3000) AND (range <= 5000)) (2 rows)
排序
再次强调，通过index、index-only或bitmap扫描，btree访问方法可以返回有序的数据。因此如果表的排序条件上有索引，优化器会考虑以下方式：表的索引扫描；表的顺序扫描然后对结果集进行排序。
排序顺序
当创建索引时可以明确指定排序顺序。如下所示，在range列上建立一个索引，并且排序顺序为降序：
1demo=# create index on aircrafts(range desc);
本案例中，大值会出现在树的左边，小值出现在右边。为什么有这样的需求？这样做是为了多列索引。创建aircraft的一个视图，通过range分成3部分：
demo=# create view aircrafts_v as select model, case when range < 4000 then 1 when range < 10000 then 2 else 3 end as class from aircrafts;
demo=# select * from aircrafts_v; model | class ---------------------+------- Boeing 777-300 | 3 Boeing 767-300 | 2 Sukhoi SuperJet-100 | 1 Airbus A320-200 | 2 Airbus A321-200 | 2 Airbus A319-100 | 2 Boeing 737-300 | 2 Cessna 208 Caravan | 1 Bombardier CRJ-200 | 1 (9 rows)
然后创建一个索引（使用下面表达式）：
demo=# create index on aircrafts( (case when range < 4000 then 1 when range < 10000 then 2 else 3 end), model);
现在，可以通过索引以升序的方式获取排序的数据：
demo=# select class, model from aircrafts_v order by class, model; class | model -------+--------------------- 1 | Bombardier CRJ-200 1 | Cessna 208 Caravan 1 | Sukhoi SuperJet-100 2 | Airbus A319-100 2 | Airbus A320-200 2 | Airbus A321-200 2 | Boeing 737-300 2 | Boeing 767-300 3 | Boeing 777-300 (9 rows)
demo=# explain(costs off) select class, model from aircrafts_v order by class, model; QUERY PLAN -------------------------------------------------------- Index Scan using aircrafts_case_model_idx on aircrafts (1 row)
同样，可以以降序的方式获取排序的数据：
demo=# select class, model from aircrafts_v order by class desc, model desc; class | model -------+--------------------- 3 | Boeing 777-300 2 | Boeing 767-300 2 | Boeing 737-300 2 | Airbus A321-200 2 | Airbus A320-200 2 | Airbus A319-100 1 | Sukhoi SuperJet-100 1 | Cessna 208 Caravan 1 | Bombardier CRJ-200 (9 rows) demo=# explain(costs off) select class, model from aircrafts_v order by class desc, model desc; QUERY PLAN ----------------------------------------------------------------- Index Scan BACKWARD using aircrafts_case_model_idx on aircrafts (1 row)
然而，如果一列以升序一列以降序的方式获取排序的数据的话，就不能使用索引，只能单独排序：
demo=# explain(costs off) select class, model from aircrafts_v order by class ASC, model DESC; QUERY PLAN ------------------------------------------------- Sort Sort Key: (CASE ... END), aircrafts.model DESC -> Seq Scan on aircrafts (3 rows)
（注意，最终执行计划会选择顺序扫描，忽略之前设置的enable_seqscan = off。因为这个设置并不会放弃表扫描，只是设置他的成本----查看costs on的执行计划）
若有使用索引，创建索引时指定排序的方向：
demo=# create index aircrafts_case_asc_model_desc_idx on aircrafts( (case when range < 4000 then 1 when range < 10000 then 2 else 3 end) ASC, model DESC);
demo=# explain(costs off) select class, model from aircrafts_v order by class ASC, model DESC; QUERY PLAN ----------------------------------------------------------------- Index Scan using aircrafts_case_asc_model_desc_idx on aircrafts (1 row)
列的顺序
当使用多列索引时与列的顺序有关的问题会显示出来。对于B-tree，这个顺序非常重要：页中的数据先以第一个字段进行排序，然后再第二个字段，以此类推。 （编辑：焦作站长网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
