分支节点的创建

最终,当向表添加行时,数据库服务器用指向所有现有叶节点的节点指针填充根节点。当数据库服务器分割另一个叶节点,而根节点没有空间用于额外的节点指针时,那么发生以下过程。

数据库服务器分割根节点并将其内容分到两个新创建的分支节点上。随着索引项的添加,越来越多的叶节点被分割,这导致数据服务器添加更多的分支节点。最终,根节点充满了指向这些分支节点的指针。当发生这种情况时,数据库服务器重新分割根节点。然后,数据库服务器在根节点和较低的分支级别之间创建另一个分支级别。该过程导致 4 个级别的树,它带有一个根节点、两个分支级别和一个叶级别。B-tree 结构可以这种方式继续增长到最大 20 级。

分支节点可以指向其下面的其他分支节点(对于四级或更多的大索引来说)或指向叶节点。在 图 1 图中,分支节点只指向叶节点。左分支节点中的第一项包含与最左的叶节点中的最大项相同的键值以及指向它的指针。第二项包含下一叶节点中的最大项和一个指向它的节点指针。分支节点中的第三项只包含指向下一个更高叶节点的指针。根据索引的增长,在索引生命周期中的以后某个时点,除了指针之外,此第三项可能还包含实际键值。

图: 分支节点的典型内容


Begin figure description - The figure shows a branch node, labeled Branch node 2, and three leaf nodes labeled Leaf nodes 3, 4, and 5. The Branch node and each of the leaf nodes contain index items listed in two-column tables. Pointers extend from each of the branch node's index items to Leaf nodes 3, 4, and 5, respectively. End figure description