数据结构---B-树

便于理解，引入多个定义，从多个角度讨论。

B-树的定义1:

 

　一棵m(m≥3)阶的B-树是满足如下性质的m叉树：

 

(1)每个结点至少包含下列数据域：

(j，P 0 ，K l ，P 1 ，K 2 ，…，K i ，P i )

其中： j为关键字总数，

K i (1≤i≤j)是关键字，关键字序列递增有序：K 1 <K 2 <…<K i

P i (0≤i≤j)是孩子指针。对于叶结点，每个P i 为空指针。

 

注意：

　①实用中为节省空间，叶结点中可省去指针域P i ，但必须在每个结点中增加一个标志域leaf，其值为真时表示叶结点，否则为内部结点。

 

　②在每个内部结点中，假设用keys(Pi)来表示子树Pi中的所有关键字，

则有：keys(P 0 )<K 1 <keys(P 1 )<K 2 <…<K i <keys(P i )

即关键字是分界点，任一关键字Ki左边子树中的所有关键字均小于K i ，右边子树中的所有关键字均大于K i 。

(2)所有叶子是在同一层上，叶子的层数为树的高度h。

 

(3)每个非根结点中所包含的关键字个数j满足：若树非空，则根至少有1个关键字，故若根不是叶子，则它至少有2棵子树。根至多有m-1个关键字，故至多有m棵子树。

 

 

B-树的定义2

 

B-树是一种平衡的多路查找树（与二叉查找树，平衡二叉树相对应而言）,它有较高的查找的效率,在文件系统中很有用.主要用于文件索引。

 

一、B-树的定义

一棵"m 阶的B树"或为空树，或为具有以下特性的 m 叉查找树：

 

以下(1)，(2)是保证其为平衡树的特性

（1）树中每个结点至多有 m 棵子树；

（2）除根以外的所有非叶结点至少有 [m/2 ]（向上取整）棵子树，根结点若是非叶结点，则至少有两棵子树；

 

补充；对于每个非叶节点，它有n个索引项/关键字，有n+1个指向子树根结点的指针；

 

以下(3)，(4)是保证其为查找树的特性

（3）所有的非叶结点中含有如下信息：

　(n,A0,(K1,D1),A1,(K2,D2),……，An-1,(Kn,Dn),An)

(Ki,Di)(i=1,…，n)为索引项，ki为索引项的关键码，Di为指向索引项内容(或记录)的指针。

Ki<Ki+1(i=1,…，n-1);

Ai(i=0,…，n) 为指向子树根结点的指针。

Ai-1 所指子树中所有索引项的关键码小于Ki(i=1,…，n)，An 所指子树中索引项的关键码大于 Kn，n(m/2-1≤n≤m-1) 为结点中索引项的个数。

 

（4）所有叶结点都在同一层上，且不含任何信息。

 

下图为一棵3阶B-树:

 

相比定义一，定义二更加具体。

 

二 B-树的特性

 

假如M为设定的非叶子结点最多子树个数，N为关键字总数；

由于限制了除根结点以外的非叶子结点，至少含有M/2个儿子，确保了结点的至少利用率，确保它为平衡查找树，所以B-树的搜索性能总是等价于二分查找（与M值无关），也就没有B 树平衡的问题, 时间复杂度： O(log m/2 n);

1.关键字集合分布在整颗树中；

2.任何一个关键字出现且只出现在一个结点中；

3.搜索有可能在非叶子结点结束；

4.由于M/2的限制，插入和删除节点后能保证B树的平衡，且非叶的非根结点一般会有指向父节点的指针，使得插入和删除更加便利。在插入结点时，如果结点已满，需要将结点分裂为两个各占M/2的结点；删除结点时，需将两个不足M/2的兄弟结点合。