Postgresql索引结构-Btree
B-tree索引类型，实现为“btree”访问⽅法，适⽤于可以排序的数据。换句话说，必须为数据类型定义“更⼤”、“更⼤或相等”、“更⼩”、“更⼩或相等”和“相等”操作符。
在B-tree的数据结构架构图中，B-tree的索引⾏被存在索引页中。在存储叶⼦节点的页中，这些⾏包含建⽴索引的数据(键)和指向表⾏的指针(TIDs)。在存储分⽀节点和根节点的页中，每⾏引⽤索引的⼀个⼦页，并包含该页中的最⼩值。下⾯是⼀个使⽤整数键的字段索引的简化⽰例。
索引的第⼀页是⼀个元页，它引⽤索引根。内部节点位于根的下⾯，⽽叶页位于最底部⾏。向下箭头表⽰从叶节点到表⾏(TIDs)的引⽤。
B-trees 有以下重要特征：
b树是平衡的，也就是说，每个叶页与根页之间⽤相同数量的内部页分隔。因此，搜索任何值都需要同样的时间。
b树是多分⽀的，也就是说，每个页⾯(通常为8 KB)包含许多(数百)个TID。因此，b树的深度⾮常⼩，对于⾮常⼤的表，实际上可以达到4-5。
索引中的数据按⾮降序排序(页⾯之间和每个页⾯内部)，相同级别的页⾯通过双向列表相互连接。因此，我们可以通过⼀个列表遍历⼀个或另⼀个⽅向，⽽不必每次都返回到根，来获得有序的数据集。等值查询
让我们考虑在树中通过条件“index -field = expression”来搜索⼀个值。⽐如说，查询49。
搜索从根节点开始，我们需要确定要下降到哪个⼦节点。由于知道根节点(4,32,)中的键，因此我们计算出⼦节点中的值范围。由于32≤49< ，我们需要下降到第⼆个⼦节点。接下来，重复相同的过程，直到我们到达⼀个叶节点，从中可以获得所需的TID。
⾮等值查询
当通过条件“indexed-field ≤ expression”(或“indexed-field ≥ expression”)进⾏搜索时，我们⾸先通过相等条件“indexed-field = expression”在索引中找到⼀个值(如果有的话)，然后按照适当的⽅向遍历叶⼦页直到最后。下图以n ≤ 35为例：
\">\"和“<”以类似的⽅式，只是最初找到的值必须删除。范围检索
当搜索范围“expression1≤indexd -field≤expression2”时，我们通过条件“indexd -field = expression1”找到⼀个值，然后在满⾜条件“indexd -field≤expression2”时继续遍历叶⼦页⾯;反之亦然:从第⼆个表达式开始，向相反的⽅向⾛，直到我们到达第⼀个表达式。下图以23 ≤ n ≤ 为例：
多列索引：演⽰数据：
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 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，这个顺序⾮常重要:页⾯内的数据将按第⼀个字段排序，然后按第⼆个字段排序，依此类推。⼤概结构如下：
从这个图表中可以清楚地看出，通过像“class = 3”(仅通过第⼀个字段进⾏搜索)或“class = 3 and model =‘波⾳777-300’”(通过两个字段进⾏搜索)这样的谓词进⾏搜索将有效地⼯作。
然⽽，通过谓词“model = 'Boeing 777-300'”进⾏搜索的效率要低得多:从根开始，我们不能确定要下降到哪⼀个⼦节点，因此，我们必须下降到所有的⼦节点。这并不意味着这样的索引永远不会被使⽤——它的效率是有争议的。例如，如果我们有三个级别的飞机，每个级别有很多型号，我们将不得不浏览⼤约三分之⼀的索引，这可能效率还不如全表扫描；
因此在实际使⽤过程中如果既有class = 3，class = 3 and model =‘波⾳777-300’，model =‘波⾳777-300’三类查询，⼀般为（class，model）和model建两个索引。 NULLs
Btree⽀持⽤is null 和is not null扫描索引。
demo=# create index on flights(actual_arrival);
demo=# explain(costs off) select * from flights where actual_arrival is null; 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)
空值位于叶节点的⼀端或另⼀端，这取决于索引是如何创建的(NULLS FIRST or NULLS LAST)。如果查询包含排序，这⼀点很重要:如果SELECT命令在其order BY⼦句中指定的空值顺序与构建索引指定的顺序相同，则可以使⽤索引(NULLS FIRST or NULLS LAST)。
