B 树¶
1 B树使用场景¶
二叉树、平衡二叉树适用于存储在计算机内存中较小的文件，统称为内查找法。若文件很大且存放于外存进行查找时，这些查找方法就不适用了。内查找法都以结点为单位进行查找，这样需要反复地进行内、外存的交换，是很费时的。1970 年，R.Bayer 和E.Mccreight 提出了一种适用于外查找的平衡多叉树——B 树，磁盘管理系统中的目录管理，以及数据库系统中的索引组织多数都采用 B树这种数据结构。
2 B树定义¶
- 树的阶：树中节点最大子树个数为m，则称为m阶数。
- 关键字（key）：B 树中一个节点可以有多个关键字，此关键字就相当于二叉树节点的值。关键字数量满足关系
[m/2]<=n<=m-1 - 一棵m阶的B树，或为空树，或为满足下列特性的m叉树：
- 树中每个结点至多有m棵子树：
- 若根结点不是叶子结点，则至少有两棵子树；
- 除根之外的所有非终端结点至少有m/2棵子树；
- 所有的叶子结点都出现在同一层次上，并且不带信息，通常称为失败结点（失败结点并不存在，指向这些结点的指针为空。引入失败结点是为了便于分析B树的查找性能)：
- 所有的非终端结点最多有m-1个关键字，结点的结构如图7.21所示。
3 B树查询¶
3.1 算法步骤¶
将给定值 key 与根结点的各个关键字 K1,K2,, 飞（1≤j≤m-1) 进行比较，由于该关键字序列是有序的，所以查找时可采用顺序查找，也可采用折半查找。查找时：
1. 若key=Ki（1≤i≤j),则查找成功；
2. 若key<K1,则顺着指针P0所指向的子树继续向下查找；
3. 若Ki<key
4 B树插入¶
4.1 插入规则¶
- 每次插入一个关键字不是在树中添加一个叶子结点，而是首先在最低层的某个非终端结点中添加一个关键字。（关键字个数区间为
[m/2]<=n<=m-1） - 当结点插入关键字后数量n满足
[m/2]<=n<=m-1，则插入成功。 - 当结点插入关键字后数量n不满足
[m/2]<=n<=m-1，则需要在同一层进行结点分裂。
4.2 节点分裂¶
- 以中间关键字为界把结点一分为二，成为两个结点，并把中间关键字向上插入到双亲结点上。
- 若双亲结点已满，则采用同样的方法继续分解。
- 最坏的情况下，一直分解到树根结点，这时B-树高度增加1。
4.3 算法步骤¶
①在B-树中查找给定关键字的记录，若查找成功，则插入操作失败；否则将新记录作为空指针p插人到查找失败的叶子结点的上一层结点（由q指向）中。
②若插入新记录和空指针后，q指向的结点的关键字个数未超过m-1,则插入操作成功，否则转入步骤③。
③以该结点的第[m/2]个关键字K[m/2]为拆分点，将该结点分成3个部分：K[m/2]左边部分、[Km/2]、[Km/2]右边部分。K[m/2]左边部分仍然保留在原结点中；K[m/2]右边部分存放在一个新创建的结点（由p指向）中；关键字值为K[m/2]的记录和指针p插入到q的双亲结点中。因q的双亲结点增加一个新的记录，所以必须对q的双亲结点重复②和③的操作，依次类推，直至由q指向的结点是根结点，转入步骤④。
④由于根结点无双亲，则由其分裂产生的两个结点的指针p和q,以及关键字为K[m/2]的记录构成一个新的根结点。此时，B树的高度增加1。
5 B树的删除¶
5.1 删除规则¶
- m阶B树的删除操作是在B-树的某个结点中删除指定的关键字及其邻近的一个指针，删除后应该进行调整使该树仍然满足B树的定义，也就是要保证每个结点的关键字数目范围为
[m/2]<=n<=m-1。 - 删除记录后，结点的关键字个数如果小于
[m/2-1],则要进行“合并”结点的操作。 - 除了删除记录，还要删除该记录邻近的指针。
- 若该结点为最下层的非终端结点，由于其指针均为空，删除后不会影响其他结点，可直接删除；
- 若该结点不是最下层的非终端结点，邻近的指针则指向一棵子树，不可直接删除。此时可做如下处理：将要删除记录用其右(左)边邻近指针指向的子树中关键字最小（大）的记录（该记录必定在最下层的非终端结点中)替换。采取这种方法进行处理，无论要删除的记录所在的结点是否为最下层的非终端结点，都可归结为在最下层的非终端结点中删除记录的情况。