btrees和b+trees是否仅在叶节点存储数据？

Question

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

是这样吗?还是它们在每个节点上都存储数据？

Answer 1

非叶节点“记录”包含

• 指向树下的下一级节点的指针(排序的节点“地址”)
• 该节点

中第一个(或最后一个，取决于实现方式)记录的键值

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

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

因此“真正”的数据只包含在叶子节点中，非叶子节点中只包含一个键值的副本。对于非常小比例的数据(这个比例取决于一个叶子节点中创建的平均数据记录数)。

这在来自Wikipedia article on B+ Trees的下图中进行了说明

​

顶部的非叶子节点(这个简单树中唯一的一个)只包含两个非叶子节点记录，每个记录都有一个键值副本(蓝色)和一个指向相应节点的指针(灰色)。这棵树恰好只有两层，因此根节点中的“记录”指向叶节点。可以想象有额外的级别(在下面显示的最上面的树之上，称为"3-5节点“)；如果是这种情况，上面的节点将包含(以及其他类似的记录)，具有键值3的记录具有指向"3-5”节点的指针。

还要注意，只有键值3和5包含在非叶节点中(即，甚至不是所有的键值都在非叶节点中再现)。

顺便说一句，在这个例子中，非叶节点包含下一个节点中最后一个记录的关键字(如果使用第一个记录也会起作用，搜索逻辑的实现方式略有不同)。

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

Answer 2

所有数据都在树叶中。

Wiki on B+。

Answer 3

关于BTrees和B+Trees有一些混淆。B+Trees仅将数据作为指针存储在叶节点上。这意味着数据必须存储在其他地方。BTrees可以在每个节点上存储数据。每种方法都有其优点和缺点。我注意到有些站点显示的BTrees和B+Trees完全一样。通常，BTrees更善于保存实际数据，而B+Trees作为索引的效率要高得多。