《高并发Oracle数据库系统的架构与设计》一2.4　索引分裂

本节书摘来自华章出版社《高并发Oracle数据库系统的架构与设计》一书中的第2章，第2.4节，作者 侯松，更多章节内容可以访问云栖社区“华章计算机”公众号查看

2.4　索引分裂

通过前面三节的介绍，相信各位读者已经能对索引的设计及其影响因素有了一定的把握，接下来两节我们将进行到索引新建后的维护阶段。先想一想，索引为什么需要维护？因为它不能保证高效的查询和DML操作，甚至成了一种拖累，或者大家都很“喜欢”它，它有些不堪重负了。这些问题对我们来说都是不能置之不理的，否则宁可不建索引。
知其然必知其所以然，要想解决索引的问题，需要先知道这些问题是怎么产生的。我们知道B树索引的结构就像一棵树一样，这棵树随着业务数据的增加，也是会慢慢生长起来的，自然也有了其“成长的烦恼”。那这棵树是通过什么方式来生长的呢？这也是问题的关键，也是我们接下来要展开讨论的话题——索引分裂。
本节将深入剖析索引树分裂生长原理，各种分裂的形式，以及因此带来的问题和解决的方法。

2.4.1　分裂原理

1.?什么是分裂
在开始介绍之前，我们先来搞清楚什么是索引分裂吧。“索引分裂”就是索引块的分裂，当一次DML事务操作修改了索引块上的数据，但是旧有的索引块没有足够的空间来容纳新修改的数据，那么将分裂出一个新索引块，旧有块的部分数据放到新开辟的索引块上去，这个过程就称为索引块的分裂（INDEX BLOCK SPLIT）。
如图2-11所示，当有新值插入到L4叶节点块的时候，此时L4叶节点块是“充满”状态，已经没有足够的空间来存储新值了，此时会在B2分支节点下，分裂出一个新的叶节点L5来存储新值。如果分支节点B2也是“充满”了呢？那就要进行分支节点的分裂，即在ROOT根节点下，分裂出一个新的分支节点出来。依此类推，如果根节点也“充满”了，则需要进行根节点的分裂。如果发生了根节点的分裂，也意味着B树的高度（BTREE LEVEL）增加了一个层次。对真正意义上的树来说，这种生长是好事，但对B树索引来说，这就不是什么好事情了，B树索引的高度是需要严格控制的。

2.?分裂的类型
从上面的介绍来说，我们大致可以将索引分裂归为三种类型：根节点分裂、分支节点分裂、叶节点分裂。当然，也可以说是两种类型，因为根节点分裂实质上是一种特殊的分支节点分裂。我们首先需要关注的是其中叶节点的分裂，因为它是最频繁发生，对性能影响最直接的因素。
我们说过分裂出新节点后，会将一部分旧有的数据放到新节点上去。按照数据迁移量的比例，我们又可以将索引分裂分为两种类型：9-1分裂和5-5分裂。如果叶节点和分支节点同时发生分裂，其分裂比例的类型是相同的，即要么都是9-1分裂，要么都是5-5分裂。
9-1分裂：绝大部分数据还保留在旧有节点上，仅有非常少的一部分数据迁移到新节点上。
5-5分裂：旧节点和新节点上的数据比例几乎是持平的。
我们通常所说的索引分裂，大部分情况都指的是9-1分裂。当事务向索引最右侧的叶节点上插入一条大于或等于现有索引块上最大值的数据，且该索引块上不存在其他未提交的事务时，如果没有足够的空间，就会发生9-1分裂。
很遗憾的是，当发生左侧节点上插入数据的时候，发生9-1分裂就会出现一些问题。如图2-12所示，当向左侧分支节点插入新值，即使其兄弟右侧分支节点数据区中没有数据（或者说没有右节点），它们的父节点都会发生分裂，极端情况下甚至会促使B树的高度增长，这对索引性能来说是很悲剧的，这一缺陷在Oracle 10g以前的版本中都是存在的。

