B +树或B树
Bor*_*rys 5 postgresql indexing b-tree
我正在学习postgresql内部和我想知道或postgresql B树索引实际上是经典的B树或B +树？要拼写出来,这意味着节点只包含键或键值对？
iwi*_*wis 11
在我看来，PostgreSQL 使用的是 B+ 树。
B树和B+树的区别
- 在B树中，指向索引表中记录的指针不仅位于树的叶子中，而且位于树的所有内部节点中。
- 在 B+ 树中，指向索引表中记录的指针仅位于树的叶子中。这里描述了B+树相对于B-树的优点。
（该图是这张图
的修改版）
B+树在DBMS中的使用
Oracle、SQL Server、SQLite、DB2和MySQL使用 B+ 树。PostgreSQL 似乎也使用 B+ 树，因为：
文档似乎指出，只有树的叶子具有指向索引表中记录的指针：
每个叶页包含指向表行的元组。每个内部页面都包含指向树中下一个级别的元组。
当 Bruce Momjian谈到内部节点时，他没有提到它们有指向索引表中记录的指针。
文档中提到的 PostgreSQL 源代码的 src/backend/access/nbtree/README 文件包含以下注释：
B树索引
该目录包含 Lehman 和 Yao 的高并发 B 树管理算法的正确实现（P. Lehman 和 S. Yao，Efficient Locking for Concurrent Operations on B-Trees，ACM Transactions on Database Systems，第 6 卷，第 4 期， 1981 年 12 月，第 650-670 页）。
Lehman 和 Yao 使用名为B* 树的树结构，该结构由 Wedekind 在On the Selection of Access Paths in a Database System论文中定义为 B 树，其中非叶节点没有指向索引表中记录的指针（它们仅具有指向其子节点的指针）。所以Wedekind定义的B*树结构是B+树。
B树.只有钥匙.索引的关键是存储键开头.数据位于表中,这些表是逻辑堆.这是维基百科的相关章节.
B树索引和表的物理存储在其他方面非常相似.它们使用相同的数据页面,大多数页面布局相同.更多内容在手册中.
- 关于"数据"的讨论令人困惑,并不重要.理解这种区别的最好方法是,在一个朴素的b +树中,内部节点中的键将在叶子中重复,而在b树中,如果键存储在内部节点中,它也不会被存储在一片叶子里.绝对是这样的情况,b +树通常被用作"数据"部分是对完整记录的引用的指示.b +树的一大优势就在于,因为所有内容都存储在叶子中,所以可以将叶子放入链表中,并且可以非常快速地迭代范围查询. (5认同)
- b +树将数据存储在叶子中.b和b +树之间的区别对于索引开始没有多大意义.如果愿意,索引和表一起形成b +树的特殊形式.索引本身只是一个b树. (4认同)
- 但如果 db 只存储键，它会是 B+？ (2认同)