性能优化：认识B*Tree 索引分裂（二）

黄玮（Fuyuncat）

黄玮（Fuyuncat），资深 Oracle DBA，从事Oracle数据库管理、维护与开发工作十余年，有丰富的大型数据库设计、开发与维护方面的经验，涉及航空、水利、军工、电信等多个行业。曾供职于某世界著名物流公司，负责公司的电子物流系统的数据库开发和维护工作。2005年创建了个人网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 ---