6
6
2014
0

B树

1.B数B-树。(B数即B-树)

B数的数据可能很庞大,不能将所有数据都读入内存,故内存缓存B树的一部分数据。我们要尽量保证每次读入尽可能多的信息。正由于这个原因,一个结点的大小通常相当于一个完整的磁盘页。因此,一个B树结点可以拥有的子女数就由磁盘页的大小决定。

也可以说B树的设计目的:减少磁盘的读、写操作

 

(1)B数每个叶子节点具有相同的深度

(2)每个结点能包含的关键字数有一个上界和下界。这些节用B数的最小度数的固定整数t>=2来表示

  (2.1)非根结点必须至少有t-1个关键字,即每个非根结点至少有t个子女。

  (2.2)如果树非空,则根节点至少包含一个关键字。

  (2.3)每个结点可以包含至多2t-1个关键字。故一个节点内至多有2t个子女,若一个结点是满的,则它有2t-1个关键字

(3)每个结点x有以下域:

   (3.1)n[x]该结点的关键字书

   (3.2)n[x]个关键字。这n[x]个关键字以非降序排列。key1[x]<=key2[x]...

   (3.3)leaf[x],x为叶子,则为true.若为内部结点,则为false

4.每个内结点包含n[x]+1个指向子女的指针。c1[x],c2[x],...

5.关键字keyi[x]对存储在各个子树中的关键字加以分隔:若ki为存储在ci[x]为根子树的关键字中,则

k1<=key1[x]<=k2<=key2[x]......

 

B树中并非只有叶子节点才存数据,中间节点也存数据

 

2.B+树

B+数和B数的差异:

1.有n颗子树的结点中含有n个关键字。

2.所有的叶子节点中包含了全部关键字的信息,即指向含有这些关键字记录的指针。

3.所有的非终端结点看成索引部分,结点中仅含有其子树根节点的最大(或者最小)关键字。而B数非终端结点页包含了的有效信息。

why??B+数比B树更适合文件索引和数据库索引。

首先B+ B树对比二叉树:B+ B具有多个分支,相比二叉树来说深度降低,一个结点对应着一次io操作,所以深度降低,则查找一个元素降低了访盘的次数!

然后比较B+ 与 B树,由于B+树的非叶子节点只存储索引信息,而B树还存储需要查找的有信息,所以B+树一个结点的索引信息更多。如果把所有同一内部结点的关键字放在同一盘中,那么关键字数量就越多。相对IO次数就降低了。

而且,只有非终结点并没有指向文件内容,所以死任何关键字的查找都要走一条从根到叶子节点的路径,长度相同,所以效率相当。

 

3 B*-Tree

B*树是在B+树上的改进:

B+树分裂:当一个结点满时,则分配一个新的结点,将原来结点1/2的数据复制到新节点,最后在父节点中增加新节点的指针。故B+树的分裂影响原结点和父节点。

B*树的分裂:当一个结点满时,如果它下一个兄弟结点未满,那么将一部分数据移到兄弟节点中,再在原结点中插入关键字,最后修改兄弟结点的关键字(因为兄弟节点关键字范围变了)。如果兄弟也满了,则在原结点与兄弟结点之间加入新节点,原结点和兄弟结点各复制1/3的数据到新节点,最后在父节点中增加新节点的指针。

所以说B*树是一颗丰满的树。B*树保证了非叶子节点的块利用率 >= 2/3 。所以相对B+树空间利用率更高

 

 

推荐参考:

http://www.360doc.com/content/11/1103/13/6938655_161335261.shtml

Category: 算法、数据结构 | Tags: | Read Count: 1112

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com