现在的位置: 首页 > 数据库 > 正文

B树索引结构分析[转]

2014年10月31日 数据库 ⁄ 共 3660字 暂无评论 ⁄ 阅读 2,017 次
文章目录

B树的结构

B树索引由根节点块,分支节点块,叶子节点块组成。对应于每个B树索引都有一个参数n,它决定了B树的所有存储块的布局。每个存储块存放n个查找键值和n+1个指针。B树的块除了有n个键&指针对外,还有一个额外的指针。在存储块能容纳n个键和n+1个指针的前提下,我们把n取得尽可能大。假定我们的存储块大小为4096字节,且整数型键值占4字节,指针占8字节。要是不考虑存储块块头信息所占空间,那么我们希望找到满足4n+8(n+1)≤4096的最大整数值n。这个值是n=340。

下面几个重要的规则限制B树的存储块中能出现的东西:

  • 根结点中,至少有两个指针被使用,所有指针指向位于B树下一层的存储块。从技术上来讲,整个B树的块只有一个指针也是可能的,因为它可能是只有一个记录的数据文件的索引。在这种情况下,整个B树既是根块又是叶块,且这个块只有一个键值和一个指针,本文我们将忽略这种平凡的情况。
  • 叶结点中,最后一个指针指向它右边的下一个叶结点存储块,即指向下一个键值大于它的块。在叶块的其他n个指针当中,至少有个指针被使用且指向数据记录;未使用的指针可看作空指针且不指向任何地方。如果第i个指数被使用,则指向具有第i个键值的记录。
  • 分支结点中,所有的n+1个指针都可以用来指向B树中下一层的块。其中至少1个指针被实际使用(但如果是根结点,则不管n多大都只要求至少两个指针被使用)。如果j个指针被使用,那该块中将有j-1个键,设为K1,K2,Kj-1。第一个指针指向B树的一部分,一些键值小于K1的记录可在这一部分找到。第二个指针指向B树的另一部分,所有键值大小等于K1且小于K2的记录可在这一部分中。依此类推。最后,第j个指针指向B树的又一部分,一些键值大于等于Kj-1的记录可以在这一部分中找到。注意:某些键值远小于K1或远大于Kj-1的记录可能根本无法通过该块到达,但可通过同一层的其他块到达。
  • 假若我们以常规的画树方式来画B树,任一给定结点的子结点按从左(第一个子结点)到右(最后一个子结点)的顺序排列。那么,我们在任何一个层次上从左到右来看B树的结点,结点的键值将按非减的顺序出现。

叶节点举例

在这个例子和其他B树实例中,我们设n=3。也就是说,块中可存放3个键值和4个指针,这是一个不代表通常情况的小数字,键值为整数。如下图所示为一个完全使用的叶结点。其中有三个键值57、81和95。前三个指针指向具有这些键值的记录。而最后一个指针,指向右边键值大于它的下一个叶结点,这正是叶结点中通常的情况。如果该叶结点是序列中的最后一个,则该指针为空。叶结点不必全部充满,但在我们这个例子中,n=3,故叶结点至少要有两个键-指针对。也就是说,下图中的键值95和第三个指针可以没有,该指针标为“指向键值为95的记录”。

b-tree-index1

分支节点举例

该例中有三个键值,与我们在叶结点的例子中所选的一样:57、81和95,该结点中还有四个指针。第一个指针指向B树的一部分,通过它我们只能到达键值小于第一个键值即57的那些记录。第二个指针通向键值介于该B树块第一个键值和第二个键值之间的那些记录,第三个指针对应键值介于该块第二个键值和第三个键值之间的那些记录,第四个指针将我们引向键值大于该块中第三个键值的那些记录。

同叶结点的例子一样,分支结点的键和指针槽也没有必要全部占用。不过,当n=3时,一个内部结点至少要出现一个键和两个指针。元素缺失最极端的情形就是键值只有57,而指针也仅使用前两个,在这种情况下,第一个指针对应于小于57的键值,而第二个指针对应于大于等于57的键值。

b-tree-index2

完整树举例

如下图所示为一棵完整的三层B+树,我们假定数据文件记录的键是2~47之间的所有素数。注意,这些值在叶结点中按顺序出现一次。所有叶结点都有两个或3个键-指针对,还有一个指向序列中下一叶结点的指针。当我们从左到右去看叶结点时,所有键都是排好序的。根结点仅有两个指针,恰好是允许的最小数目,尽管至多可有4个指针。

根结点中的某个键将通过第一个指针访问到的键值与通过第二个指针访问到的键值分隔开来。也就是说,不超过12的键值可通过根结点的第一个子树找到;大于等于13的键值可通过第二个子树找到。

如果我们看根结点的第一个具有键值7的分支结点,会发现它有两个指针,一个通向小于7的键,而另一个通向大于等于7的键。注意,该结点的第二个指针只能使我们找到键7和11,而非所有大于7的键,比如键13(虽然我们可以通过叶结点中指向下一个块的指针找到那些更大的键)。

