B+树的插入和删除策略.[急]

分类: 电脑/网络 >>程序设计 >>其他编程语言

问题描述:

B+树的插入和删除策略.

好多书上说的都不一样

什么重新分布指针啊?搞不懂

解析:

我上学时做过B+树的project,的确比较复杂

插入的时候,当一个节点满了就会引起节点分裂,同时可能引起父节点分裂,最终指向根结点

删除的时候,当一个节点包含的个数小于一半时需要合并节点,同时要考虑其他节点的相应变化

B+树是一种平衡多叉树,跟B树差不多

一棵m阶的B树满足下列条件：

⑴ 树中每个结点至多有m个孩子；

⑵ 除根结点和叶子结点外，其它每个结点至少有m/2个孩子；

⑶ 若根结点不是叶子结点，则至少有2个孩子；

⑷ 所有叶子结点都出现在同一层，叶子结点不包含任何关键字信息；

⑸ 有k个孩子的非终端结点恰好包含有k-1个关键字。

在B树中，每个结点中关键字从小到大排列，并且当该结点的孩子是非叶子结点时，该k-1个关键字正好是k个孩子包含的关键字的值域的分划。

因为叶子结点不包含关键字，所以可以把叶子结点看成在树里实际上并不存在外部结点，指向这些外部结点的指针为空，叶子结点的数目正好等于树中所包含的关键字总个数加1。

B树中的一个包含n个关键字，n+1个指针的结点的一般形式为： （n,P0,K1,P1,K2,P2,…,Kn,Pn）

其中，Ki为关键字，K1<K2<…<Kn, Pi 是指向包括Ki到Ki+1之间的关键字的子树的指针。

B-Tree索引是最常见的索引结构，默认创建的索引就是B-Tree索引。

一、B树索引的结构

B-树索引是基于二叉树结构的。B-树索引结构有3个基本组成部分：根节点、分支节点和叶子节点。其中根节点位于索引结构的最顶端，而叶子节点位于索引结构的最底端，中间为分子节点。

叶子节点（Leaf node）：包含条目直接指向表里的数据行。

分支节点（Branch node）：包含的条目指向索引里其他的分支节点或者是叶子节点。

根节点（Branch node）：一个B树索引只有一个根节点，它实际就是位于树的最顶端的分支节点。

可以用下图一来描述B树索引的结构。其中，B表示分支节点，而L表示叶子节点。

clip_image001

1.1关于分支节点块（包括根节点块）

1、 其所包含的索引条目都是按照顺序排列的（缺省是升序排列，也可以在创建索引时指定为降序排列）。

2、 每个索引条目（也可以叫做每条记录）都具有两个字段。第一个字段表示当前该分支节点块下面所链接的索引块中所包含的最小键值；第二个字段为四个字节，表示所链接的索引块的地址，该地址指向下面一个索引块。

3、 在一个分支节点块中所能容纳的记录行数由数据块大小以及索引键值的长度决定。比如从上图一可以看到，对于根节点块来说，包含三条记录，分别为（0 B1）、（500 B2）、（1000 B3），它们指向三个分支节点块。其中的0、500和1000分别表示这三个分支节点块所链接的键值的最小值。而B1、B2和B3则表示所指向的三个分支节点块的地址。

1.2关于叶子节点

1、 B树索引的所有叶子块一定位于同一层上，这是由B树的数据结构定义的。Oracle 设计的B树索引结构保证了B 树索引从根到叶子都有相等的分支节点，保证了B树索引的平衡，这样就不会因为基表的数据插入后删除 *** 作造成B树索引变得不平衡，从而影响索引的性能。因此，从根块到达任何一个叶子块的遍历代价都是相同的； 索引高度是指从根块到达叶子块时所遍历的数据块的个数，通常，大多数的B树索引的高度都是2到3，也就意味着，即使表中有上百万条记录，从索引中定位一个键字只需要2或3次I/O,索引越高，性能越差；

2、 叶子节点所包含的索引条目与分支节点一样，都是按照顺序排列的（缺省是升序排列，也可以在创建索引时指定为降序排列）

3、 每个索引条目（也可以 叫做每条记录）也具有两个字段。第一个字段表示索引的键值，对于单列索引来说是一个值；而对于多列索引来说则是多个值组合在一起的。第二个字段表示键值所对应的记录行的ROWID，该ROWID是记录行在表里的物理地址。ROWID 是唯一的Oracle 指针，指向该行的物理位置，使用ROWID 是Oracle 数据库中访问行最快的方法。参照Oracle中的rowid

4、 叶子节点其实是一个双向链表，每个叶子节点包含一个指向下一个和上一个叶子点的指针，这样在一定范围内便利索引以搜索需要的记录。

clip_image002

clip_image004

二、B树索引的访问

当oracle进程需要访问数据文件里的数据块时，oracle会有两种类型的I/O *** 作方式：

1） 随机访问，每次读取一个数据块（通过等待事件“db file sequential read”体现出来）。

