B 树

 

    度：一个结点的子树个数称为该结点的 度 ( Degree )，一棵树的度是指该树中结点最大的 度数

    深度：结点中的 层数 是从根开始算起的，设根结点的层数为1 ，则其余结点的 层数 等于其双亲结点的层数加

1 、树中结点最大的层数称为树的 高度 ( Hgight )或 深度 ( Depth )

动态查找树主要有：二叉查找树（Binary Search Tree ），平衡二叉查找树（ Balanced Binary Search Tree ），红黑树 (Red-Black Tree ) ， B-tree/ B + -tree/ B * -tree(B~Tree)。前三者是典型的二叉查找树结构，其查找的时间复杂度 O (log 2 N ) 与树的深度相关，那么降低树的深度自然会提高查找效率。

 

但是咱们有面对这样一个实际问题：就是大规模数据存储中，实现索引查询这样一个实际背景下，树节点存储的元素数量是有限的（如果元素数量非常多的话，查找就退化成节点内部的线性查找了），这样导致二叉查找树结构由于 树的深度过大而造成磁盘I/O 读写过于频繁，进而导致查询效率低下 ，那么如何减少树的深度（当然是不能减少查询的数据量），一个基本的想法就是：采用 多叉树 结构（由于树节点元素数量是有限的，自然该节点的子树数量也就是有限的）。

 

B-tree（ B-tree 树即 B 树， B 即 Balanced ，平衡的意思）这棵神奇的树是在 Rudolf Bayer ,  Edward M. McCreight (1970)写的一篇论文《 Organization and Maintenance of Large Ordered Indices 》中首次提出的（wikipedia 中： http://en.wikipedia.org/wiki/B-tree ，阐述了B-tree 名字来源以及相关的开源地址）。

B-树，即为B树 。因为B树的原英文名称为B-tree，而国内很多人喜欢把B-tree译作B-树，其实，这是个非常不好的直译，很容易让人产生误解。如人们可能会以为B-树是一种树，而B树又是一种一种树。而事实上是， B-tree就是指的B树 。

 

 B树与红黑树最大的不同在于， B 树的结点可以有许多子女，从几个到几千个。那为什么又说  B 树与红黑树很相似呢 ? 因为与红黑树一样，一棵含 n 个结点的 B 树的高度也为 O （ lgn ），但可能比一棵红黑树的高度小许多，应为它的分支因子比较大。所 以， B 树可以在 O （ logn ）时间内，实现各种如插入（ insert ），删除（ delete ）等动态集合操作 。

 

B树的定义 ( 算法导论 )

一棵B 结 T 是具有如下性质的有根树 (  根为 root[T] ) ：

1） ：每个结点X 有以下域：

a) ：n[x] ，当前存储在结点 X 中的关键字数，

b) ：n[x] 个关键数本身，以非降序存放，因此 key1[x]<=key2[x]<=...<=key n[x] ，

c) ：leaf[x] ，是一个布尔值，如果 x 是叶子的话，则它为 TRUE ，如果 x 为一个内结点的话，则为 FALSE ，

2） ：每个内结点 X 还包含 n[x]+1 个指向其子女的指针 c1[x],c2[x],...,c(n[x]+1)[x] ，叶结点没有子女，故它们的 ci 域无定义。

3） 各关键字keyi[x] 对储在各子树中的关键字范围加以分隔：如果 ki 为存储在以 ci[x] 为根的子树中的关键字，则： k1<=key1[x]<=k2<=key2[x]<=...<=keyn[x][x]<=keyn[x]+1 。 ( 如果某个指针在节点node 最左边且不为 null ，则其指向节点的所有 key 小于 v(key 1 )，其中 v(key 1 )为 node 的第一个 key 的值 ； 如果某个指针在节点node 最右边且不为 null ，则其指向节点的所有 key 大于 v(key m )，其中 v(key m )为 node 的最后一个 key 的值 ； 如果某个指针在节点node 的左右相邻 key 分别是 key i 和key i+1 且不为null ，则其指向节点的所有 key 小于 v(key i+1 )且大于 v(key i ) )

4） 每个叶子结点具有相同的深度，即树的高度h

5） 每一个结点能包含的关键字数有一个上界和一个下界，这些界可以用一个称作B 树的最小度数的固定数 t>=2 来表示：

