theory - btrees 和 b+trees 是否只在叶子上存储数据？

Question

b 树和 b+ 树是否只在它们的叶子上存储数据？我假设他们使用内部节点来搜索所需的数据。

是这种情况还是他们在每个节点中都存储数据？

Answer 1

非叶节点“记录”包含

• 指向树下一层节点的指针（某种节点“地址”）
• 该节点中第一个（或最后一个，取决于实现）记录的键的值

这样的非叶“记录”按键顺序列出，以便通过扫描（或在其中进行二进制搜索）非叶节点，可以知道下一层中的哪个节点可能包含搜索到的值。

叶节点记录包含完整的数据记录：键值和其他任何内容。

因此“真实”数据仅包含在叶节点中，非叶节点仅包含键值的[副本]。对于很小比例的数据 （这个比例取决于在叶节点中发现的平均数据记录数）。

这在维基百科关于 B+ 树的文章中的下图中进行了说明

顶部的非叶节点（这棵简单树中的唯一一个）仅包含两个非叶节点记录，每个记录都有一个键值副本（蓝色）和一个指向相应节点的指针（灰色）。这棵树恰好只有两层，因此根节点中的“记录”指向叶节点。可以想象还有额外的层级（在下面显示的最顶层树之上，称之为“3-5 节点”）；如果是这种情况，上面的节点将包含（以及其他类似的记录），键值为 3 的记录和指向“3-5”节点的指针。
另请注意，只有键值 3 和 5 包含在非叶节点中（即，甚至不是所有键值都在非叶节点中复制）。
下一个节点中的最后一条记录（如果使用第一条记录也可以使用，然后实现搜索逻辑的方式略有不同）。

叶节点包含键值（也是蓝色）和相应的数据记录（d1、d2...以灰色显示）。显示在每个叶节点末尾的红色指针指向下一个叶节点，即包含键顺序的下一个数据记录的叶节点；这些指针对于“扫描”一系列数据记录很有用。

Answer 2

所有数据都在叶子中。

B+ 上的维基。

Answer 3

BTrees 和 B+Trees 存在一些混淆。B+Trees 仅将叶节点上的数据存储为指针。这意味着数据必须存储在其他地方。BTree 可以在每个节点上存储数据。每个都有优点和缺点。我注意到有些网站显示的 BTrees 与 B+Trees 完全相同。一般来说，BTrees 更擅长保存实际数据，而 B+Trees 作为索引效率更高。