【IT168 技术文档】什么是B-tree索引块分裂

　　当一个事务需要修改(大多数情况是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，而导致节点分裂：

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

　　枝节点分裂

　　枝节点的下一层的节点分裂，会导致在枝节点上增加一条记录指向新增加的节点，当此时枝节点上空间不足时，会导致枝节点分裂。

　　这种情况很容易被重现，我们这就不放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分裂：

　　当新插入的数据小于索引中的最大值时，此时数据块空间不足容纳新的键值;

　　当插入、删除数据时，数据块上没有足够空间分配新的ITL slot;

　　当新插入的数据大于或等于索引中最大值时，此时数据块上还存在其它未提交的事务。

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

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

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

　　当发生9-1分裂时，通常是索引的键值是递增的，且表上的主要操作为插入操作、事务并发量比较低的情况。保证新的数据块上有最大的空闲空间插入新值，因而减少了分裂的发生;

　　发生5-5分裂时，通常表上的并发事务较多，且插入、删除的数据比较分散，因此需要保持分裂的新、老数据块上有相当的空闲空间以容纳新事务、新数据。

　　树的生长

　　当分裂导致B树索引的层数(Btree Level)增加时，我们称之为树的“生长”。当叶子节点分裂时，在其父节点上需要增加一条记录指向新节点，如果此时父节点上没有足够空间，则父节点也会发生分裂，如果如此递归下去，直到根节点也分裂，那么索引的高度就增加了。

　　下图为一次9-1分裂导致的树的增长：

　　上面的分裂过程中，节点Root、B5、B3和L4在数据插入前都已经饱和，当数据插入时，导致这4个节点发生连锁的分裂，最终root的分裂会分配两个新枝节点，分别为其左右枝节点，由于L4、B3、B5都是发生9-1分裂，在新分裂的数据块上没有被转移老数据，它们都被放到了新生的右枝上了。

　　在每一个枝节点中，都有且只有一个左指针指向其下一层的左节点。这个指针很特殊，它存储于枝节点的头部而非数据区，其节点的键值是枝节点中唯一小于枝节点的键值数据、且不被存储。枝节点中其它的所有指针我们都称为右指针(即其节点键值大于等于枝节点的键值，且都有相应记录存储)。在节点分裂过程中，始终会保证每一个枝节点的左节点都有数据。

　　由于左节点的特殊性，仅仅按照之前的分裂条件，当向左枝节点左侧插入数据时，即使其兄弟右枝节点数据区中没有数据(即只有左节点、没有右节点)，它们的父节点都会分裂，在特殊情况下(所有左枝节点都饱和，但右枝节点下没有数据)，索引高度会增加，但底层枝节点下很空，叶子节点很少。甚至于特殊情况下(索引数据块为2K、键值数据长度大于1K)，叶子节点数可以等于索引高度。这一算法缺陷在9i及之前版本都存在，如下图所示：

　　分裂前，所有左枝节点、叶子节点都已经饱和，左分裂造成连锁分裂，促成树的增长。如果键值为特殊数据、数据块为2K的话，此次分裂后，所有左节点仍然保持饱和状态——意味下一次的左插入会继续导致树的增长。

　　在10g中，这个缺陷被修正了：当左枝节点已经饱和时，会先检查其兄弟右枝节点是否为空，如果为空，则将左枝节点的部分数据(5-5)转移到右枝节点，从而避免左枝节点的分裂，如下图所示：

　　这一算法的修正避免了左分裂造成树的迅速增长。

　　我们知道，在表的数据块中，当数据插入时，要保证数据块上剩余空间大于、等于PCTFREE的比例设置，以用于数据更新和多事务处理，从而减少数据迁移(Row Migration)的发生;而当分配新的数据块时，会根据INITRANS的设置预留相应的ITL slot，保证并发事务能分配到ITL slot。

　　在索引中，这两个参数仅在有数据时创建或重建索引才会起作用，且仅在叶子节点上起作用。

　　INITRANS

　　INITRANS在索引数据块上是否起作用，是由索引在创建或重建时是否有数据(即是否会分配数据块)决定的。比较以下代码，第一段代码在truncate之后rebuild(即不会分配索引数据块)，因而ITL slot数量为默认值2;第二段代码在有数据时rebuild，然后再truncate，此时再插入数据产生的新的索引块上ITL slot数量就受到INITRANS的控制：

　　需要注意的是，当数据块上ITL Slot数量大于起作用的INITRANS时，在分裂时被“继承”。在以下例子中，在rebuild时，指定了INITRANS为3：

　　我们同时启动4个事务作用在最后一个节点，导致该数据块上分配5个(加一个递归事务ITL slot)ITL slot：

　　然后将它们全部提交或回滚，再插入数据，造成分裂：

　　Dump出分裂的数据块，可以看到所有数据块都被分配了5个ITL slot，而不是INITRANS(3)的数量：

　　PCTFREE

　　PCTFREE在分裂时则被忽略。在上述例子中，我们找到一块发生9-1分裂产生的数据块，可以看到其空闲空间为44b，空闲率为44/2048=2.1%，远远小于我们rebuild时的设定值(60)。

　　我们再插入一些中间数据，造成5-5分裂：　

　　可以看到，发生分裂的数据块的空闲率为556/2048=27.1%，可见PCTFREE(60)也被忽略了。

　　索引分裂是导致分裂的用户事务中调用的递归事务控制，其对资源的请求和释放都是在该递归事务中完成的。

　　在任何一块枝节点数据块上，有且只有一个ITL slot，这个ITL slot不是被用于用户事务(User Transaction)的，而是被用于发生分裂时的递归事务的。同样，在叶子节点上，第一ITL slot，也是用于此目的:

　　我们将叶子节点和枝节点Dump出来，可以看到叶子节点的第一条ITL slot和枝节点的ITL slot不同于用户事务(叶子节点上第二条)的ITL slot：

　　注意：也许你注意到了上述例子中，最后2个叶子节点的递归事务ITL与枝节点的递归事务ITL相同。实际上，这就是在分裂时被“继承”下来的，而最后一个叶子节点因为还没有发生分裂，实际上也没有产生新的递归事务。

　　当索引数据块需要分裂时，会从Freelist中找到空闲的数据块满足分配需要，在10224的跟踪文件中，可以看到以下信息记录了新数据块的分配：

　　如果索引数据块上的数据被全部删除，该数据块就会被放置在freelist的前面，但并不从B树结构上删除:

　　从跟踪文件可以看到：当数据块中的实际记录数(rrow)为0时，被放到了freelist，但是并未从树结构中拿走。

　　在下一次数据块分裂时，从freelist上获取到该数据块，然后将其从树结构中删除，重新分配到树结构中：

　　跟踪文件显示了这一数据块被回收利用的过程：

　　需要注意的是，数据块被放入freelist的条件是该数据块上的实际记录数(rrow)为0，而不是等待删除这些数据的事务提交：

　　事务未提交，但从跟踪文件可以看到数据块已经被放到freelist上去了：

　　如果此时发生分裂，因为该数据块在freelist的前列，因此仍然会被获取到，但是，由于其上面的事务并未提交，所以不会被分配：　

　　下一次分裂时，由于其还在freelist，但事务仍未提交，会再次发生这一过程——这就导致了IO的增加：　

　　第二种需要注意的情况是，当删除的空数据块被放置到freelist后(事务也已提交)，此时它仍然在树结构中，此时如果有正好属于该数据块在树中位置的数据被插入，数据仍然会被写入该数据块上，但并不从freelist上移走：

　　此时如果发生分裂，该数据块仍然会被获得，但是分配失败，此时，它才会被从freelist上移走：

　　尽管索引分裂是由递归事务控制的，其资源的请求与释放都很短暂，不受用户事务是否结束的影响，但是，在并发环境中，索引分裂仍然会导致一些等待事件。

　　enq: TX - Index contention

　　首先一个与索引分裂直接相关的等待事件，也是仅仅因为索引分裂才会导致的等待事件是"enq: TX - Index contention"。这一等待是一种TX队列等待，在10g之前，被笼统的归入TX队列等待中，10g之后，才有了更细致的划分。

　　当一个更新事务需要插入/删除某个索引块上的数据，而这个数据块正在被另外一个事务分裂，则需要等待分裂完成后才能修改上面的数据，此时就会发生“enq: TX - Index contention”等待事件：

　　可以看到，第二个会话中出现了"enq: TX - Index contention"等待：

       enq: TX - allocate ITL entry

　　这一等待也是属于TX队列等待。

　　在索引数据块上，有2种情形会导致发生“enq: TX - allocate ITL entry”等待：1、达到数据块上最大事务数限制;2、递归事务ITL争用。很显然，第二种情形是由索引分裂引起的：当一个事务中递归事务请求分裂一个数据块时，该数据块正在被另外一个事务的递归事务分裂，就发生“enq: TX - allocate ITL entry”等待。我们前面提过，无论在叶子节点数据块上还是在枝节点数据块上，有且只有一个ITL slot(枝节点上的唯一ITL slot，叶子节点上的第一条ITL slot)是用于递归事务的，当2个递归事务同时要请求该ITL slot，后发出请求的事务就需要等待：

　　可以看到两个会话中都发生了“enq: TX - allocate ITL entry”等待：

　　db file sequential read

　　“db file sequential read”是因为Oracle从磁盘上读取单个数据块到内存中发生的等待——索引的读取就是单个数据块的读取(Fast Full Index Scan除外)。

　　当发生索引块分裂，新数据块立即被加入索引树结构(和事务是否结束无关)，这些新数据块被放入LRU链表中，Touch Count为1——因此容易被从buffer中置换出。此时，如果发生对索引的读，这些新数据块也会被读取——如果此时它们已经不在内存中，则会导致“db file sequential read”等待的增加：

　　此时(在另外会话中)读取索引，发生db file sequential read等待

　　这种情况下db file sequential read等待和并发的索引块分裂是无关的——是因为分裂导致索引段的数据块增加。但下面这种情况，就和并发索引分裂相关。

　　前面提过，当数据块上当大量数据被删除，或者插入数据的事务被回滚，会在索引结构中留下大量空数据块被放入freelist，此时发生索引分裂，将可能会引起更多“db file sequential read”等待：当一个事务进行分裂时，从freelist的前列读取到空闲数据块——该数据块是由其它事务删除数据或者回滚而被放入freelist的，而如果此时该空闲数据块状态异常(删除事务未提交、或者有新的数据被重新插入该数据块)，则分裂事务需要再重新读取空闲数据块。比较下面2段代码：

　　1、索引构建好后，从buffer中置换出：

　　此时另外一个事务分裂索引会导致60的db file sequential read等待：

　　2、而如果事务将构建好的索引数据删除，相应数据块被放到freelist中去了，此时事务未提交，这些数据块的状态不适合作为分裂时的新数据块：

　　另外一个事务需要进行分裂时，会先读取到freelist上的数据——发现不能被作为新数据块，需重新读取空闲数据块，造成db file sequential read等待增加：

　　这种情况下，还会可能导致连锁等待：分裂事务会对被分裂数据块加共享锁，此时如果有其它事务需要向该数据块写入数据，那么这些事务就会进入等待队列，并记录"enq: TX - index contention"，直到分裂事务找到可用数据块、完成分裂。