从Oracle 10g开始，对于左侧节点的数据插入行为，引进了5-5分裂的方式，修正了9-1分裂造成的缺陷。如图2-13所示，当左侧分支节点B1已经处于“充满”状态，会去判断其兄弟右侧分支节点B2是否有空间，如果有，则将部分数据（5∶5的比例）迁移到右侧分支节点上，这样就避免了分支节点甚至根节点的分裂。

5-5分裂的方式也不是万能的，如果过于频繁的5-5分裂也会造成索引空间使用率不高，使得索引结构看上去像一个“虚胖子”，不够“结实’，同样会造成性能问题。
那什么时候会发生5-5分裂呢？简单地说，就是在索引需要分裂，但不能进行9-1分裂的时候就会触发5-5分裂。这听起来像一句废话，可将9-1分裂的条件反过来看，也正是5-5分裂发生的条件：
左侧节点发生新值插入时（新值小于索引中的最大值）；
发生DML操作，索引块上没有足够空间分配新的ITL槽；
新值待插入的索引块上存在其他未提交的事务。
对比一下9-1分裂和5-5分裂的发生场景。9-1分裂通常是索引的键值是递增的，表上的事务并发量比较低，可保证新的数据块上有较大的空闲空间插入新值。5-5分裂通常是表上的事务并发度较高，操作的数据是无序的，需保证分裂的新旧数据块上有相对较大的空闲空间以容纳新事务的操作。
总体来看，不论是9-1分裂还是5-5分裂，对于性能来说，都不是什么好事。索引块的分裂意味着索引数据一定范围上的重组，其维护代价都是非常高昂的，应该尽可能地避免不必要的分裂发生。

2.4.2　实例分析

1.?9-1分裂分析
下面我们通过一些实例的操作来进一步深入分析9-1分裂的过程吧，这将是一个很美妙的过程，就像看到一棵树生长一样。具体步骤如下：
步骤1　创建一个新表alex_t05及索引，我们主要考察索引idx_alex_t05_id：

SQL> create table alex_t05 (id number, name varchar2(100));
SQL> create index idx_alex_t05_id on alex_t05 (id);

步骤2　向alex_t05表中顺序地添加3000行数据，此过程我们将开启10224事件进行跟踪：

SQL> alter session set events '10224 trace name context 
  2  forever,level 1';

Session altered

SQL> declare
  2  begin
  3    for i in 1 .. 3000 loop
  4      insert into alex_t05 values (i, 'alex');
  5    end loop;
  6    commit;
  7  end;
  8  /

SQL> alter session set events '10224 trace name context off';

Session altered

下面是10224跟踪事件记录的索引分裂过程的日志，可以看到其记录了5次索引叶节点数据块的分裂，也就是说整个过程发生了5次索引分裂。因为测试表和索引都是新建的，也就是说此时索引树结构应该有6个叶节点数据块。

splitting leaf,dba 0x010267a4,time 14:53:00.149
kdisnew_bseg_srch_cbk reject block -mark full,dba 0x010267a4,time 14:53:00.151
kdisnew_bseg_srch_cbk rejecting block ,dba 0x010267a4,time 14:53:00.151
kdisnew_bseg_srch_cbk using block,dba 0x010267a6,time 14:53:00.152
kdisnew_bseg_srch_cbk reject block -mark full,dba 0x010267a6,time 14:53:00.152
kdisnew_bseg_srch_cbk rejecting block ,dba 0x010267a6,time 14:53:00.152
kdisnew_bseg_srch_cbk using block,dba 0x010267a7,time 14:53:00.152
splitting leaf,dba 0x010267a7,time 14:53:00.420
kdisnew_bseg_srch_cbk reject block -mark full,dba 0x010267a7,time 14:53:00.421
kdisnew_bseg_srch_cbk rejecting block ,dba 0x010267a7,time 14:53:00.421
kdisnew_bseg_srch_cbk using block,dba 0x010267a8,time 14:53:00.421
splitting leaf,dba 0x010267a8,time 14:53:00.652
kdisnew_bseg_srch_cbk reject block -mark full,dba 0x010267a8,time 14:53:00.652
kdisnew_bseg_srch_cbk rejecting block ,dba 0x010267a8,time 14:53:00.652
kdisnew_bseg_srch_cbk using block,dba 0x010267a5,time 14:53:00.652
splitting leaf,dba 0x010267a5,time 14:53:00.879
kdisnew_bseg_srch_cbk reject block -mark full,dba 0x010267a5,time 14:53:00.879
kdisnew_bseg_srch_cbk rejecting block ,dba 0x010267a5,time 14:53:00.879
kdisnew_bseg_srch_cbk using block,dba 0x010267ae,time 14:53:00.881
splitting leaf,dba 0x010267ae,time 14:53:01.128
kdisnew_bseg_srch_cbk reject block -mark full,dba 0x010267ae,time 14:53:01.128
kdisnew_bseg_srch_cbk rejecting block ,dba 0x010267ae,time 14:53:01.128
kdisnew_bseg_srch_cbk using block,dba 0x010267af,time 14:53:01.128

