b-tree - 这个 B 树会是什么样子？

Question

B-tree 是 4 阶的，这意味着一个节点可以保存 4 个指针和 3 个键。

插入以下内容：AGIY

由于它们不能全部放在一个节点中，我知道该节点会分裂。所以我知道在插入这些东西后会有一个带有 2 个子节点的根节点，但我不知道它们会是什么样子。

Answer 1

A

A 已插入

AG

G 已插入

AGI

我被插入

  G
 / \
A   I

插入Y时节点已满，分成2个节点并向上传递中间，G

  G
 / \
A   IY

已插入 Y

Answer 2

这是操作的动画：

http://ysangkok.github.io/js-clrs-btree/btree.html#{"actions":[["initTree",{"keys":[]},2],["insert","A "],["插入","G"],["插入","I"],["插入","Y"]]}

“initTree”的第二个参数是顺序，但使用了另一个定义。此程序中的最大键数为 2*order-1。所以我将 order 设置为 2，它与您的示例相匹配。