HelloDBA [English]
搜索Internet 搜索 HelloDBABA
首页
技术文档
产品及下载
订阅
  • 至 Google
  • 至 Yahoo
  • 至 zhuxia
  • 至 xianguo
  • 至 QQ email
  • 至 YouDao
关于
  Oracle技术站。email: fuyuncat@gmail.com  MSN: fuyuncat@hotmail.com   acoug  acoug 

B*Tree 索引中的数据块分裂——如何分裂

[English]

作者： fuyuncat

来源： www.HelloDBA.com

日期： 2009-10-12 08:43:43

分享到  新浪微博 腾讯微博 人人网 i贴吧 开心网 豆瓣 淘宝 推特 Facebook GMail Blogger Orkut Google Bookmarks

什么是B*Tree索引块分裂

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

什么情况下发生索引块分裂

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

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

  •     5-5分裂：新旧2个数据块上的数据基本相等；
  •     9-1分裂：大部分数据还在原有数据块上，只有少量数据被转移到新的数据块上。

叶子节点分裂

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

SQL代码
  1. HELLODBA.COM> create table idx_split (a number, b varchar2(1446), c date);   
  2.   
  3. Table created.   
  4.   
  5. HELLODBA.COM> create index idx_split_idx on idx_split (a, b) tablespace idx_2k pctfree 10;   
  6.   
  7. Index created.   
  8.   
  9. HELLODBA.COM> begin  
  10.   2     for i in 1..1000   
  11.   3     loop   
  12.   4         insert into tx_index_contention (a, b, c) values (i, lpad('A', 10, 'A'), sysdate);   
  13.   5     end loop;   
  14.   6  end;   
  15.   7  /   
  16.   
  17. PL/SQL procedure successfully completed.   
  18.   
  19. HELLODBA.COM> commit;   
  20.   
  21. Commit complete.   
  22.   
  23. HELLODBA.COM> alter session set events '10224 trace name context forever,level 1';   
  24.   
  25. Session altered.   
  26.   
  27. --叶子节点没有足够空间，发生分裂   
  28. HELLODBA.COM> insert into idx_split (a, b, c) values (800, lpad('A', 20, 'A'), sysdate);   
  29.   
  30. 1 row created.  

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

SQL代码
  1. splitting leaf,dba 0x03c00557,time 12:44:01.652   
  2. kdisnew_bseg_srch_cbk reject block -mark full,dba 0x03c0054a,time 12:44:01.699   
  3. kdisnew_bseg_srch_cbk rejecting block ,dba 0x03c0054a,time 12:44:01.699   
  4. kdisnew_bseg_srch_cbk using block,dba 0x03c0054b,time 12:44:01.699  

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

SQL代码
  1. HELLODBA.COM> alter session set events 'immediate trace name treedump level 198801';   
  2.   
  3. Session altered.   
  4. Trace文件：   
  5.    leaf: 0x3c00557 62915927 (14: nrow: 31 rrow: 31)   
  6.    leaf: 0x3c0054b 62915915 (15: nrow: 21 rrow: 21)  

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

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

SQL代码
  1. Block header dump:  0x03c00551   
  2.  Object id on Block? Y   
  3.  seg/obj: 0x30892  csc: 0x00.b10c56ed  itc: 2  flg: E  typ: 2 - INDEX  
  4.      brn: 0  bdba: 0x3c00542 ver: 0x01 opc: 0   
  5.      inc: 0  exflg: 0   
  6.     
  7.  Itl           Xid                  Uba         Flag  Lck        Scn/Fsc   
  8. 0x01   0x00b0.01d.00000009  0x00800b1e.0021.02  -BU-    1  fsc 0x0000.b10c56f0   
  9. 0x02   0x0000.000.00000000  0x00000000.0000.00  ----    0  fsc 0x0000.00000000   
  10.   
  11. ...   
  12. kdxconro 51   
  13. kdxcofbo 138=0x8a   
  14. kdxcofeo 158=0x9e   
  15. kdxcoavs 20   
  16. ...  

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

