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 棵子树；
- 所有的 叶子结点都出现在同一层次上，并且不带信息，通常称为失败结点（或者叫 NULL 结点，失败结点并不存在，指向这些结点的指针为空。引入失败结点是为了便于分析 B 树的查找性能)：
- 所有的 非终端结点最多有 m-1 个关键字，结点的结构如图 7.21 所示。其中 n 表示结点关键字数量，P 指子结点点指针，K 指关键字。
3 B 树优缺点¶
特点： 1. B 树的 插入可能会引起结点的分裂，而 删除可能会引起结点的合并。 优点： 2. B 树的高度远远小于 AVL 树和红黑树
4 B 树查询¶
4.1 算法步骤¶
将给定值 key 与根结点的各个关键字 Ki,Kj,（1≤j≤m-1) 进行比较，由于该关键字序列是有序的，所以查找时可采用顺序查找，也可采用折半查找。查找时：
1. 若 key=Ki（1≤i≤j),则查找成功；
2. 若 key<K1,则顺着指针 P0 所指向的子树继续向下查找；
3. 若 Ki<key
5 B 树插入¶
5.1 插入规则¶
- 每次插入一个关键字 不是在树中添加一个叶子结点，而是首先在 最底层的某个非终端结点中添加一个关键字。（关键字个数区间为
[m/2]<=n<=m-1） - 当结点插入关键字后数量 n 满足
[m/2]<=n<=m-1，则插入成功。 - 当结点插入关键字后数量 n 不满足
[m/2]<=n<=m-1，则需要在同一层进行结点分裂。
5.2 节点分裂¶
- 以中间关键字为界把结点一分为二，成为两个结点，并把中间关键字向上插入到双亲结点上。
- 若双亲结点已满，则采用同样的方法继续分解。
- 最坏的情况下，一直分解到树根结点，这时 B- 树高度增加 1。
5.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。
6 B 树的删除¶
6.1 删除规则¶
- m 阶 B 树的删除操作是在 B- 树的某个结点中删除指定的关键字及其邻近的一个指针，删除后应该进行调整使该树仍然满足 B 树的定义，也就是要保证每个结点的关键字数目范围为
[m/2]<=n<=m-1。 - 删除记录后，结点的关键字个数如果小于
[m/2-1],则要进行“合并”结点的操作。 - 除了删除记录，还要删除该记录邻近的指针。
- 若该结点为最下层的非终端结点，由于其指针均为空，删除后不会影响其他结点，可直接删除；
- 若该结点不是最下层的非终端结点，邻近的指针则指向一棵子树，不可直接删除。此时可做如下处理：将要删除记录用其右 (左) 边邻近指针指向的子树中关键字最小（大）的记录（该记录必定在最下层的非终端结点中) 替换。采取这种方法进行处理，无论要删除的记录所在的结点是否为最下层的非终端结点，都可归结为在最下层的非终端结点中删除记录的情况。