PostgreSQL的B-tree索引用法详解

2024-02-28 13:28作者：下载吧

结构

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，通过遍历链表就可以获取一个有序的数据集。

下面是一个索引的简单例子，该索引存储的记录为整型并只有一个字段：

PostgreSQL的B-tree索引用法详解

该索引最顶层的页是元数据页，该数据页存储索引root页的相关信息。内部节点位于root下面，叶子页位于最下面一层。向下的箭头表示由叶子节点指向表记录（TIDs）。

等值查询

例如通过”indexed-field = expression”形式的条件查询49这个值。

PostgreSQL的B-tree索引用法详解

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的示意图：

PostgreSQL的B-tree索引用法详解

大于和小于可以通过同样的方法进行查询。查询时需要排除等值查询出的值。

范围查询

范围查询”expression1 ≤ indexed-field ≤ expression2″时，需要通过 “expression1 ≤ indexed-field =expression2″找到一匹配值，然后在叶子节点从左到右进行检索，一直到不满足”indexed-field ≤ expression2” 的条件为止；或者反过来，首先通过第二个表达式进行检索，在叶子节点定位到该值后，再从右向左进行检索，一直到不满足第一个表达式的条件为止。

下图是23 ≤ n ≤ 64的查询示意图:

PostgreSQL的B-tree索引用法详解

案例

下面是一个查询计划的实例。通过demo database中的aircraft表进行介绍。该表有9行数据，由于整个表只有一个数据页，所以执行计划不会使用索引。为了解释说明问题，我们使用整个表进行说明。