a） ：每个非根结点必须至少有t-1 个关键字，每个非根的内结点至少有 t 个子女，如果树是非空的，则根结点至少要包含一个关键字。

b） ：每个根结点至多可包含2t-1 个关键字，所以一个内结点至多可以包含 2t 个子女。如果说一个结点是满的，则他正好有 2t-1 个关键字

 

如下图所示，即是一棵B 树，一棵关键字为英语中辅音字母的 B 树，现在要从树种查找字母  R （包含 n[x] 个关键字的内结点 x ， x 有 n[x]+1] 个子女（也就是说，一个内结点 x 若含有 n[x] 个关键字，那么 x 将含有 n[x]+1 个子女）。所 有的叶结点都处于相同的深度，带阴影的结点为查找字母 R 时要检查的结点）：

从 上图看到，一个内结点x 若含有 n[x] 个关键字，那么 x 将含有 n[x]+1 个子女。如含有 2 个关键字 D H 的内结点有3 个子女，而含有 3 个关键字 Q T X 的内结点有4 个子女。

 

B树的定义如下：

#define m 1024

struct BTNode;
typedef struct BTNode * PBTNode;
struct BTNode{
    int keyNum;/*实际关键字个数， keyNum<m*/
    PBTNode parent;/*指向父结点 */
    PBTNode *ptr;/*子树指针向量： ptr[0]...ptr[keyNum]*/
    KeyType *key;/*关键字向量： key[0]...key[keyNum-1]*/
}

typedef struct BTNode * BTree;
typedef BTree * PBTree; 

 

 

B树的高度

B树上大部分操作所需的磁盘存取次数与 B 树的高度成正比。

定理：如果 n>=1，则对于任意一棵包含 n 个关键字、高度为 h 、最小度数为 t>=2 的 B 树 T 有：

 

如果一棵 B树的高度为 h, 其根结点包含至少一个关键字页其它结点包含至少 t-1 个关键字。这样，在深度 1 至少有 2 个结点，在深度 2 至少有 2t 个结点，在深度 3 至少有 2*t 的平方个结点，等等，直到深度 h 至少有 2*t 的 h-1 次方个结点。

关键字的个数n 满足不等式：

 

 

B树的查找

    B树的根结点始终在内存中，因而无需对根做 DISK-READ ；但是每当根节点改变时，都需要对根节点做一次 DISK-WRITE ；

任何被当做参数的结点被传递之前都要先对它做一次DISK-READ ；

搜索B 树跟搜索二叉树很相似，只是在每个结点所做的不是个二叉或者两路分支决定，而是根据该结点的子女数所做的多路分支决定，也就是在每个内结点 X 处，要做 (n[x]+1) 路的分支决定。

B-TREE-SEARCH的输入是一个指向某子树的跟结点 X 的指针，以及要在该数中搜索的一个关键字 K 。顶层调用的形式为 B-TREE-SEARCH （ root[T],k ）。如果 K 在 B 树中， B-TREE-SEARCH 就返回一个由结点 y 和使 keyi[y]=k 成立的下标 i 组成的有序对 (y,i) ，否则返回 NIL( 空指标 )。

B-TREE-SEARCH(x,k)

i=1

while (i<=n[x] && k>keyi[x])

    i+=1

if (i<=n[x] && k==keyi[x])

    return (x,i)

if (leaf[x])

    return NIL

else

    return B-TREE-SEARCH(ci[x],k)

    第1-3 行找出使 k<=keyi[x] 成立的最小下标 i, 若找不到就将 i 置为 n[x]+1 ，第 4-5 行检查是否已经找到该关键字，如果找到了就返回，第 6-9 行或者以失败结束查找，或者对子女做 DISK-READ 后进行递归查找。

 

    如上面B 树，如果要查找关键字 28 ，从根结点开始，调用 B-TREE-SEARCH （ root[T],28 ），进入函数， n[x]=2 ，第一行设置 i=1 ，第二行 while( 1<=2 && 28>17) ，则设置 i+=1 ， i=2 ，再次进行 while 判断 while( 2<=2 && 28>35) ，条件不成立，跳出循环；进行 if 判断： if( 2<=2 && 28==35) ，条件不成立没有返回； if( leaf[x] ) ，叶子结点跳转到 else 中进行递归搜索，此时 i=2 ，也就是指向模块 3 的指针 P2 。