结构
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，通过遍历链表就可以获取一个有序的数据集。
下面是一个索引的简单例子，该索引存储的记录为整型并只有一个字段：
该索引最顶层的页是元数据页，该数据页存储索引root页的相关信息。内部节点位于root下面，叶子页位于最下面一层。向下的箭头表示由叶子节点指向表记录（TIDs）。
等值查询
例如通过"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"形式进行等值（如果存在该值）查询，定位到叶子节点后，再向左或向右进行遍历检索。
下图是查询 n ≤ 35的示意图：
大于和小于可以通过同样的方法进行查询。查询时需要排除等值查询出的值。
范围查询
范围查询"expression1 ≤ indexed-field ≤ expression2"时，需要通过 "expression1 ≤ indexed-field =expression2"找到一匹配值，然后在叶子节点从左到右进行检索，一直到不满足"indexed-field ≤ expression2" 的条件为止；或者反过来，首先通过第二个表达式进行检索，在叶子节点定位到该值后，再从右向左进行检索，一直到不满足第一个表达式的条件为止。
下图是23 ≤ n ≤ 64的查询示意图:
案例
下面是一个查询计划的实例。通过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索引。）
等值查询的执行计划：
1. demo=# explain(costs off) select * from aircrafts where range = 3000; 2. QUERY PLAN 3. --------------------------------------------------- 4. Index Scan using aircrafts_range_idx on aircrafts 5. Index Cond: (range = 3000) 6. (2 rows)
非等值查询的执行计划：
1. demo=# explain(costs off) select * from aircrafts where range < 3000; 2. QUERY PLAN 3. --------------------------------------------------- 4. Index Scan using aircrafts_range_idx on aircrafts 5. Index Cond: (range < 3000) 6. (2 rows)
范围查询的执行计划：
1. demo=# explain(costs off) select * from aircrafts 2. where range between 3000 and 5000; 3. QUERY PLAN 4. ----------------------------------------------------- 5. Index Scan using aircrafts_range_idx on aircrafts 6. Index Cond: ((range >= 3000) AND (range <= 5000)) 7. (2 rows)
排序
再次强调，通过index、index-only或bitmap扫描，btree访问方法可以返回有序的数据。因此如果表的排序条件上有索引，优化器会考虑以下方式：表的索引扫描；表的顺序扫描然后对结果集进行排序。
排序顺序
当创建索引时可以明确指定排序顺序。如下所示，在range列上建立一个索引，并且排序顺序为降序：
demo=# create index on aircrafts(range desc);
本案例中，大值会出现在树的左边，小值出现在右边。为什么有这样的需求？这样做是为了多列索引。创建aircraft的一个视图，通过range分成3部分：
1. demo=# create view aircrafts_v as 2. select model, 3. case 4. when range < 4000 then 1 5. when range < 10000 then 2 6. else 3 7. end as class 8. from aircrafts; 9. 10. 11. demo=# select * from aircrafts_v; 12. model | class 13. ---------------------+------- 14. Boeing 777-300 | 3 15. Boeing 767-300 | 2 16. Sukhoi SuperJet-100 | 1 17. Airbus A320-200 | 2 18. Airbus A321-200 | 2 19. Airbus A319-100 | 2 20. Boeing 737-300 | 2 21. Cessna 208 Caravan | 1 22. Bombardier CRJ-200 | 1 23. (9 rows)
然后创建一个索引（使用下面表达式）：
1. demo=# create index on aircrafts( 2. (case when range < 4000 then 1 when range < 10000 then 2 else 3 end), 3. model);
现在，可以通过索引以升序的方式获取排序的数据：
1. demo=# select class, model from aircrafts_v order by class, model; 2. class | model 3. -------+--------------------- 4. 1 | Bombardier CRJ-200 5. 1 | Cessna 208 Caravan 6. 1 | Sukhoi SuperJet-100 7. 2 | Airbus A319-100 8. 2 | Airbus A320-200 9. 2 | Airbus A321-200 10. 2 | Boeing 737-300 11. 2 | Boeing 767-300 12. 3 | Boeing 777-300 13. (9 rows) 14. 15. 16. demo=# explain(costs off) 17. select class, model from aircrafts_v order by class, model; 18. QUERY PLAN 19. -------------------------------------------------------- 20. Index Scan using aircrafts_case_model_idx on aircrafts 21. (1 row)
同样，可以以降序的方式获取排序的数据：
1. demo=# select class, model from aircrafts_v order by class desc, model desc; 2. class | model 3. -------+--------------------- 4. 3 | Boeing 777-300 5. 2 | Boeing 767-300 6. 2 | Boeing 737-300 7. 2 | Airbus A321-200 8. 2 | Airbus A320-200 9. 2 | Airbus A319-100 10. 1 | Sukhoi SuperJet-100 11. 1 | Cessna 208 Caravan 12. 1 | Bombardier CRJ-200 13. (9 rows) 14. demo=# explain(costs off) 15. select class, model from aircrafts_v order by class desc, model desc; 16. QUERY PLAN 17. ----------------------------------------------------------------- 18. Index Scan BACKWARD using aircrafts_case_model_idx on aircrafts 19. (1 row)
然而，如果一列以升序一列以降序的方式获取排序的数据的话，就不能使用索引，只能单独排序：
1. demo=# explain(costs off) 2. select class, model from aircrafts_v order by class ASC, model DESC; 3. QUERY PLAN 4. ------------------------------------------------- 5. Sort 6. Sort Key: (CASE ... END), aircrafts.model DESC 7. -> Seq Scan on aircrafts 8. (3 rows)
（注意，最终执行计划会选择顺序扫描，忽略之前设置的enable_seqscan = off。因为这个设置并不会放弃表扫描，只是设置他的成本----查看costs on的执行计划）
若有使用索引，创建索引时指定排序的方向：
1. demo=# create index aircrafts_case_asc_model_desc_idx on aircrafts( 2. (case 3. when range < 4000 then 1 4. when range < 10000 then 2 5. else 3 6. end) ASC, 7. model DESC); 8. 9. 10. demo=# explain(costs off) 11. select class, model from aircrafts_v order by class ASC, model DESC; 12. QUERY PLAN 13. ----------------------------------------------------------------- 14. Index Scan using aircrafts_case_asc_model_desc_idx on aircrafts 15. (1 row)
