1

对于 B+ 树插入，你为什么要遍历树然后向上分裂父母？

维基百科建议这种插入方法：

执行搜索以确定新记录应进入哪个存储桶。

  • 如果桶未满（插入后最多 b - 1 个条目），则添加记录。
  • 否则，拆分桶。
    • 分配新叶子并将桶的一半元素移动到新桶。
    • 将新叶子的最小键和地址插入父节点。
    • 如果父级已满，也将其拆分。
      • 将中间键添加到父节点。
    • 重复直到找到不需要拆分的父级。

如果根分裂，则创建一个具有一个键和两个指针的新根。

你为什么要遍历树然后返回执行拆分？为什么不在下行过程中遇到节点时拆分节点？

对我来说，所提出的方法执行了两倍的工作，并且还需要更多的簿记。

谁能解释为什么这是插入的首选方法，而不是向下拆分的方法，以及在遍历期间插入的缺点是什么？

4

1 回答 1

2

您必须回溯树，因为您实际上不知道是否需要在最低级别进行拆分，直到您到达那里。

这一切都在短语“如果桶未满，......”中。

您还应该意识到，它远没有两倍的工作量。由于您在向下的过程中记住了各种各样的东西（节点指针、节点内的索引等等），因此在返回的过程中没有那么多的计算或搜索。

于 2013-01-29T00:12:53.727 回答