theory - btree 和 b+tree 只在叶子节点存储数据吗？

Question

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

是这样的还是他们在每个节点都存储数据？

Answer 1

非叶​​子节点“记录”包含

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

此类非叶“记录”按关键顺序列出，以便通过扫描(或在其中进行二分查找)非叶节点，人们知道下一层中的哪个节点可能包含搜索值。

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

因此“真实”数据仅包含在叶节点中，非叶节点仅包含键值的[副本]。 对于很小比例的数据(该比例取决于叶节点中找到的数据记录的平均数量)。

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

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

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