技术开发 频道

B-Tree 索引中的数据块分裂

  枝节点分裂

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

  这种情况很容易被重现,我们这就不放demo代码了,下面是trace文件中记录的枝节点分裂:

splitting branch,dba 0x03c00556,time 16:19:27.276

  kdisnew_bseg_srch_cbk rejecting block ,dba
0x03c0054e,time 16:19:27.276

  kdisnew_bseg_srch_cbk using block,dba
0x03c0054e,time 16:19:27.276

  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的数据: 

HELLODBA.COM> begin

  
2 for i in 1..1000

  
3 loop

  
4 insert into idx_split (a, b, c) values (i, dbms_random.string(1,500), sysdate);

  
5 end loop;

  
6 end;

  
7 /

  PL
/SQL procedure successfully completed.

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

...

  kdxcofbo
376=0x178

  kdxcofeo
385=0x181

  kdxcoavs
9

  ...

  row#
2[401] dba: 62915925=0x3c00555

  col
0; len 2; (2): c1 0b

  col
1; TERM

  row#
3[409] dba: 62915926=0x3c00556

  col
0; len 2; (2): c1 0e

  col
1; TERM

  row#
4[417] dba: 62915927=0x3c00557

  col
0; len 2; (2): c1 11

  col
1; TERM

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

HELLODBA.COM> create index idx_split_idx1 on idx_split (a, b) tablespace idx_2k pctfree 0;

  
Index created.

  HELLODBA.COM
> create index idx_split_idx2 on idx_split (b, a) tablespace idx_2k pctfree 0;

  
Index created.

  HELLODBA.COM
> conn demo/demo

  Connected.

  HELLODBA.COM
> alter session set events '10224 trace name context forever,level 1';

  Session altered.

  HELLODBA.COM
> begin

  
2 for i in 1..1000

  
3 loop

  
4 insert into idx_split (a, b, c) values (i, lpad('A', 500, 'A'), sysdate);

  
5 end loop;

  
6 end;

  
7 /

  PL
/SQL procedure successfully completed.

  HELLODBA.COM
> commit;

  
Commit complete.

  HELLODBA.COM
> analyze index idx_split_idx1 validate structure;

  
Index analyzed.

  HELLODBA.COM
> select NAME, HEIGHT, BLOCKS, BR_BLKS, LF_BLKS from index_stats;

  NAME HEIGHT BLOCKS BR_BLKS LF_BLKS

  
------------------------------ ---------- ---------- ---------- ----------

  IDX_SPLIT_IDX1
3 1536 11 1000

  HELLODBA.COM
> analyze index idx_split_idx2 validate structure;

  
Index analyzed.

  HELLODBA.COM
> select NAME, HEIGHT, BLOCKS, BR_BLKS, LF_BLKS from index_stats;

  NAME HEIGHT BLOCKS BR_BLKS LF_BLKS

  
------------------------------ ---------- ---------- ---------- ----------

  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个新的数据块:

splitting leaf,dba 0x03c00545,time 16:19:27.26

  kdisnew_bseg_srch_cbk reject block
-mark full,dba 0x03c00545,time 16:19:27.58

  kdisnew_bseg_srch_cbk rejecting block ,dba
0x03c00545,time 16:19:27.73

  kdisnew_bseg_srch_cbk using block,dba
0x03c0055e,time 16:19:27.73

  kdisnew_bseg_srch_cbk reject block
-mark full,dba 0x03c0055e,time 16:19:27.73

  kdisnew_bseg_srch_cbk rejecting block ,dba
0x03c0055e,time 16:19:27.73

  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分裂:

HELLODBA.COM> begin

  
2 for i in 1..816

  
3 loop

  
4 insert into idx_split (a, b, c) values (i*3, lpad('A', 100, 'A'), sysdate);

  
5 end loop;

  
6 end;

  
7 /

  PL
/SQL procedure successfully completed.

  HELLODBA.COM
> select s.sid, n.name, s.value from v$sesstat s, v$statname n

  
2 where s.statistic# = n.statistic# and sid in (select sid from v$mystat) and value>0 and n.name like '%split%';

  SID NAME VALUE

  
---------- --------------------------- ----------

  
302 branch node splits 2

  
302 leaf node splits 50

  
302 leaf node 90-10 splits 50

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

 branch: 0x3c0043f 62915647 (2: nrow: 1, level: 1)

  leaf:
0x3c0043e 62915646 (-1: nrow: 1 rrow: 1)

  5-5分裂

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

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

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

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

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

--Session 1, 数据插入后未提交

  HELLODBA.COM
> truncate table idx_split;

  
Table truncated.

  HELLODBA.COM
> begin

  
2 for i in 1..816

  
3 loop

  
4 insert into idx_split (a, b, c) values (i*3, lpad('A', 100, 'A'), sysdate);

  
5 end loop;

  
6 end;

  
7 /

  PL
/SQL procedure successfully completed.

  
--Session 2, 插入一条大于索引最大值的数据

  HELLODBA.COM
> insert into idx_split (a, b, c) values (817*3, lpad('A', 100, 'A'), sysdate);

  
1 row created.

  HELLODBA.COM
> select s.sid, n.name, s.value from v$sesstat s, v$statname n

  
2 where s.statistic# = n.statistic# and sid in (select sid from v$mystat) and n.name like '%leaf node%';

  SID NAME VALUE

  
---------- ----------------------- -----------

  
307 leaf node 90-10 splits 0

  
307 leaf node splits 1

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

 branch: 0x3c00433 62915635 (2: nrow: 6, level: 1)

  ...

  leaf:
0x3c00431 62915633 (3: nrow: 11 rrow: 11)

  leaf:
0x3c00432 62915634 (4: nrow: 6 rrow: 6)

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

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

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

0
相关文章