B*Tree 索引中的数据块分裂——树的生长
[English]
作者：
fuyuncat
来源：
www.HelloDBA.com
分享到
当分裂导致B树索引的层数（Btree Level）增加时，我们称之为树的“生长”。当叶子节点分裂时，在其父节点上需要增加一条记录指向新节点，如果此时父节点上没有足够空间，则父节点也会发生分裂，如果如此递归下去，直到根节点也分裂，那么索引的高度就增加了。
下图为一次9-1分裂导致的树的增长：
上面的分裂过程中，节点Root、B5、B3和L4在数据插入前都已经饱和，当数据插入时，导致这4个节点发生连锁的分裂，最终root的分裂会分配两个新枝节点，分别为其左右枝节点，由于L4、B3、B5都是发生9-1分裂，在新分裂的数据块上没有被转移老数据，它们都被放到了新生的右枝上了。
在每一个枝节点中，都有且只有一个左指针指向其下一层的左节点。这个指针很特殊，它存储于枝节点的头部而非数据区，其节点的键值是枝节点中唯一小于枝节点的键值数据、且不被存储。枝节点中其它的所有指针我们都称为右指针（即其节点键值大于等于枝节点的键值，且都有相应记录存储）。在节点分裂过程中，始终会保证每一个枝节点的左节点都有数据。
由于左节点的特殊性，仅仅按照之前的分裂条件，当向左枝节点左侧插入数据时，即使其兄弟右枝节点数据区中没有数据（即只有左节点、没有右节点），它们的父节点都会分裂，在特殊情况下（所有左枝节点都饱和，但右枝节点下没有数据），索引高度会增加，但底层枝节点下很空，叶子节点很少。甚至于特殊情况下（索引数据块为2K、键值数据长度大于1K），叶子节点数可以等于索引高度。这一算法缺陷在9i及之前版本都存在，如下图所示：
分裂前，所有左枝节点、叶子节点都已经饱和，左分裂造成连锁分裂，促成树的增长。如果键值为特殊数据、数据块为2K的话，此次分裂后，所有左节点仍然保持饱和状态——意味下一次的左插入会继续导致树的增长。
在10g中，这个缺陷被修正了：当左枝节点已经饱和时，会先检查其兄弟右枝节点是否为空，如果为空，则将左枝节点的部分数据（5-5）转移到右枝节点，从而避免左枝节点的分裂，如下图所示：
这一算法的修正避免了左分裂造成树的迅速增长。
--- Fuyuncat TBC ---