步骤3　再来验证一下发生的分裂是不是发生了9-1分裂。通过数据字典的查询，可以看到该会话（因为是新建的会话）制造了5次9-1分裂，这和10224事件跟踪的结果是不谋而合的。验证结果如下所示：

SQL> select s.sid, n.name, s.value
  2    from v$sesstat s, v$statname n
  3   where s.statistic# = n.statistic#
  4     and sid in (select sid from v$mystat)
  5     and value > 0
  6     and n.name like '%split%';

       SID   NAME                      VALUE
---------- ------------------------- -------
       1621  leaf node splits              5
       1621  leaf node 90-10 splits        5

步骤4　再来分析一下索引idx_alex_t05_id的结构吧，同时DUMP出索引树形结构。
此时的分裂就索引空间的使用率来说，是比较高效的，使用率大约在76%左右。从DUMP文件可以看到每个叶节点块大约存储570个条目，简单地做个换算，76%充盈的叶块可以存储570行的记录，那一个100%充盈的块即可以存储571/0.76＝750行记录。
同时我们看到索引的PCT_FREE=10%，也就是说索引的叶块的利用率可以达到90%，单块可以存储记录行数即为750×0.9＝675。但实际情况单块存储的记录行数在没有达到675行就已经分裂了，PCT_FREE参数的设置被忽视了。当发生9-1分裂的时候，PCT_FREE参数值仅仅可以作为参考，不知道5-5分裂的时候是否也是一样呢？验证如下所示：

SQL> analyze index idx_alex_t05_id validate structure;

Index analyzed

SQL> select height, 
  2  round((del_lf_rows_len/lf_rows_len)*100,2)||'%' ratio,
  3  pct_used from index_stats where name= 'IDX_ALEX_T05_ID';

    HEIGHT  RATIO       PCT_USED
---------- ---------- ----------
         2  0%                76

SQL> select pct_free from user_indexes 
  2  where index_name='IDX_ALEX_T05_ID';

  PCT_FREE
----------
        10

SQL> alter session set events 'immediate trace name 
  2  treedump level 311979';
----- begin tree dump
branch: 0x10267a4 16934820 (0: nrow: 6, level: 1)
   leaf: 0x10267a6 16934822 (-1: nrow: 577 rrow: 577)
   leaf: 0x10267a7 16934823 (0: nrow: 570 rrow: 570)
   leaf: 0x10267a8 16934824 (1: nrow: 570 rrow: 570)
   leaf: 0x10267a5 16934821 (2: nrow: 570 rrow: 570)
   leaf: 0x10267ae 16934830 (3: nrow: 570 rrow: 570)
   leaf: 0x10267af 16934831 (4: nrow: 143 rrow: 143)
----- end tree dump

2.?5-5分裂分析
接下来再来看一下5-5分裂的情况，它和9-1分裂的方式和原理是不一样的。我们知道有三种情况会触发5-5分裂，我们来逐一测试一下吧。
场景1　左侧节点发生新值插入的情况。
我们可以对上面9-1分裂的例子变换一下，反序插入3000条记录，再通过10224事件和树形结构的DUMP来分析。反序插入记录的代码如下所示：

