非叶子节点"记录"包含
- 指向树中下一级节点的指针(各种节点"地址")
- 该节点中第一个(或最后一个,取决于实现)记录的键的值
这种非叶子"记录"按密钥顺序列出,以便通过扫描(或在其中进行二进制搜索)非叶节点,可以知道下一级中的哪个节点可以包含搜索到的值.
叶节点记录包含完整的数据记录:键值和其他任何内容.
因此,"真实"数据仅包含在叶节点中,非叶节点仅包含[密钥值的副本].对于一小部分数据 (此比例取决于叶节点中创建的平均数据记录数).
维基百科关于B + Trees的文章中的图片说明了这一点
顶部的非叶节点(这个简化树中唯一的一个)只包含两个非叶节点记录,每个记录都有一个键值(蓝色)的副本和指向相应节点的指针(灰色) ).该树恰好只有两个级别,因此根节点中的"记录"指向叶节点.可以想象还有其他级别(在下面显示的最顶层树之上,称之为"3-5节点"); 如果是这种情况,上面的节点将包含(以及其他类似的记录),键值为3的记录带有指向"3-5"节点的指针.
还要注意,只有键值3和5包含在非叶节点中(即,甚至不在非叶节点中再现所有键值).
在这个例子中,非叶子节点包含下一个节点中最后一个记录的密钥(如果使用第一个记录,则也可以工作,然后在搜索逻辑的实现方式上略有不同).
叶节点包含键值(蓝色)和相应的数据记录(d1,d2 ......以灰色显示).在每个叶节点的末尾显示的红色指针指向下一个叶节点,即按键顺序包含下一个数据记录的叶节点; 这些指针对于"扫描"一系列数据记录很有用.