Question

1、B 树

B 树是为磁盘或其它直接存取辅助存储设备而设计的一种平衡查找树，主要特点是降低磁盘 I/O 操作次数。

B 树以自然的方式推广二叉查找树。

B 树的分支因子由磁盘特性所决定。

2、B 数的数据结构

int n：当前存储在结点 x 中的关键字数
key[N]：n 个关键，以非降序存放
bool leaf;//TRUE:x 是叶子；FALSE:x 是内结点
node *child[N+1]：只有内结点才有。指向其 n+1 个孩子的指针。child[1].key <= key[1] <= child[2].key……

3.B 树的特征

（1）只有内结点才有指向子女的指针，且 child[1].key <= key[1] <= child[2].key……

（2）每个叶结点具有相同的深度

（3）分支因子 t>=2

（4）每个非根结点至少有 t-1 个关键字，如果是内结点，至少有 t 个子女

（5）每个结点至多有 2t-1 个关键字，如果是内结点，到多有 2t 个子女

4.B 树上的操作

B-Tree-Search(x, k)

B-Tree-Create(T)

B-Tree-Split-Child(x,i,y)

B-Tree-Insert(T,k)

B-Tree-Insert-Nonfull(x,k)

B-Tree-Delete(T,x)