SQL> declare
  2  begin
  3    for i in 1 .. 3000 loop
  4      insert into alex_t05 values (3001-i, 'alex');
  5    end loop;
  6    commit;
  7  end;
  8  /

此时，我们注意到索引同样只发生了叶节点块的分裂，但是同样的操作，分裂次数由5次增加到了9次。为什么呢？因为触发的是5-5分裂，5-5分裂导致索引叶节点的数据块使用率不高，或者说在使用率还不高的时候就发生了分裂。示例如下：

SQL> select s.sid, n.name, s.value
  2    from v$sesstat s, v$statname n
  3   where s.statistic# = n.statistic#
  4     and sid in (select sid from v$mystat)
  5     and value > 0
  6     and n.name like '%split%';

       SID   NAME                      VALUE
---------- ------------------------- -------
       1621  leaf node splits              9
       1621  leaf node 90-10 splits        0

所以，此时索引空间总体的使用率也由之前的76%下降到了48%（见下面的统计信息），从索引树形结构的DUMP文件中也可以看到单块存储的记录行数由570行下降到了281行，说明此时索引有点像个“虚胖子”了。如果一个索引上频繁发生5-5分裂，则这个“虚胖子”将变得越发“虚弱”。在一次简单的查询或者DML操作的时候，会扫描非常多的索引块，直接导致I/O次数的增加，特别是在并发度很高的表上，这样的变化甚至可能是致命的，可能会让你丧失近10倍的响应速度。当然，这种问题可以通过索引重建来修复，2.5节会具体展开介绍。

SQL> select height, 
  2  round((del_lf_rows_len/lf_rows_len)*100,2)||'%' ratio,
  3  pct_used from index_stats where name= 'IDX_ALEX_T05_ID';

     HEIGHT RATIO        PCT_USED
----------- ---------- ----------
          2  0%                48

如下为索引树形结果的DUMP日志：

----- begin tree dump
branch: 0x10267a4 16934820 (0: nrow: 10, level: 1)
   leaf: 0x10267a7 16934823 (-1: nrow: 471 rrow: 471)
   leaf: 0x10267b0 16934832 (0: nrow: 281 rrow: 281)
   leaf: 0x10267af 16934831 (1: nrow: 281 rrow: 281)
   leaf: 0x10267ae 16934830 (2: nrow: 281 rrow: 281)
   leaf: 0x10267ad 16934829 (3: nrow: 281 rrow: 281)
   leaf: 0x10267ac 16934828 (4: nrow: 281 rrow: 281)
   leaf: 0x10267ab 16934827 (5: nrow: 281 rrow: 281)
   leaf: 0x10267a6 16934822 (6: nrow: 281 rrow: 281)
   leaf: 0x10267a5 16934821 (7: nrow: 281 rrow: 281)
   leaf: 0x10267a8 16934824 (8: nrow: 281 rrow: 281)
----- end tree dump

如预期的结果一样，在发生5-5分裂的时候，PCT_FREE参数再一次被忽视。参数PCT_FREE在索引创建时起作用，而在使用时往往被忽略。如下是索引IDX_ALEX_T05_ID的PCT_FREE参数设置情况：

SQL> select pct_free from user_indexes 
  2  where index_name='IDX_ALEX_T05_ID';

  PCT_FREE
----------
        10

场景2　DML操作时，索引块上没有足够空间分配新的ITL槽。
这种情况应该和第三种情况（新值待插入的索引块上存在其他未提交的事务）结合起来一起看会更加清晰。两种情况都是因为应用的并发度高而引发的。同一索引数据块上的事务数超出了实际允许的ITL数，导致MAXTRANS不足。另外，从Oracle 10g开始，MAXTRANS的值被强制设置为255，不能修改，但实际ITL槽数所占空间一般不能超过数据块大小的一半，如默认8KB大小数据块的限制为169。
我们模拟一个高并发的例子来看一下吧，只做一个简单的insert操作，并发度设置为300（大于169），每个并发进程循环执行100次。

SQL> insert into alex_t05 values 
  2  (trunc(dbms_random.value()*10000), 'alex');

