数据库系统内幕

42

｜

第

2

章

是叶节点还是非叶节点（即，该节点是拥有键和值还是仅拥有键）被分裂并不重要。在

叶节点分裂的情况下，键连同其相关值一起被移动。

分裂完成后有两个节点，我们必须选择正确的节点才能完成插入。为此，我们可以使用

分隔键不变量。如果插入的键小于要提升的键，则最后插入到原分裂节点。否则，我们

将要插入的键放入新创建的节点。

总之，节点分裂分为四个步骤：

1.　分配一个新节点。

2.　将一半元素从分裂节点复制到新节点。

3.　将新元素放入相应节点。

4.　在分裂节点的父节点处，添加一个分隔键和指向新节点的指针。

2.3.7 B

树的节点合并

为了进行删除，首先要定位目标叶节点。当叶节点被定位后，键和与其相关的值就被删除。

如果相邻节点所拥有的值太少（即，其占用率低于阈值），则需要合并同一层的节点。这

种情况称为

下溢

（underflow）。 [BAYER72] 描述了两种下溢场景：如果两个相邻节点

具有公共父节点，并且它们的内容能够放入单个节点，则它们的内容应该合并（连接起

来）；如果它们的内容无法放入单个节点，则应在它们之间重新分配键以恢复平衡（参见

4.4 节）。更准确地说，如果满足以下条件，则合并两个节点：

•

对于叶节点：如果一个节点可以容纳最多 N 个键值对，并且两个相邻节点中的键值

对的数目加起来小于或等于 N。

•

对于非叶节点：如果一个节点可以容纳最多 N +1 个指针，并且两个相邻节点中指针

的数量加起来小于或等于 N+1。

图 2-13 展示了删除元素 16 时的合并过程。在这个过程中，我们将元素从一个兄弟节 ...