2） 顺序访问，每次读取多个数据块（通过等待事件“db file scattered read”体现出来）。

第一种方式则是访问索引里的数据块，而第二种方式的I/O *** 作属于全表扫描。这里顺带有一个问题，为何随机访问会对应到db file sequential read等待事件，而顺序访问则会对应到db file scattered read等待事件呢？这似乎反过来了，随机访问才应该是分散（scattered）的，而顺序访问才应该是顺序（sequential）的。其实，等待事件主要根据实际获取物理I/O块的方式来命名的，而不是根据其在I/O子系统的逻辑方式来命名的。下面对于如何获取索引数据块的方式中会对此进行说明。

事实上在B树索引虽然为一个树状的立体结构，但其对应到数据文件里的排列当然还是一个平面的形式，也就是像下面这样。

/根/分支/分支/叶子/…/叶子/分支/叶子/叶子/…/叶子/分支/叶子/叶子/…/叶子/分支/.....

因此，当oracle需要访问某个索引块的时候，势必会在这个结构上跳跃的移动。

当oracle需要获得一个索引块时，首先从根节点开始，根据所要查找的键值，从而知道其所在的下一层的分支节点，然后访问下一层的分支节点，再次同样根据键值访问再下一层的分支节点，如此这般，最终访问到最底层的叶子节点。可以看出，其获得物理I/O块时，是一个接着一个，按照顺序，串行进行的。在获得最终物理块的过程中，我们不能同时读取多个块，因为我们在没有获得当前块的时候是不知道接下来应该访问哪个块的。因此，在索引上访问数据块时，会对应到 db file sequential read等待事件，其根源在于我们是按照顺序从一个索引块跳到另一个索引块，从而找到最终的索引块的。

那么对于全表扫描来说，则不存在访问下一个块之前需要先访问上一个块的情况。全表扫描时，oracle知道要访问所有的数据块，因此唯一的问题就是尽可能高效的访问这些数据块。因此，这时oracle可以采用同步的方式，分几批，同时获取多个数据块。这几批的数据块在物理上可能是分散在表里的，因此其对应到db file scattered read等待事件。

三、DML对B树索引的影响

3.1 INSERT

在每个INSERT *** 作过程中，关键字必须被插入在正确叶节点的位置。如果叶节点已满，不能容纳更多的关键字，就必须将叶节点拆分。拆分的方法有两种：

1)如果新关键字值在所有旧叶节点块的所有关键字中是最大的，那么所有的关键字将按照99:1的比例进行拆分，使得在新的叶节点块中只存放有新关键字，而其他的所有关键字（包括所有删除的关键字）仍然保存在旧叶节点块中。

2)如果新关键字值不是最大的，那么所有的关键字将按照50:50的比例进行拆分，这时每个叶节点块（旧与新）中将各包含原始叶节点中的一半关键字。

这个拆分必须通过一个指向新叶节点的新入口向上传送到父节点。如果父节点已满，那么这个父节点也必须进行拆分，并且需要将这种拆分向上传送到父节点的父节点。这时，如果这个父节点也已满，将继续进行这个过程。这样，某个拆分可能最终被一直传送到根节点。如果根节点满了，根结点也将进行分裂。根结点在进行分裂的时候，就是树的高度增加的时候。根节点进行分裂的方式跟其他的的节点分裂的方式相比较，在物理位置上的处理也是不同的。根节点分裂时，将原来的根结点分裂为分支节点或叶节点，保存到新的块中，而将新的根节点信息保存到原来的根结点块中，这样做的是为因为避免修改数据字典所带来的相对较大的开销。

注意：现在Oracle都是采用了平衡算法，正常情况下即使索引关键字不断增大，也不会产生不平衡树。当索引关键字不断增大，导致树级别单方向增长时，Oracle会自动进行索引翻转以维持索引的平衡，当然这种 *** 作非常消耗资源

在索引的每一个层次之间，每一个层最左边的节点的block头部都有一个指向下层最左边的块的指针，这样有利于fast full scan 的快速定位最左边的叶子节点。

每个拆分过程都是要花费一定的开销的，特别是要进行物理硬盘I/O动作。此外，在进行拆分之前，Oracle必须查找到一个空块，用来保存这个拆分。可以用以下步骤来进行查找空块的动作：

1) 在索引的自由列表(free-list, 又称为空闲列表) 中查到一个空闲块，可以通过CREATE/ALTER INDEX命令为一个索引定义多个空闲列表。索引空闲列表并不能帮助Oracle查找一个可用来存放将要被插入的新关键字的块。这是因为关键字值不能随机地存放在索引中可用的第一个“空闲”叶节点块中，这个值必须经过适当的排序之后，放置在某个特定的叶节点块中。只有在块拆分过程中才需要使用索引的空闲列表，每个空闲列表都包含有一个关于“空”块的链接列表。当为某个索引定义了多个空闲列表时，首先将从分配给进程的空间列表中扫描一个空闲块。如果没有找到所需要的空闲块，将从主空闲列表中进行扫描空闲块的动作。