查询并发插入操作前后的系统统计信息，做个差值得到并发操作的等待事件统计和索引分裂状态统计（整个过程数据库无其他会话操作）。因为是无序的插入，索引大部分分裂情况都是5-5分裂。而从等待事件来看，出现了“enq: TX - allocate ITL entry”等待事件，意味着出现了数据块上ITL的争用，当然这其中包括了数据块和索引块的争用。示例如下所示：

SQL> select event, total_waits
  2    from v$system_event
  3   where event in
  4         ('enq: TX - allocate ITL entry', 'enq: TX - index contention');

EVENT                            TOTAL_WAITS
-------------------------------- -----------
enq: TX - allocate ITL entry              18
enq: TX - index contention               134

SQL> select n.name, s.value
  2    from v$sysstat s, v$statname n
  3   where s.statistic# = n.statistic#
  4     and n.name like '%split%';

NAME                           VALUE
------------------------- ----------
leaf node splits                5522
leaf node 90-10 splits            53
branch node splits                22
root node splits                   0

在索引块上，有以下两种情况会触发“enq: TX - allocate ITL entry”等待：
达到数据块上最大事务数限制；
递归事务ITL争用。
场景3　新值待插入的索引块上存在其他未提交的事务。
前面说到这种情况也是由于高并发造成的，需要和第二种情况结合起来考虑。可以说高并发对第三种情况的影响更为明显。
我们再模拟一个高并发的例子，做一个简单的顺序的insert操作，并发度仍设置为300，每个并发进程循环执行仍为100次。因为是顺序插入的，并发的争用更为集中到最右侧的索引节点块上。Insert语句如下：
SQL> insert into alex_t05 values (seq_alex_t05_id.nextval, 'alex');
从如下查询结果可以看到，索引的分裂次数减少了，但是等待事件的次数增加了，也可以说由于等待时间加长了导致发生索引块的分裂的次数减少了。“enq: TX – index contention”是一个与索引分裂直接相关的等待事件，也仅由索引分裂才会触发的等待事件。当一个索引块上发生DML操作，而这个索引块正在被另外一个事务分裂，则需要等待分裂完成后才能修改上面的数据，此时就会发生“enq: TX - index contention”等待事件。因为争用的索引块更集中了，该等待事件发生的次数也就增加了。示例如下所示：

SQL> select event, total_waits
  2    from v$system_event
  3   where event in
  4         ('enq: TX - allocate ITL entry', 'enq: TX - index contention');

EVENT                            TOTAL_WAITS
-------------------------------- -----------
enq: TX - allocate ITL entry             285
enq: TX - index contention             15492

SQL> select n.name, s.value
  2    from v$sysstat s, v$statname n
  3   where s.statistic# = n.statistic#
  4     and n.name like '%split%';

NAME                           VALUE
------------------------- ----------
leaf node splits                1304
leaf node 90-10 splits            19
branch node splits                 4
root node splits                   0

综上所述，发生5-5分裂时，如果是第一种情况，新值小于索引中的最大值，这在索引的应用中是不可避免的，除非是完全理想状态（索引聚簇因子无限接近于数据块数）下。换而言之，其对性能的影响可以不用太多关注，因为我们做不了什么。反之，应该更多关注的是第二种和第三种情况，特别是第三种情况，因为其发生的概率和影响程度都较大。
3.?高并发优化
了解了问题的原理和发生过程，再来说一说解决的办法吧。前面说到索引的争用源自于索引的分裂，因为这是一个代价高昂的操作，而触发索引分裂的契机就是索引上的高并发事务操作。问题现在就集中在“如何去解决高并发导致索引块分裂的争用”上面。
也许有人要说了，索引块上有分裂和争用就增加一些ITL槽来增加并发处理能力嘛。这样的做法会有效吗？我们不妨修改一下索引的initrans参数来试试看，重复做一下300路并发100次循环的简单顺序插入操作：
SQL> alter index idx_alex_t05_id rebuild initrans 10 pctfree 10;
优化后的效果对比如表2-4所示，从分裂情况来看，索引块的分裂总次数明显下降了，而且更倾向于走9-1分裂，说明增加ITL槽后索引块处理并发事务的能力加强了。但不幸的是，等待事件的等待次数反而增加了，特别是ITL槽争用的等待更加明显了，所以说修改initrans参数并没有真正解决问题。随着并发度的不断提升，ITL槽的争用也越发激烈，就好像千军万马买火车票，原来2个窗口，现在增加到10个窗口，其实意义并不大，还是需要一些根本的解决手段。

