B+Tree分裂导致叶节点容量变小

Question

我目前正在尝试理解和重新创建一个数据库。在数据库中存储数据的一种常见方法是使用B+Tree。数据仅存储在所谓的“叶节点”上，而“叶节点”是由“索引节点”索引的。如果一个完整的叶节点被插入，它将被分割，其内容被平分到两个新节点。我知道这恰好保持了树的平衡和易于搜索。但我不太明白这个程序。

这个例子取自这个线程'splitting a node in b+ tree‘。

假设我们有这样一个B+Tree：

            [21             30           50]
           /   \              \            \
   [10|20|-] => [21|22|25] => [30|40|-] => [50|60|80]

然后插入键'23‘。我们需要分裂21\22\25节点。为了平衡这棵树，我们均匀地分配钥匙，然后到达这棵树：

            [21                             30           50]
           /   \                              \            \
   [10|20|-] => [21|22|-] => [23|25|-] => [30|40|-] => [50|60|80]

                                        ||
                                        ||
                                        \/


                               [       30        ]
                              /                   \
            [21            23]                     [50]
           /   \             \                    /    \
   [10|20|-] => [21|22|-] => [23|25|-] => [30|40|-] => [50|60|80]

在我对B+Trees的理解中，这将使21\22-叶子无法被填充到最大容量。这是因为任何小于21的键都将被输入到10\20\x-叶中，而23已经是一个当前密钥。

如果我们认为叶子节点是存在于数据库中的页面，这就浪费了宝贵的内存和磁盘空间，需要更多的磁盘操作来查找值，从而使数据库变得更慢。

我非常感谢对我的想法的反馈和一些帮助清理误解，如果他们在场。

非常感谢!

Answer 1

这就是所谓的b-树“填充因子”。当按随机顺序插入时，填充因子为70%是在实践中可以实现的最佳方法。当插入顺序，它下降到50%，正如你已经观察到的。B*树分裂算法在分割前进行再平衡，在按顺序插入条目时达到66%的填充因子。

使用一些技术，B树设计可以更好地提高填充因子。一种方法是检测顺序插入和分裂叶片不平衡.新的左节点保留了大部分原始条目，但是新的右节点开始时大部分是空的。该技术还需要检测反向插入顺序，以防止创建一个深渊填充因子。

通过各种技术的结合，顺序插入的填充因子可以达到100%，随机插入顺序的填充因子可以达到80%。要达到80%以上，需要更复杂的再平衡步骤，这可能会导致实际成本过高。