可视化Postgres B-Tree索引的小工具

可以使用此工具可视化您的索引的内部结构。点击标题
它需要 python3.6.*。您还必须安装 pageinspect ( https://www.postgresql.org/docs/10/static/pageinspect.html ) 扩展。如果您想将此工具用于 GiST 索引，则必须安装 gevel ( http://www.sai.msu.su/~megera/wiki/Gevel ) postgres 扩展。

什么是 B 树？
BTree 代表平衡树，在平衡树中，所有叶子与根的距离相等。此外，根节点和父节点可以有两个以上的子节点，从而最小化树的深度。

postgres 中的 B 树
Postgres 实现了 Lehman & Yao Btree，它具有您将在本文中发现的一些特殊性，或者如果您真的喜欢它，请阅读他们的研究论文。

假设：

SELECT email FROM crocodile WHERE number_of_teeth < 18;

为此，我们决定创建以下索引：

CREATE INDEX ON crocodile (number_of_teeth);

元页
为这个索引生成了pageinspect_inspector，这里是第一个屏幕截图：

在这里我们看到了索引和根的元页metapage。元页始终是 posgres 索引的第一页。它包含了：

指向根的指针可以改变。
在插入之后，可能有必要将当前根拆分为两个页，在这种情况下，将创建一个新的根，并在拆分页上使用指针：

根、父和叶都是具有相同结构的页，页有：

下一页和上一页的指针
由于下一页和上一页的指针，同一层次的页是一个链接列表。这是Yao和Lehmann BTree的一个特点。例如，它在ORDER BY查询的叶子中是非常有用的。下面是第0层（叶）的页:

如果我们想运行查询

SELECT email FROM crocodile ORDER BY number_of_teeth ASC

Postgres会从第一页开始，由于有了下一页的指针，直接将所有的行按正确的顺序排列。

关于high key
high key也是雷曼和姚氏BT树所特有的。页中的任何项目都会有一个低于或等于high key的值。

总结