在进行下一步的优化之前，我们先来思考一下为什么会形成这个问题呢？是的，是高并发没错。再根本一些的原因是高并发操作过于集中在最右侧的索引块上，如果我们能把这种“集中”打散了，那问题是不是就解决了呢？接下来，我们可以引进反向键的B树索引（REVERSE KEY INDEX）来打散这种“集中”，试着解决这个问题看看。
删除掉之前的索引，并重建一个反键索引，如下所示：
SQL> create index idx_alex_t05_id on alex_t05 (id) reverse;
此时的优化效果如表2-5所示，不论从等待事件，还是索引分裂情况来看，优化效果都是比较明显的，这证明我们成功打散了高并发过程中的“集中”。

为什么反键索引会带来这样的效果呢？主要是由反键索引的存储结构决定的，或者说反键索引就是为了解决此类问题而衍生出来的B树索引类型。
对于普通B树索引来说，要存储数据“1234”、“1235”、“1239”，它可能就存储在同一个叶节点块中，如图2-14的左图所示。但是反键B树索引则先会把待存储的数据做一个顺序反转，成为“4321”、“5321”、“9321”后再进行存储，如图2-14的右图所示，本来连续的数据有可能存储在不同叶节点块中，这样就避免了热点索引块的争用。

但是，我们说反键索引也是有一利必有一弊，这一弊则同样是由反键索引的存储结构带来的。我们在数据入库的时候得到了优势，那数据读取呢？查询“1234”、“1235”、“1239”记录，本来访问一个索引块即可，现在需要访问三个了，增加了额外的I/O开销。所以，在反键索引的应用中特别要注意的是，其索引列上的查询，尽可能地使用等值查询，避免范围查询，这样可以避免额外的I/O开销。下面是一个强制走反键索引的范围查询，可以看到COST开销是大得可怕的。

SQL> select * from alex_t05 where id between 106001 and 106010;
------------------------------------------------------------------------------------
| Id  | Operation                   | Name            | Rows  | Bytes | Cost (%CPU)|
------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT            |                 |    11 |    99 |  1146   (1)|
|   1 |  TABLE ACCESS BY INDEX ROWID| ALEX_T05        |    11 |    99 |  1146   (1)|
|*  2 |   INDEX FULL SCAN           | IDX_ALEX_T05_ID |   975 |       |   178   (1)|
------------------------------------------------------------------------------------

当然，我们大可不必因为有弊端而不用它，这样将是非常可惜的。普通B树索引和反键B树索引处理高并发事务的对比情况，如图2-15所示。横坐标轴是递增的高并发数，主纵坐标轴对应柱状图是“enq: TX - index contention”等待事件的平均等待时间，次纵坐标轴对应的是TPS变化曲线。普通B树索引对应的是较高的柱状图和较低TPS曲线，反键B树索引对应的则是较低的柱状图和较高的TPS曲线。

从等待时间来看，反键索引几乎完全消除了“enq: TX - index contention”等待，而TPS能力也有4～5倍的性能提升。相信这完全有理由让大家接受反键索引了。
索引的高效使用不仅在设计阶段需要多多关注，在后期维护阶段也是不容忽视的。高并发的事务处理往往可以使一些潜在的问题浮现出来或更为突出，对于索引分裂和生长的问题大致可以总结以下几点：
避免一切不必要的索引块分裂发生；
尽可能简化索引结构，移除不必要的索引字段；
使选择性更强的字段在前，减小分支节点的大小；
有可能的话，可以创建压缩索引；
对于更新较少的OLAP应用，考虑使用较大数据块的表空间；
定期进行索引重建，再好的设计和使用都无法完全避免索引分裂问题。