B树和B+树的总结

B树

为什么要B树

磁盘中有两个机械运动的部分,分别是盘片旋转和磁臂移动。盘片旋转就是我们市面上所提到的多少转每分钟,而磁盘移动则是在盘片旋转到指定位置以后,移动磁臂后开始进行数据的读写。那么这就存在一个定位到磁盘中的块的过程,而定位是磁盘的存取中花费时间比较大的一块,毕竟机械运动花费的时候要远远大于电子运动的时间。当大规模数据存储到磁盘中的时候,显然定位是一个非常花费时间的过程,但是我们可以通过B树进行优化,提高磁盘读取时定位的效率。

为什么B类树可以进行优化呢?我们可以根据B类树的特点,构造一个多阶的B类树,然后在尽量多的在结点上存储相关的信息,保证层数尽量的少,以便后面我们可以更快的找到信息,磁盘的I/O操作也少一些,而且B类树是平衡树,每个结点到叶子结点的高度都是相同,这也保证了每个查询是稳定的。

简介

这里的B树,也就是英文中的B-Tree,一个 m 阶的B树满足以下条件:

  1. 每个结点至多拥有m棵子树;
  2. 根结点至少拥有两颗子树(存在子树的情况下);
  3. 除了根结点以外,其余每个分支结点至少拥有 m/2 棵子树;
  4. 所有的叶结点都在同一层上;
  5. 有 k 棵子树的分支结点则存在 k-1 个关键码,关键码按照递增次序进行排列;
  6. 关键字数量需要满足ceil(m/2)-1 <= n <= m-1;

举个栗子:

B树上大部分的操作所需要的磁盘存取次数和B树的高度是成正比的,在B树中可以检查多个子结点,由于在一棵树中检查任意一个结点都需要一次磁盘访问,所以B树避免了大量的磁盘访问。

操作

既然是树,那么必不可少的操作就是插入和删除,这也是B树和其它数据结构不同的地方,当然了,还有必不可少的搜索,分享一个对B树的操作进行可视化的网址,它是由usfca提供的。

假定对高度为h的m阶B树进行操作。

插入

新结点一般插在第h层,通过搜索找到对应的结点进行插入,那么根据即将插入的结点的数量又分为下面几种情况。

  • 如果该结点的关键字个数没有到达m-1个,那么直接插入即可;
  • 如果该结点的关键字个数已经到达了m-1个,那么根据B树的性质显然无法满足,需要将其进行分裂。分裂的规则是该结点分成两半,将中间的关键字进行提升,加入到父亲结点中,但是这又可能存在父亲结点也满员的情况,则不得不向上进行回溯,甚至是要对根结点进行分裂,那么整棵树都加了一层。

其过程如下:

删除

同样的,我们需要先通过搜索找到相应的值,存在则进行删除,需要考虑删除以后的情况,

  • 如果该结点拥有关键字数量仍然满足B树性质,则不做任何处理;
  • 如果该结点在删除关键字以后不满足B树的性质(关键字没有到达ceil(m/2)-1的数量),则需要向兄弟结点借关键字,这有分为兄弟结点的关键字数量是否足够的情况。
    • 如果兄弟结点的关键字足够借给该结点,则过程为将父亲结点的关键字下移,兄弟结点的关键字上移;
    • 如果兄弟结点的关键字在借出去以后也无法满足情况,即之前兄弟结点的关键字的数量为ceil(m/2)-1,借的一方的关键字数量为ceil(m/2)-2的情况,那么我们可以将该结点合并到兄弟结点中,合并之后的子结点数量少了一个,则需要将父亲结点的关键字下放,如果父亲结点不满足性质,则向上回溯;
  • 其余情况参照BST中的删除。

具体实现算法如下:

删除:

B树元素的删除操作与插入操作类似,但是却要麻烦,因为得分两种情况处理。
(1)寻找到存在这个元素,而且这个元素所在是叶子节点(即它的孩子为空),直接对其进行删除,之后再判断是否小于B树规则中要求的最小的关键字个数(ceil(m/2) – 1)。如果小于,那就调用合并函数。
(2)如果寻找到的这个元素是非叶子节点的元素,通过寻找比该元素小的最大元素(该元素肯定为叶子节点),把该元素直接赋值给要删除的元素,再在叶子节点处进行(1)中的操作。

 

