BTree 索引中的数据块分裂.docx
- 文档编号:15829014
- 上传时间:2023-07-08
- 格式:DOCX
- 页数:22
- 大小:91.40KB
BTree 索引中的数据块分裂.docx
《BTree 索引中的数据块分裂.docx》由会员分享,可在线阅读,更多相关《BTree 索引中的数据块分裂.docx(22页珍藏版)》请在冰点文库上搜索。
BTree索引中的数据块分裂
B-Tree 索引中的数据块分裂
什么是B-tree索引块分裂
当一个事务需要修改(大多数情况是Insert操作,某些情况下也可能为Delete操作)索引块(枝节点或叶子节点)上的数据,但没有足够空间容纳新的数据(包括索引条目、ITLslot)时,会将原有块上的部分数据放到一个新的数据块上去,这一过程就是索引块分裂(IndexBlockSplitting)。
什么情况下发生索引块分裂
按照分裂的对象不同,分为叶子节点分裂和枝节点分裂,而枝节点分裂中还有一个特殊的分裂:
根节点分裂。
按照分裂时,2个数据块上分布的数据比例,分为5-5分裂和9-1分裂:
5-5分裂:
新旧2个数据块上的数据基本相等;
9-1分裂:
大部分数据还在原有数据块上,只有少量数据被转移到新的数据块上。
叶子节点分裂
1、当Insert、Update(实际上就是Delete+Insert)时,叶子节点块上没有足够空间容纳新的索引条目,就会发生叶子节点分裂:
HELLODBA.COM>createtableidx_split(anumber,bvarchar2(1446),cdate);
Tablecreated.
HELLODBA.COM>createindexidx_split_idxonidx_split(a,b)tablespaceidx_2kpctfree10;
Indexcreated.
HELLODBA.COM>begin
2foriin1..1000
3loop
4insertintotx_index_contention(a,b,c)values(i,lpad('A',10,'A'),sysdate);
5endloop;
6end;
7/
PL/SQLproceduresuccessfullycompleted.
HELLODBA.COM>commit;
Commitcomplete.
HELLODBA.COM>altersessionsetevents'10224tracenamecontextforever,level1';
Sessionaltered.
--叶子节点没有足够空间,发生分裂
HELLODBA.COM>insertintoidx_split(a,b,c)values(800,lpad('A',20,'A'),sysdate);
1rowcreated. 在10224事件的trace文件中可以看到叶子节点块分裂的记录:
splittingleaf,dba0x03c00557,time12:
44:
01.652
kdisnew_bseg_srch_cbkrejectblock-markfull,dba0x03c0054a,time12:
44:
01.699
kdisnew_bseg_srch_cbkrejectingblock,dba0x03c0054a,time12:
44:
01.699
kdisnew_bseg_srch_cbkusingblock,dba0x03c0054b,time12:
44:
01.699 同时,将Btree结构dump出来,也可以看到节点被分裂:
HELLODBA.COM>altersessionsetevents'immediatetracenametreedumplevel198801';
Sessionaltered.
Trace文件:
leaf:
0x3c0055762915927(14:
nrow:
31rrow:
31)
leaf:
0x3c0054b62915915(15:
nrow:
21rrow:
21)
2、当事务需要修改节点上的数据,叶子节点上没有足够空间容纳新的ITLslot时,也会发生分裂。
我们dump出一个“满”的节点,注意到它上面的空闲空间只有20字节,小于一条ITLslot的大小(24字节)
Blockheaderdump:
0x03c00551
ObjectidonBlock?
Y
seg/obj:
0x30892csc:
0x00.b10c56editc:
2flg:
Etyp:
2-INDEX
brn:
0bdba:
0x3c00542ver:
0x01opc:
0
inc:
0exflg:
0
ItlXidUbaFlagLckScn/Fsc
0x010x00b0.01d.000000090x00800b1e.0021.02-BU-1fsc0x0000.b10c56f0
0x020x0000.000.000000000x00000000.0000.00----0fsc0x0000.00000000
...
kdxconro51
kdxcofbo138=0x8a
kdxcofeo158=0x9e
kdxcoavs20
... 并且此时它里面有一条空闲ITLslot(第一条ITLslot是用于递归事务的,后面会有解释),先用一个事务占用它:
HELLODBA.COM>deletefromidx_splitwherea=500;
1rowdeleted. 然后再启动一个事务,造成了空间不足分配新的ITLslot,而导致节点分裂:
HELLODBA.COM>altersessionsetevents'10224tracenamecontextforever,level1';
Sessionaltered.
HELLODBA.COM>deletefromidx_splitwherea=501;
1rowdeleted. 在10224trace文件中记录此次分裂:
splittingleaf,dba0x03c00551,time12:
54:
00.827
kdisnew_bseg_srch_cbkusingblock,dba0x03c00550,time12:
54:
00.874
枝节点分裂
枝节点的下一层的节点分裂,会导致在枝节点上增加一条记录指向新增加的节点,当此时枝节点上空间不足时,会导致枝节点分裂。
这种情况很容易被重现,我们这就不放demo代码了,下面是trace文件中记录的枝节点分裂:
splittingbranch,dba0x03c00556,time16:
19:
27.276
kdisnew_bseg_srch_cbkrejectingblock,dba0x03c0054e,time16:
19:
27.276
kdisnew_bseg_srch_cbkusingblock,dba0x03c0054e,time16:
19:
27.276
kdisnew_bseg_srch_cbkusingblock,dba0x03c0054e,time16:
19:
27.276 要注意的是,枝节点中存储的数据是比较特殊的,因而数据的分布会直接影响到枝节点的多少以及其分裂的频率。
在枝节点中,每条记录指向了下一层一个节点上的最小值,但其并不一定完整的存储了索引字段上的数据:
对于单个字段,如果字段的前面一部分数据就可以定位到下一层的节点块,则枝节点中只存储这一部分数据;例如,字段A的索引节点的第一个叶子节点上的字段数据是AAA11111,AAA22222,....AAA55555;第二个节点上的字段数据是AAA66666,....AAA99999,那么,在枝节点上分别存储的数据是AAA1和AAA6
对于复合字段索引,如果前面字段已经可以定位到下一层的节点块,则枝节点中只存储这些字段,而不存储后面的字段值。
例如,在字段(A,B)上建立了索引,A的值是自增长的,所以通过A就可以定位到下一层的节点,在枝节点上就只存储了A的数据:
HELLODBA.COM>begin
2foriin1..1000
3loop
4insertintoidx_split(a,b,c)values(i,dbms_random.string(1,500),sysdate);
5endloop;
6end;
7/
PL/SQLproceduresuccessfullycompleted.
我们将一个枝节点dump出来,可以看到B字段的数据没有被记录:
...
kdxcofbo376=0x178
kdxcofeo385=0x181
kdxcoavs9
...
row#2[401]dba:
62915925=0x3c00555
col0;len2;
(2):
c10b
col1;TERM
row#3[409]dba:
62915926=0x3c00556
col0;len2;
(2):
c10e
col1;TERM
row#4[417]dba:
62915927=0x3c00557
col0;len2;
(2):
c111
col1;TERM
正因为枝节点的这种的索引值的存储方式,在下面例子中,字段在索引中的顺序不同直接导致了索引的高度不同:
HELLODBA.COM>createindexidx_split_idx1onidx_split(a,b)tablespaceidx_2kpctfree0;
Indexcreated.
HELLODBA.COM>createindexidx_split_idx2onidx_split(b,a)tablespaceidx_2kpctfree0;
Indexcreated.
HELLODBA.COM>conndemo/demo
Connected.
HELLODBA.COM>altersessionsetevents'10224tracenamecontextforever,level1';
Sessionaltered.
HELLODBA.COM>begin
2foriin1..1000
3loop
4insertintoidx_split(a,b,c)values(i,lpad('A',500,'A'),sysdate);
5endloop;
6end;
7/
PL/SQLproceduresuccessfullycompleted.
HELLODBA.COM>commit;
Commitcomplete.
HELLODBA.COM>analyzeindexidx_split_idx1validatestructure;
Indexanalyzed.
HELLODBA.COM>selectNAME,HEIGHT,BLOCKS,BR_BLKS,LF_BLKSfromindex_stats;
NAMEHEIGHTBLOCKSBR_BLKSLF_BLKS
----------------------------------------------------------------------
IDX_SPLIT_IDX131536111000
HELLODBA.COM>analyzeindexidx_split_idx2validatestructure;
Indexanalyzed.
HELLODBA.COM>selectNAME,HEIGHT,BLOCKS,BR_BLKS,LF_BLKSfromindex_stats;
NAMEHEIGHTBLOCKSBR_BLKSLF_BLKS
----------------------------------------------------------------------
IDX_SPLIT_IDX2820485211000 可以看到,idx_split_idx1和idx_split_idx2中的字段是一样的,因此它们的叶子节点数也是一样的,但是因为它们的数据分布性不同以及在索引中的位置不相同,导致它们的枝节点的数量和索引高度有很大的差别。
同时,通过10224事件的trace文件也可以看到,发生在idx_split_idx2上的枝节点分裂次数远远多余在idx_split_idx1上发生的次数。
根节点分裂——特殊的枝节点分裂
在所有枝节点中,有一个特殊的枝节点(或许你可以将它作为一种单独的节点类别),那就是根节点。
根节点上的数据已经导致根节点分裂的条件基本上和普通枝节点相同,但是,唯一不同的是,普通枝节点或叶子节点在分裂时,只分配一个新的数据块,然后将被分裂的数据块上的部分数据转移到新的数据块上去,而根节点的分裂是需要分配2个新的数据块,将原有数据分别转移到2个新的数据块上去,在原有节点上生成2条记录分别指向这2个新的数据块。
下面的Trace记录的就是根节点的分裂,可以看到它获取了2个新的数据块:
splittingleaf,dba0x03c00545,time16:
19:
27.26
kdisnew_bseg_srch_cbkrejectblock-markfull,dba0x03c00545,time16:
19:
27.58
kdisnew_bseg_srch_cbkrejectingblock,dba0x03c00545,time16:
19:
27.73
kdisnew_bseg_srch_cbkusingblock,dba0x03c0055e,time16:
19:
27.73
kdisnew_bseg_srch_cbkrejectblock-markfull,dba0x03c0055e,time16:
19:
27.73
kdisnew_bseg_srch_cbkrejectingblock,dba0x03c0055e,time16:
19:
27.73
kdisnew_bseg_srch_cbkusingblock,dba0x03c0055f,time16:
19:
27.73 9-1分裂
当事务向索引中最后一个叶子节点数据块上插入一条大于或等于(ROWID大于最大值的ROWID)数据块上最大值的数据,且该数据块上不存在其它未提交事务时,此时如果没有足够空间,就会发生9-1分裂:
即分裂时,绝大部分数据保留在原有节点数据块上,仅少量数据被转移到新数据块上。
注意1:
当向索引中插入大于、等于最大值的数据时,PCTFREE会被忽略(我们在后面会介绍索引中PCTFREE和INITRANS的影响)
注意2:
如果叶子节点分裂导致枝节点也分裂,枝节点的分裂比例和叶子节点的分裂比例是相同的。
下面例子中,枝节点和叶子节点都发生了9-1分裂:
HELLODBA.COM>begin
2foriin1..816
3loop
4insertintoidx_split(a,b,c)values(i*3,lpad('A',100,'A'),sysdate);
5endloop;
6end;
7/
PL/SQLproceduresuccessfullycompleted.
HELLODBA.COM>selects.sid,n.name,s.valuefromv$sesstats,v$statnamen
2wheres.statistic#=n.statistic#andsidin(selectsidfromv$mystat)andvalue>0andn.namelike'%split%';
SIDNAMEVALUE
-----------------------------------------------
302branchnodesplits2
302leafnodesplits50
302leafnode90-10splits50
注意,这里的统计结果中,枝节点的分裂方式并未显示,但从Trace文件中可以看到,新分裂的节点数据块上只有少量数据,发生的是9-1分裂:
branch:
0x3c0043f62915647(2:
nrow:
1,level:
1)
leaf:
0x3c0043e62915646(-1:
nrow:
1rrow:
1) 5-5分裂
有3种情况会导致5-5分裂:
当新插入的数据小于索引中的最大值时,此时数据块空间不足容纳新的键值;
当插入、删除数据时,数据块上没有足够空间分配新的ITLslot;
当新插入的数据大于或等于索引中最大值时,此时数据块上还存在其它未提交的事务。
第一种情况很常见,这里不举例了。
第二种情况可以参见之前的例子。
下面代码是第三种情况的例子代码:
--Session1,数据插入后未提交
HELLODBA.COM>truncatetableidx_split;
Tabletruncated.
HELLODBA.COM>begin
2foriin1..816
3loop
4insertintoidx_split(a,b,c)values(i*3,lpad('A',100,'A'),sysdate);
5endloop;
6end;
7/
PL/SQLproceduresuccessfullycompleted.
--Session2,插入一条大于索引最大值的数据
HELLODBA.COM>insertintoidx_split(a,b,c)values(817*3,lpad('A',100,'A'),sysdate);
1rowcreated.
HELLODBA.COM>selects.sid,n.name,s.valuefromv$sesstats,v$statnamen
2wheres.statistic#=n.statistic#andsidin(selectsidfromv$mystat)andn.namelike'%leafnode%';
SIDNAMEVALUE
--------------------------------------------
307leafnode90-10splits0
307leafnodesplits1
可以看到该分裂为5-5分裂,从索引树结构上也可以看出:
branch:
0x3c0043362915635(2:
nrow:
6,level:
1)
...
leaf:
0x3c0043162915633(3:
nrow:
11rrow:
11)
leaf:
0x3c0043262915634(4:
nrow:
6rrow:
6)
实际上,无论是9-1分裂还是5-5分裂,其目的都是为了减少分裂,因为节点分裂是一个代价高昂的操作:
当发生9-1分裂时,通常是索引的键值是递增的,且表上的主要操作为插入操作、事务并发量比较低的情况。
保证新的数据块上有最大的空闲空间插入新值,因而减少了分裂的发生;
发生5-5分裂时,通常表上的并发事务较多,且插入、删除的数据比较分散,因此需要保持分裂的新、老数据块上有相当的空闲空间以容纳新事务、新数据。
树的生长
当分裂导致B树索引的层数(BtreeLevel)增加时,我们称之为树的“生长”。
当叶子节点分裂时,在其父节点上需要增加一条记录指向新节点,如果此时父节点上没有足够空间,则父节点也会发生分裂,如果如此递归下去,直到根节点也分裂,那么索引的高度就增加了。
下图为一次9-1分裂导致的树的增长:
上面的分裂过程中,节点Root、B5、B3和L4在数据插入前都已经饱和,当数据插入时,导致这4个节点发生连锁的分裂,最终root的分裂会分配两个新枝节点,分别为其左右枝节点,由于L4、B3、B5都是发生9-1分裂,在新分裂的数据块上没有被转移老数据,它们都被放到了新生的右枝上了。
在每一个枝节点中,都有且只有一个左指针指向其下一层的左节点。
这个指针很特殊,它存储于枝节点的头部而非数据区,其节点的键值是枝节点中唯一小于枝节点的键值数据、且不被存储。
枝节点中其它的所有指针我们都称为右指针(即其节点键值大于等于枝节点的键值,且都有相应记录存储)。
在节点分裂过程中,始终会保证每一个枝节点的左节点都有数据。
由于左节点的特殊性,仅仅按照之前的分裂条件,当向左枝节点左侧插入数据时,即使其兄弟右枝节点数据区中没有数据(即只有左节点、没有右节点),它们的父节点都会分裂,在特殊情况下(所有左枝节点都饱和,但右枝节点下没有数据),索引高度会增加,但底层枝节点下很空,叶子节点很少。
甚至于特殊情况下(索引数据块为2K、键值数据长度大于1K),叶子节点数可以等于索引高度。
这一算法缺陷在9i及之前版本都存在,如下图所示:
分裂前,所有左枝节点、叶子节点都已经饱和,左分裂造成连锁分裂,促成树的增长。
如果键值为特殊数据、数据块为2K的话,此次分裂后,所有左节点仍然保持饱和状态——意味下一次的左插入会继续导致树的增长。
在10g中,这个缺陷被修正了:
当左枝节点已经饱和时,会先检查其兄弟右枝节点是否为空,如果为空,则将左枝节点的部分数据(5-5)转移到右枝节点,从而避免左枝节点的分裂,如下图所示:
这一算法的修正避免了左分裂造成树的迅速增长。
我们知道,在表的数据块中,当数据插入时,要保证数据块上剩余空间大于、等于PCTFREE的比例设置,以用于数据更新和多事务处理,从而减少数据迁移(RowMigration)的发生;而当分配新的数据块时,会根据INITRANS的设置预留相应的ITLslot,保证并发事务能分配到ITLslot。
在索引中,这两个参数仅在有数据时创建或重建索引才会起作用,且仅在叶子节点上起作用。
INITRANS
INITRANS在索引数据块上是否起作用,是由索引在创建或重建时是否有数据(即是否会分配数据块)决定的。
比较以下代码,第一段代码在truncate之后rebuild(即不会分配索引数据块),因而ITLslot数量为默认值2
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- BTree 索引中的数据块分裂 索引 中的 数据 分裂