HelloDBA [English]
搜索Internet 搜索 HelloDBABA
  Oracle技术站。email: fuyuncat@gmail.com  MSN: fuyuncat@hotmail.com   acoug  acoug 

B*Tree 索引中的数据块分裂——树的生长

[English]

作者: fuyuncat

来源: www.HelloDBA.com

日期: 2009-10-13 07:05:10

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

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

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

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

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

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

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

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

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

     --- Fuyuncat TBC ---

Top

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

申明
by fuyuncat