B+树内部节点

Question

我正在翻阅一本教科书，却被困在了这个问题上：

考虑一棵B+树，其中每个叶块最多可以包含3个记录，每个内部块最多可以包含3个键，树中的所有记录块都完全被3条记录占用，记录具有键值: 5,10,15，.，文件中有4个记录块

问题：“在一个图表中绘制这棵树”

到目前为止，我已经将所有记录添加到叶级，有4个块，有3个键，总共12个值，所以我的叶级别的倍数从5到60不等。我现在被困在在上面的级别上添加什么(内部块)。

Answer 1

你已经为叶级做了正确的事情。只需要一个内部块，它将有4个指向这些叶块的指针和3个键。这3个键通常是来自该块下块中最小键的副本。在该内部块中不重复第一个块的键，只重复其他块的键。

说明这种结构的一种方法是这样：

​

​

通常，叶块是在一个单独或双链接列表中链接在一起的，尽管这并不是B+树的严格要求。我没有在上面描述过这一点。