最后,根结点的第二个分支结点的4个指针槽都被使用。第一个指针将我们引向一些键值小于23的键,即13、17和19。第二个指针将我们引向键值大于等于23而小于31的所有键;第三个指针将我们引向键值大于等于31而小于43的所有键;而第四个指针将我们引向一些键值大于等于43的键(在这个例子中,是所有的键)。

b-tree-index3

带重复键树举例

如下图所示,树中有重复键值。具体来说:键11已被键13替换;键19、29和31全部被键23替换。这样就造成根结点的键是17而不是13。原因在于,虽然13是第二个子树根结点中最小的键,但它不是该子树的新键,因为它在根结点的第一个子树中出现过。

我们还需要对根结点的第二个子结点做些改变。第二个键改为37,因为它是第三个子结点(从左数第五个叶结点)的第一个新键。最有趣的是,第一个键现在为空,因为第二个子结点(第四个叶结点)根本就没有新键。换言之,如果查找某个键且到达根结点的第二个子结点,我们不会从该子结点的第二个子结点起开始查找。若是查找23或其他更小的值,我们应该从它的第一个子结点起开始查找,在那里我们将找到所需的记录(如果是17),或找到所需的记录的第一个(如果是23)。注意:

  • 查找13时我们不会到达根结点的第二个子结点,而是直接到第一个子结点中去查找。
  • 如果查找介于24~36之间的某个键,我们会直接到第三个叶结点中查找。但当我们连一个所需键值都找不到时,我们就知道不必继续往右查找。举例来说,如果叶结点中存在键24,它要么在第四个叶结点上,这时根结点的第二个子结点中的空键将会被24替代;要么在第五个叶结点上,这时根结点的第二个子结点的键37将被24替代。

b-tree-index4

B树范围查询

如果想在B树叶结点上找出在范围[a,b]之间的所有键值,我们通过一次查找来找出键a。不论它是否存在,我们都将到达可能出现a的叶结点,然后在该叶结点中查找键a或大于a的那些键。我们所找到的每个这样的键都有一个指针指向相应的记录,这些记录的键在所需的范围内。

如果我们没有发现大于b的键,我们就使用当前叶结点指向下一个叶结点的指针,并继续检查键和跟踪相应指针,直到我们找到一个大于b的键,这时我们停止查找;或者到了叶结点的末尾,在这种情况下,我们到达下一个叶结点且重复这个过程。

上面的查找算法当b为无穷时也有效,即项中只有一个下界而没有上界。在这种情况下,我们查找从键a可能出现的叶结点开始到最后一个叶结点的所有叶结点,如果a为-∞(即项中有一个上界而没下界),那么,在查找“负无穷”时,不论处于B树的哪个结点,我们总被引向该结点的第一个子结点,即最终将找到第一个叶结点。然后按上述过程查找,仅在超过键b时停止查找。

B树的插入

插入原则上是递归的:

  • 设法在适当的叶结点中为新键找到空闲空间,如果有的话,就把键放在那里。
  • 如果在适当的叶结点中没有空间,就把该叶结点分裂成两个,并且把其中的键分到这两个新结点中,使每个新结点有一半或刚好超过一半的键。
  • 某一层的结点分裂在其上一层看来,相当于是要在这一较高的层次上插入一个新的键-指针对。因此,我们可以在这一较高层次上逆归地使用这个插入策略:如果有空间,则插入;如果没有,则分裂这个父结点且继续向树的高层推进。
  • 例外的情况是,如果试图插入键到根结点中并且根结点没有空间,那么我们就分裂根结点成两个结点,且在更上一层创建一个新的根结点。这个新的根结点有两个刚分裂成的结点作为它的子结点。回想一下,不管n(结点中键的槽数)多大,根结点总是允许只有一个键和两个子结点。

B树的效率

每次按给定查找键值查找记录都需要从根结点一直访问到叶结点以找到指向记录的指针。因为我们只读B树的块,所以磁盘I/O数将是B树的层数加上一次(对查找而言)或两次(对插入或删除而言)处理记录本身的磁盘I/O。我们肯定会这样问:B树到底有多少层?对于典型的键、指针和块大小来说,三层就足够了,除非数据库极大。因此,我们一般取3作为B树的层数。

对于每次查找,我们甚至可以通过B树用比3次还少的磁盘I/O来实现。B树根结点块是永久地缓存在主存中的绝佳选择。如果这样,那么每次查找3层的B树只需两次磁盘读操作。实际上,在某些情况下,把B树的第二层结点块保存在缓冲区中也是合理的。这样,B树的查找就减少到一次磁盘I/O再加上处理数据文件本身所需的磁盘I/O。

原文地址:

http://19880614.blog.51cto.com/4202939/1310014

» 声明:本站文章源于个人经验总结或书籍、互联网转载,内容仅用于个人学习,请勿转载,否则后果自负!

给我留言

留言无头像?