6.BTREE索引详解-01.docx

9页

0次

2024-06-15

25墨值下载

Btree 索引介绍

BTree：最常用的索引， BTree 索引适合用于处理等值查询和范围查询。 PostgreSQL 的查

询规划器会在使用以下运算符时考虑使用 B-tree 索引：<、<=、=、>=、>、

BETWEEN、IN、IS NULL、IS NOT NULL。

另外，查询规划器在涉及模式匹配运算符 LIKE、~、ILIKE、~*的查询时考虑使用 B-tree 索

引。

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

•B 树是平衡的，也就是说，每个叶子节点与根节点都由相同数量的中间节点分隔开。因此，

搜索任何值都需要花费相同的时间。

• B 树是多分支的，即每个页面（通常为 8 KB）包含许多（数百个）ctid。因此，B 树的深度

很小，对于非常大的表，实际上可以达到 4–5 的深度。当字段超过单个索引页的 1/3 时，不适

合 b-tree 索引。

索引中的数据按非递减顺序排序（在页面之间和每个页面内部），并且同一级别的页面通过•

双向列表相互连接。

因此，可以仅通过列表的一个方向或另一个方向获得有序数据集，而不必每次都返回到根。

索引结构

下面是带整数键的一个字段上的索引的简化示例：

等值搜索

通过条件“索引字段=表达式 ” 在树中搜索值。假设对 49 的键感兴趣。

搜索从根节点开始，然后需要确定要降到哪个中间节点。由于知道根节点（4、32、64）中的

键，因此可以计算出中间节点的值范围。由于 32 < 49 < 64，所以需要下降到第二个中间节点。

接下来，递归重复相同的过程，直到到达叶子节点，可以从该叶叶子节点获得所需的 TID。

如果一个索引包含非唯一值，并且可能有多个相等的值以至于它们没法存放在一页。因此，一

旦在内部页面中找到一个完全相等的值，就必须向左移一个位置，然后从左到右查看底层的索

引行以寻找所需的键。

不等搜索

当通过条件“索引字段 <= 表达式 ”（或"索引字段 >= 表达式 “）进行搜索时，首先通过等式条

件"索引字段=表达式" 在索引中找到一个值（如果有的话），然后按照适当的方向遍历叶子节

点直到结束。该图说明了 n <= 35 的过程：

of 9

25墨值下载

关注