SQL代码
  1. HELLODBA.COM> delete from idx_split where a=500;   
  2.   
  3. 1 row deleted.  

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

SQL代码
  1. HELLODBA.COM> alter session set events '10224 trace name context forever,level 1';   
  2.   
  3. Session altered.   
  4.   
  5. HELLODBA.COM> delete from idx_split where a=501;   
  6.   
  7. 1 row deleted.  

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

SQL代码
  1. splitting leaf,dba 0x03c00551,time 12:54:00.827   
  2. kdisnew_bseg_srch_cbk using block,dba 0x03c00550,time 12:54:00.874  

枝节点分裂

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

SQL代码
  1. splitting branch,dba 0x03c00556,time 16:19:27.276      
  2. kdisnew_bseg_srch_cbk rejecting block ,dba 0x03c0054e,time 16:19:27.276      
  3. kdisnew_bseg_srch_cbk using block,dba 0x03c0054e,time 16:19:27.276      
  4. kdisnew_bseg_srch_cbk using block,dba 0x03c0054e,time 16:19:27.276  

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

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

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

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

SQL代码
  1. HELLODBA.COM> begin  
  2.   2     for i in 1..1000   
  3.   3     loop   
  4.   4         insert into idx_split (a, b, c) values (i, dbms_random.string(1,500), sysdate);   
  5.   5     end loop;   
  6.   6  end;   
  7.   7  /   
  8.   
  9. PL/SQL procedure successfully completed.  

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

SQL代码
  1. ...   
  2. kdxcofbo 376=0x178   
  3. kdxcofeo 385=0x181   
  4. kdxcoavs 9   
  5. ...   
  6. row#2[401] dba: 62915925=0x3c00555   
  7. col 0; len 2; (2):  c1 0b   
  8. col 1; TERM   
  9. row#3[409] dba: 62915926=0x3c00556   
  10. col 0; len 2; (2):  c1 0e   
  11. col 1; TERM   
  12. row#4[417] dba: 62915927=0x3c00557   
  13. col 0; len 2; (2):  c1 11   
  14. col 1; TERM  

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

SQL代码
  1. HELLODBA.COM> create index idx_split_idx1 on idx_split (a, b) tablespace idx_2k pctfree 0;   
  2.   
  3. Index created.   
  4.   
  5. HELLODBA.COM> create index idx_split_idx2 on idx_split (b, a) tablespace idx_2k pctfree 0;   
  6.   
  7. Index created.   
  8.   
  9. HELLODBA.COM> conn demo/demo   
  10. Connected.   
  11. HELLODBA.COM> alter session set events '10224 trace name context forever,level 1';   
  12.   
  13. Session altered.   
  14.   
  15. HELLODBA.COM> begin  
  16.   2     for i in 1..1000   
  17.   3     loop   
  18.   4         insert into idx_split (a, b, c) values (i, lpad('A', 500, 'A'), sysdate);   
  19.   5     end loop;   
  20.   6  end;   
  21.   7  /   
  22.   
  23. PL/SQL procedure successfully completed.   
  24.   
  25. HELLODBA.COM> commit;   
  26.   
  27. Commit complete.   
  28.   
  29. HELLODBA.COM> analyze index idx_split_idx1 validate structure;   
  30.   
  31. Index analyzed.   
  32.   
  33. HELLODBA.COM> select NAME, HEIGHT, BLOCKS, BR_BLKS, LF_BLKS from index_stats;   
  34.   
  35. NAME                               HEIGHT     BLOCKS    BR_BLKS    LF_BLKS   
  36. ------------------------------ ---------- ---------- ---------- ----------   
  37. IDX_SPLIT_IDX1                          3       1536         11       1000   
  38.   
  39. HELLODBA.COM> analyze index idx_split_idx2 validate structure;   
  40.   
  41. Index analyzed.   
  42.   
  43. HELLODBA.COM> select NAME, HEIGHT, BLOCKS, BR_BLKS, LF_BLKS from index_stats;   
  44.   
  45. NAME                               HEIGHT     BLOCKS    BR_BLKS    LF_BLKS   
  46. ------------------------------ ---------- ---------- ---------- ----------   
  47. IDX_SPLIT_IDX2                          8       2048        521       1000  

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

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

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

