性能优化：认识B树索引分裂

黄玮（Fuyuncat）

黄玮（Fuyuncat），资深 Oracle DBA，从事Oracle数据库管理、维护与开发工作十余年，有丰富的大型数据库设计、开发与维护方面的经验，涉及航空、水利、军工、电信等多个行业。曾供职于某世界著名物流公司，负责公司的电子物流系统的数据库开发和维护工作。2005年创建了个人网 www.HelloDBA.com，致力于数据库底层技术的研究，整理和发布了大量关于数据库系统底层机制、存储结构、性能调优以及基础算法方面的文章，获得广大同行的高度评价。

编辑手记：知己知彼，百战不殆。最强大的敌人无知。在数据库运维中，索引分裂是很常见的问题，这一期我们就跟随作者的脚步去认识索引分裂，为以后的索引维护打好基础。

如何分裂

当一个事务需要修改（大多数情况是Insert操作，某些情况下也可能为 Delete 操作）索引块（枝节点或叶子节点）上的数据，但没有足够空间容纳新的数据（包括索引条目、ITL slot）时，会将原有块上的部分数据放到一个新的数据块上去，这一过程就是索引块分裂（Index Block Splitting）。

按照分裂的对象不同，分为叶子节点分裂和枝节点分裂，而枝节点分裂中还有一个特殊的分裂：根节点分裂。

按照分裂时，2个数据块上分布的数据比例，分为5-5分裂和9-1分裂：

§ 5-5分裂：新旧2个数据块上的数据基本相等；

§ 9-1分裂：大部分数据还在原有数据块上，只有少量数据被转移到新的数据块上。

1) 叶子节点分裂

当 Insert、Update（实际上就是 Delete+Insert）时，叶子节点块上没有足够空间容纳新的索引条目，就会发生叶子节点分裂：

在10224事件的 trace 文件中可以看到叶子节点块分裂的记录：

同时，将 Btree 结构 dump 出来，也可以看到节点被分裂：

2、当事务需要修改节点上的数据，叶子节点上没有足够空间容纳新的 ITL slot 时，也会发生分裂。

我们 dump 出一个“满”的节点，注意到它上面的空闲空间只有20字节，小于一条 ITL slot的大小（24字节）

并且此时它里面有一条空闲 ITL slot（第一条ITL slot是用于递归事务的，后面会有解释），先用一个事务占用它：

然后再启动一个事务，造成了空间不足分配新的 ITL slot，而导致节点分裂：

在10224 trace文件中记录此次分裂：

枝节点分裂

枝节点的下一层的节点分裂，会导致在枝节点上增加一条记录指向新增加的节点，当此时枝节点上空间不足时，会导致枝节点分裂。 这种情况很容易被重现，我们这就不放 demo 代码了，下面是 trace 文件中记录的枝节点分裂：

要注意的是，枝节点中存储的数据是比较特殊的，因而数据的分布会直接影响到枝节点的多少以及其分裂的频率。

在枝节点中，每条记录指向了下一层一个节点上的最小值，但其并不一定完整的存储了索引字段上的数据：

对于单个字段，如果字段的前面一部分数据就可以定位到下一层的节点块，则枝节点中只存储这一部分数据；例如，字段A的索引节点的第一个叶子节点上的字段数据是 AAA11111, AAA22222, .... AAA55555；第二个节点上的字段数据是 AAA66666,....AAA99999，那么，在枝节点上分别存储的数据是 AAA1 和 AAA6

对于复合字段索引，如果前面字段已经可以定位到下一层的节点块，则枝节点中只存储这些字段，而不存储后面的字段值。例如，在字段(A, B)上建立了索引，A的值是自增长的，所以通过A就可以定位到下一层的节点，在枝节点上就只存储了A的数据:

我们将一个枝节点 dump 出来，可以看到B字段的数据没有被记录：

正因为枝节点的这种的索引值的存储方式，在下面例子中，字段在索引中的顺序不同直接导致了索引的高度不同：

可以看到，idx_split_idx1和idx_split_idx2 中的字段是一样的，因此它们的叶子节点数也是一样的，但是因为它们的数据分布性不同以及在索引中的位置不相同，导致它们的枝节点的数量和索引高度有很大的差别。同时，通过 10224 事件的 trace 文件也可以看到，发生在 idx_split_idx2 上的枝节点分裂次数远远多余在 idx_split_idx1上发生的次数。

根节点分裂——特殊的枝节点分裂

在所有枝节点中，有一个特殊的枝节点（或许你可以将它作为一种单独的节点类别），那就是根节点。根节点上的数据已经导致根节点分裂的条件基本上和普通枝节点相同，但是，唯一不同的是，普通枝节点或叶子节点在分裂时，只分配一个新的数据块，然后将被分裂的数据块上的部分数据转移到新的数据块上去，而根节点的分裂是需要分配2个新的数据块，将原有数据分别转移到2个新的数据块上去，在原有节点上生成2条记录分别指向这2个新的数据块。下面的Trace记录的就是根节点的分裂，可以看到它获取了2个新的数据块：

9-1分裂

当事务向索引中最后一个叶子节点数据块上插入一条大于或等于（ROWID 大于最大值的ROWID）数据块上最大值的数据，且该数据块上不存在其它未提交事务时，此时如果没有足够空间，就会发生9-1分裂：即分裂时，绝大部分数据保留在原有节点数据块上，仅少量数据被转移到新数据块上。

注意：当向索引中插入大于、等于最大值的数据时，PCTFREE 会被忽略（我们在后面会介绍索引中 PCTFREE 和 INITRANS 的影响）

注意2：如果叶子节点分裂导致枝节点也分裂，枝节点的分裂比例和叶子节点的分裂比例是相同的。

下面例子中，枝节点和叶子节点都发生了9-1分裂：

注意，这里的统计结果中，枝节点的分裂方式并未显示，但从 Trace 文件中可以看到，新分裂的节点数据块上只有少量数据，发生的是9-1分裂：

5-5分裂

有3种情况会导致5-5分裂：

1. 当新插入的数据小于索引中的最大值时，此时数据块空间不足容纳新的键值；
2. 当插入、删除数据时，数据块上没有足够空间分配新的ITL slot；
3. 当新插入的数据大于或等于索引中最大值时，此时数据块上还存在其它未提交的事务。

第一种情况很常见，这里不举例了。第二种情况可以参见之前的例子。下面代码是第三种情况的例子代码：

可以看到该分裂为5-5分裂，从索引树结构上也可以看出：

实际上，无论是9-1分裂还是5-5分裂，其目的都是为了减少分裂，因为节点分裂是一个代价高昂的操作：

• 当发生9-1分裂时，通常是索引的键值是递增的，且表上的主要操作为插入操作、事务并发量比较低的情况。保证新的数据块上有最大的空闲空间插入新值，因而减少了分裂的发生；
• 发生5-5分裂时，通常表上的并发事务较多，且插入、删除的数据比较分散，因此需要保持分裂的新、老数据块上有相当的空闲空间以容纳新事务、新数据。

--- Fuyuncat TBC ---