B树讲解

定义：一颗B树拥有如下性质的有根树

1）每个节点有以下域

a）n[x] ：存储在节点x中的关键字数

b）n[x]个关键字，按照非降序排列

c）leaf[x]为布尔值，x为叶子则leaf[x]=True 否则为false

2）每个内节点x还包含n[x]+1个指向其子女的指针c1[x],c2[x]……C(n[x]+1)[x]。叶子没有子女

3）各关键字key[x] 之间 的子树的关键字范围 在关键字key1[x]<=c1[x]<=key2[x]之间。

4）每一个叶子有相同的深度=树的高度h

5）每一个节点能包含的关键字数有一个上界和下届。用B树的最小度数t>=2来限定。

a）每个非根必须至少 t-1 个关键字、t个子女。

b）每个非根至多2t-1关键字，所以一个关键字至多2t个子女。我们说一个节点是满的则它恰好有2t-1个关键字。

例子：当t=2时，每个非根、非叶节点可以包含的节点数为（ 1、2、3）。子女数可以为（2、3、4）。实际中采用大的多的t值。

对B树的基本操作：

搜索B树，向B树中插入关键字，B树中节点的分裂，从B树种删除关键字。

源码（C）：