B+树或B树

Question

我正在学习postgresql内部程序，我想知道postgresql树索引实际上是经典的B树还是B+tree？要拼出来，这意味着节点只包含键或键值对？

Answer 1

我说的是B树，首先，但它可以说更接近B+树。

请参阅iwis的回答更深入地讨论它。

您必须同时考虑索引+堆(+辅助存储)。一个索引本身基本上是无用的。

这是一个维基百科相关章节。

相关索引方法的名称是Postgres中的“B树”。物理存储与表(堆)或任何其他索引类型的存储非常相似。所有的数据页都使用相同的页面布局。手册里有更多。

发展正在进行中。自从提出这个问题以来，设计在许多方面都发生了变化(改进)。最新的显著变化(截至2021年4月)是去叠在Postgres 13。

Answer 2

在我看来，PostgreSQL使用的是B+树。

B树与B+树的区别

• 在B树中，索引表中记录的指针不仅在树的叶子中，而且在树的所有内部节点中。
• 在B+树中，指向索引表中记录的指针仅在树的叶子中。阐述了B+树相对于B树的优点.

​

(图片是对这幅画的修改)

数据库管理系统中B+树的使用

Oracle，Server，SQLite，DB2和MySQL使用B+树。似乎PostgreSQL也使用了B+树，因为：

• 文档似乎指出，只有树的叶子才有指向索引表中记录的指针： 每个叶页都包含指向表行的元组。每个内部页面都包含指向树中下一层的元组。
• 当Bruce关于内部节点的他说时，他没有提到它们有指向索引表中记录的指针。
• 文档中提到的PostgreSQL源代码的src/backend/access/nbtree/自述文件包含以下注释： Btree索引 该目录包含了雷曼和姚的高并发B树管理算法的正确实现(P. Lehman和S. Yao，B-树上并发操作的高效锁定，ACM Transaction on Database Systems，第6卷，第4期，1981年12月，pp 650-670)。

雷曼和姚使用了一个名为B* tree的树结构，在数据库系统中访问路径的选择论文中，Wedekind将它定义为B-树，其中非叶节点没有指向索引表中记录的指针(它们只有指向子节点的指针)。因此，Wede申德定义的B*树结构是一个B+树。