2) 如果没有找到任何空闲块，Oracle将试图分配另一个扩展段。如果在表空间中没有更多的自由空间，Oracle将产生错误ORA-01654。

3) 如果通过上述步骤，找到了所需的空闲块，那么这个索引的高水位标(HWM)将加大。

4) 所找到的空闲块将用来执行拆分动作。

在创建B*树索引时，一个需要注意的问题就是要避免在运行时进行拆分，或者，要在索引创建过程中进行拆分（“预拆分”），从而使得在进行拆分时能够快速命中，以便避免运行时插入动作。当然，这些拆分也不仅仅局限于插入动作，在进行更新的过程中也有可能会发生拆分动作。

3.2 UPDATE

索引更新完全不同于表更新，在表更新中，数据是在数据块内部改变的（假设数据块中有足够的空间来允许进行这种改变）；但在索引更新中，如果有关键字发生改变，那么它在树中的位置也需要发生改变。请记住，一个关键字在B*树中有且只有一个位置。因此，当某个关键字发生改变时，关键字的旧表项必须被删除，并且需要在一个新的叶节点上创建一个新的关键字。旧的表项有可能永远不会被重新使用，这是因为只有在非常特殊的情况下， Oracle才会重用关键字表项槽，例如，新插入的关键字正好是被删除的那个关键字（包括数据类型、长度等等）。（这里重用的是块，但完全插入相同的值的时候，也不一定插入在原来的被删除的位置，只是插入在原来的块中，可能是该块中的一个新位置。也正因为如此，在索引块中保存的的记录可能并不是根据关键字顺序排列的，随着update等的 *** 作，会发生变化。）那么，这种情况发生的可能性有多大呢？许多应用程序使用一个数列来产生NUMBER关键字（特别是主关键字）。除非它们使用了RECYCLE选项，否则这个数列将不会两次产生完全相同的数。这样，索引中被删除的空间一直没有被使用。这就是在大规模删除与更新过程中，表大小不断减小或至少保持不变但索引不断加大的原因。

3.3 DELETE

当删除表里的一条记录时，其对应于索引里的索引条目并不会被物理的删除，只是做了一个删除标记。当一个新的索引条目进入一个索引叶子节点的时候，oracle会检查该叶子节点里是否存在被标记为删除的索引条目，如果存在，则会将所有具有删除标记的索引条目从该叶子节点里物理的删除。

当一个新的索引条目进入索引时，oracle会将当前所有被清空的叶子节点（该叶子节点中所有的索引条目都被设置为删除标记）收回，从而再次成为可用索引块。

尽管被删除的索引条目所占用的空间大部分情况下都能够被重用，但仍然存在一些情况可能导致索引空间被浪费，并造成索引数据块很多但是索引条目很少的后果，这时该索引可以认为出现碎片。而导致索引出现碎片的情况主要包括：

1、不合理的、较高的PCTFREE。很明显，这将导致索引块的可用空间减少。

2、索引键值持续增加（比如采用sequence生成序列号的键值），同时对索引键值按照顺序连续删除，这时可能导致索引碎片的发生。因为前面我们知道，某个索引块中删除了部分的索引条目，只有当有键值进入该索引块时才能将空间收回。而持续增加的索引键值永远只会向插入排在前面的索引块中，因此这种索引里的空间几乎不能收回，而只有其所含的索引条目全部删除时，该索引块才能被重新利用。

3、经常被删除或更新的键值，以后几乎不再会被插入时，这种情况与上面的情况类似。

四、总结

通过上面对B树的分析，可以得出以下的应用准则：

1、避免对那些可能会产生很高的更新动作的列进行索引。

2、避免对那些经常会被删除的表中的多个列进行索引。若有可能，只对那些在这样的表上会进行删除的主关键字与/或列进行索引。如果对多个列进行索引是不可避免的，那么就应该考虑根据这些列对表进行划分，然后在每个这样的划分上执行TRUNCATE动作（而不是DELETE动作）。TRUNCATE在与 DROP STORAGE短语一同使用时，通过重新设置高水位标来模拟删除表与索引以及重新创建表与索引的过程。

3、避免为那些唯一度不高的列创建B*树索引。这样的低选择性将会导致树节点块的稠密性，从而导致由于索引“平铺( flat)”而出现的大规模索引扫描。唯一性的程度越高，性能就越好，因为这样能够减少范围扫描，甚至可能用唯一扫描来取代范围扫描。

4）空值不存储在单列索引中。对于复合索引的方式，只有当某个列不空时，才需要进行值的存储。在为DML语句创建IS NULL或IS NOT NULL短语时，应该切记这个问题。

5）IS NULL不会导致索引扫描，而一个没有带任何限制的IS NOT NULL则可能会导致完全索引扫描。

---