SQL代码
  1. splitting leaf,dba 0x03c00545,time 16:19:27.26   
  2. kdisnew_bseg_srch_cbk reject block -mark full,dba 0x03c00545,time 16:19:27.58   
  3. kdisnew_bseg_srch_cbk rejecting block ,dba 0x03c00545,time 16:19:27.73   
  4. kdisnew_bseg_srch_cbk using block,dba 0x03c0055e,time 16:19:27.73   
  5. kdisnew_bseg_srch_cbk reject block -mark full,dba 0x03c0055e,time 16:19:27.73   
  6. kdisnew_bseg_srch_cbk rejecting block ,dba 0x03c0055e,time 16:19:27.73   
  7. kdisnew_bseg_srch_cbk using block,dba 0x03c0055f,time 16:19:27.73  

9-1分裂

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

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

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

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

SQL代码
  1. HELLODBA.COM> begin  
  2.   2     for i in 1..816   
  3.   3     loop   
  4.   4         insert into idx_split (a, b, c) values (i*3, lpad('A', 100, 'A'), sysdate);   
  5.   5     end loop;   
  6.   6  end;   
  7.   7  /   
  8.   
  9. PL/SQL procedure successfully completed.   
  10.   
  11. HELLODBA.COM> select s.sid, n.name, s.value from v$sesstat s, v$statname n   
  12.   2  where s.statistic# = n.statistic# and sid in (select sid from v$mystat) and value>0 and n.name like '%split%';   
  13.   
  14.        SID NAME                        VALUE   
  15. ---------- --------------------------- ----------   
  16.        302 branch node splits          2   
  17.        302 leaf node splits            50   
  18.        302 leaf node 90-10 splits      50  

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

SQL代码
  1. branch: 0x3c0043f 62915647 (2: nrow: 1, level: 1)   
  2.    leaf: 0x3c0043e 62915646 (-1: nrow: 1 rrow: 1)  

5-5分裂

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

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

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

SQL代码
  1. --Session 1, 数据插入后未提交   
  2. HELLODBA.COM> truncate table idx_split;   
  3.   
  4. Table truncated.   
  5.   
  6. HELLODBA.COM> begin  
  7.   2     for i in 1..816   
  8.   3     loop   
  9.   4         insert into idx_split (a, b, c) values (i*3, lpad('A', 100, 'A'), sysdate);   
  10.   5     end loop;   
  11.   6  end;   
  12.   7  /   
  13.   
  14. PL/SQL procedure successfully completed.   
  15.   
  16. --Session 2, 插入一条大于索引最大值的数据   
  17. HELLODBA.COM> insert into idx_split (a, b, c) values (817*3, lpad('A', 100, 'A'), sysdate);   
  18.   
  19. 1 row created.   
  20.   
  21. HELLODBA.COM> select s.sid, n.name, s.value from v$sesstat s, v$statname n   
  22.   2  where s.statistic# = n.statistic# and sid in (select sid from v$mystat) and n.name like '%leaf node%';   
  23.   
  24.        SID NAME                    VALUE   
  25. ---------- ----------------------- -----------   
  26.        307 leaf node 90-10 splits  0   
  27.        307 leaf node splits        1  

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

SQL代码
  1. branch: 0x3c00433 62915635 (2: nrow: 6, level: 1)   
  2.    ...   
  3.    leaf: 0x3c00431 62915633 (3: nrow: 11 rrow: 11)   
  4.    leaf: 0x3c00432 62915634 (4: nrow: 6 rrow: 6)  

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

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

--- Fuyuncat TBC ---
上一篇： 下一篇：
本类中的所有文章

Top

Copyright ©2005，HelloDBA.Com 保留一切权利

申明
by fuyuncat