合并:

思路还是挺清晰的,首先先向兄弟结点(优先向左兄弟节点借,如果左兄弟节点不存在,那么再向右兄弟节点借)借元素,如果兄弟能够借给你元素的话(即借了你之后并不会小于最少的关键字数),那么直接从兄弟那里取元素(通过与父亲节点进行交换来实现),否则,和兄弟合并。

合并其实是分裂反过来的情况,从父亲结点那里取出一个key值介于要合并的两个结点之间的元素,插入左部分最末尾处,同时右部分插到左部分后面,然后父亲结点元素依次往前挪。从而实现合并操作。之后,也必须对父亲结点进行判断是否小于最小的关键字数,如果也小于,对父亲节点进行递归合并操作。

 

其过程如下:

B 树

为什么要B 树

由于B 树的数据都存储在叶子结点中,分支结点均为索引,方便扫库,只需要扫一遍叶子结点即可,但是B树因为其分支结点同样存储着数据,我们要找到具体的数据,需要进行一次中序遍历按序来扫,所以B 树更加适合在区间查询的情况,所以通常B 树用于数据库索引,而B树则常用于文件索引。

简介

同样的,以一个m阶树为例:

  1. 根结点只有一个,分支数量范围为[2,m];
  2. 分支结点,每个结点包含分支数范围为[ceil(m/2), m];
  3. 分支结点的关键字数量等于其子分支的数量减一,关键字的数量范围为[ceil(m/2)-1, m-1],关键字顺序递增;
  4. 所有叶子结点都在同一层;

操作

其操作和B树的操作是类似的,不过需要注意的是,在增加值的时候,如果存在满员的情况,将选择结点中的值作为新的索引,还有在删除值的时候,索引中的关键字并不会删除,也不会存在父亲结点的关键字下沉的情况,因为那只是索引。

B树和B 树的区别

这都是由于B 树和B具有这不同的存储结构所造成的区别,以一个m阶树为例。

  1. 关键字的数量不同;B 树中分支结点有m个关键字,其叶子结点也有m个,其关键字只是起到了一个索引的作用,但是B树虽然也有m个子结点,但是其只拥有m-1个关键字。
  2. 存储的位置不同;B 树中的数据都存储在叶子结点上,也就是其所有叶子结点的数据组合起来就是完整的数据,但是B树的数据存储在每一个结点中,并不仅仅存储在叶子结点上。
  3. 分支结点的构造不同;B 树的分支结点仅仅存储着关键字信息和儿子的指针(这里的指针指的是磁盘块的偏移量),也就是说内部结点仅仅包含着索引信息。
  4. 查询不同;B树在找到具体的数值以后,则结束,而B 树则需要通过索引找到叶子结点中的数据才结束,也就是说B 树的搜索过程中走了一条从根结点到叶子结点的路径。

 

 

如图所示,区别有以下两点:

1. B 树中只有叶子节点会带有指向记录的指针(ROWID),而B树则所有节点都带有,在内部节点出现的索引项不会再出现在叶子节点中。

2. B 树中所有叶子节点都是通过指针连接在一起,而B树不会。

 

B 树的优点:

1. 非叶子节点不会带上ROWID,这样,一个块中可以容纳更多的索引项,一是可以降低树的高度。二是一个内部节点可以定位更多的叶子节点。

2. 叶子节点之间通过指针来连接,范围扫描将十分简单,而对于B树来说,则需要在叶子节点和内部节点不停的往返移动。

 

B树的优点:

对于在内部节点的数据,可直接得到,不必根据叶子节点来定位。

 

 

 

 

 

 

 

 

 

参考链接:

http://www.cnblogs.com/George1994/p/7008732.html

http://www.cnblogs.com/ivictor/p/5849061.html

http://www.cnblogs.com/QG-Hothoren/p/4564721.html

 

 

Leave a Reply

Your email address will not be published.