B 树和 B 树

B 树可视化：https://www.cs.usfca.edu/~galles/visualization/BTree.html

B 树及其基本操作

B 树，又称多路平衡查找树，B 树中所有结点的孩子个数的最大值称为 B 树的阶，通常用 表示。一棵 阶 B 树或为空树，或为满足如下特性的 叉树：

1. 树中每个结点至多有 棵子树，即至多含有 个关键字。
2. 若根结点不是终端结点，则至少有两棵子树。
3. 除根结点外的所有非叶结点至少有 棵子树，即至少含有 个关键字。（保证查找效率）
4. 所有非叶结点的结构如下：[ | | | | | | | | ]。其中，#card=math&code=Ki%5C%20%28i%3D1%2C2%2C%5Ccdots%20%2Cn%29&id=y4wvr) 为结点的关键字，且满足 ；#card=math&code=P_i%5C%20%28i%3D0%2C1%2C%5Ccdots%20%2Cn%29&id=KvSSR) 为指向子树根结点的指针，且指针  所指子树中所有结点的关键字均小于 ， 所指子树中所有结点的关键字均大于 ，#card=math&code=n%20%5C%20%28%5Cleft%20%5Clceil%20%5Cfrac%7Bm%7D%7B2%7D%20%5Cright%20%5Crceil%20-1%5Cle%20n%20%5Cle%20m-1%29&id=YG6HN) 为结点中关键字的个数。
5. 所有的叶结点都出现在同一层次上，并且不带信息（可以视为外部结点或类似于折半查找判定树的查找失败结点，实际上这些结点不存在，指向这些结点的指针为空）。（对于任何一个结点，其所有子树的高度都要相同）

阶 B 树的核心特性：

1. 根节点的子树数 ，关键字数 ；其他结点的子树数 ；关键字数
2. 对于任何一个结点，其所有子树的高度都要相同

B 树是所有结点的平衡因子均等于 0 的多路平衡查找树。

下图所示的 B 树中所有结点的最大孩子数 ，因此它是一棵 5 阶 B 树，在 阶 B 树中结点最多可以有 个孩子。

可以借助该实例来分析上述性质：

1. 结点的孩子个数等于该节点中关键字个数加 1。
2. 如果根结点没有关键字就没有子树，此时 B 树为空；如果根节点有关键字，则其子树必然大于等于两棵，因为子树个数等于关键字个数加 1。
3. 除根结点外的所有非终端结点至少有 棵子树（即至少有 个关键字），至多有 5 棵子树（即至多有 4 个关键字）。
4. 结点中关键字从左到右递增有序，关键字两侧均有指向子树的指针，左边指针所指向子树的所有关键字均小于该关键字，右边指针所指子树的所有关键字均大于该关键字。或者看成下层结点关键字总是落在由上层结点关键字所划分的区间内，如第二层最左结点的关键字划分成了 3 个区间：%2C(5%2C%2011)%2C(11%2C%20%2B%5Cinfty)#card=math&code=%28-%5Cinfty%2C%205%29%2C%285%2C%2011%29%2C%2811%2C%20%2B%5Cinfty%29&id=DxYfJ)，该结点 3 个指针所指子树的关键字均落在这 3 个区间内。
5. 所有叶结点均在第 4 层，代表查找失败的位置。

   B 树的高度（磁盘存取次数）

   B 树中的大部分操作所需的磁盘存取次数与 B 树的高度成正比。

下面来分析 B 树在不同情况下的高度。当然，首先应该明确 B 树的高度不包括最后的不带任何信息的叶结点所处的那一层（有些书对 B 树的高度的定义中，包含最后的那一层）。

若 ，则对任意一棵包含 个关键字、高度为 、阶数为 的 B 树：

1. 因为 B 树中每个结点最多有 棵子树， 个关键字，所以在一棵高度为 的 阶 B 树中关键字的个数应满足 (1%2Bm%2Bm%5E2%2B%5Ccdots%20%2Bm%5E%7Bh-1%7D%3Dm%5Eh-1)#card=math&code=n%5Cle%20%28m-1%29%281%2Bm%2Bm%5E2%2B%5Ccdots%20%2Bm%5E%7Bh-1%7D%3Dm%5Eh-1%29&id=qCeW2) ，因此有 %7D#card=math&code=h%5Cge%20%5Clog_%7Bm%7D%7B%28n%2B1%29%7D&id=C1JDz) 。最小高度
2. 若让每个结点中的关键字个数达到最少，则容纳同样多关键字的 B 树的高度达到最大。由 B 树的定义：第一层至少有 1 个结点；第二层至少有 2 个结点；除根结点外的每个非终端结点至少有 棵子树，则第三层至少有 个结点……第 层至少有 %5E%7Bh-1%7D#card=math&code=2%28%5Cleft%20%5Clceil%20%5Cfrac%7Bm%7D%7B2%7D%20%5Cright%20%5Crceil%20%29%5E%7Bh-1%7D&id=pVJg9) 个结点，注意到第 层是不包含任何信息的叶结点。对于关键字个数为 的 B 树，叶结点即查找不成功的结点为 ，由此有 %5E%7Bh-1%7D#card=math&code=n%2B%201%5Cge%202%28%5Cleft%20%5Clceil%20%5Cfrac%7Bm%7D%7B2%7D%20%5Cright%20%5Crceil%20%29%5E%7Bh-1%7D&id=FZk7J)，即 。

故含 个关键字、高度为 、阶数为 的 B 树有：

B 树的查找

在 B 树上进行查找与二叉查找树很相似，只是每个结点都是多个关键字的有序表，在每个结点上所做的不是两路分支决定，而是根据该结点的子树所做的多路分支决定。B 树的查找包含两个基本操作：

1. 在B树中找结点；
2. 在结点内找关键字。

由于 B 树常存储在磁盘上，因此前一个查找操作是在磁盘上进行的，而后一个查找操作是在内存中进行的，即在找到目标结点后，先将结点信息读入内存，然后在结点内采用顺序查找法或折半查找法。在 B 树上查找到某个结点后，先在有序表中进行查找，若找到则查找成功，否则按照对应的指针信息到所指的子树中去查找。查找到叶结点时（对应指针为空指针），则说明树中没有对应的关键字，查找失败。

B 树的插入

与二叉查找树的插入操作相比，B树的插入操作要复杂得多。在二叉查找树中，仅需查找到需插入的终端结点的位置。但是,在 B 树中找到插入的位置后，并不能简单地将其添加到终端结点中，因为此时可能会导致整棵树不再满足 B 树定义中的要求。将关键字 key 插入 B 树的过程如下：

1. 定位。利用前述的 B 树查找算法，找出插入该关键字的最低层中的某个非叶结点（在 B 树中查找 key 时，会找到表示查找失败的叶结点，这样就确定了最底层非叶结点的插入位置。注意：插入位置一定是最低层中的某个非叶结点）。
2. 插入。在 B 树中，每个非失败结点的关键字个数都在区间 内。插入后的结点关键字个数小于 ，可以直接插入；插入后检查被插入结点内关键字的个数，当插入后的结点关键字个数大于 时，必须对结点进行分裂。

分裂的方法是：取一个新结点，在插入 key 后的原结点，从中间位置 将其中的关键字分为两部分，左部分包含的关键字放在原结点中，右部分包含的关键字放到新结点中，中间位置 的结点插入原结点的父结点。若此时导致其父结点的关键字个数也超过了上限，则继续进行这种分裂操作，直至这个过程传到根结点为止，进而导致 B 树高度增 1。

B 树的删除

B 树中的删除操作与插入操作类似，但要稍微复杂一些，即要使得删除后的结点中的关键字个数 ，因此将涉及结点的“合并”问题。

当被删关键字 不在终端结点（最低层非叶结点）中时，可以用 的前驱（或后继） 来替代 ，然后在相应的结点中删除 ， 关键字 必定落在某个终端结点中，则转换成了被删关键字在终端结点中的情形。

• 直接前驱：当前关键字左侧指针所指子树中“最右下”的元素。
• 直接后继：当前关键字右侧指针所指子树中“最左下”的元素。

当被删关键字在终端结点（最低层非叶结点）中时，有下列三种情况：

1. 直接删除关键字。若被删除关键字所在结点的关键字个数 ，表明删除该关键字后仍满足 B 树的定义，则直接删去该关键字。
2. 兄弟够借。若被删除关键字所在结点删除前的关键字个数，且与此结点相邻的右（或左）兄弟结点的关键字个数，则需要调整该结点、右（或左）兄弟结点及其双亲结点（父子换位法），以达到新的平衡。当右兄弟很宽裕时，用当前结点的后继、后继的后继来填补空缺；当左兄弟很宽裕时，用当前结点的前驱、前驱的前驱来填补空缺。
3. 兄弟不够借。若被删除关键字所在结点删除前的关键字个数 ，且此时与该结点相邻的左、右兄弟结点的关键字个数均 ，则将关键字删除后与左（或右）兄弟结点及双亲结点中的关键字进行合并。在合并过程中，双亲结点中的关键字个数会减 1 。 若其双亲结点是根结点且关键字个数减少至 0 （根结点关键字个数为 1 时，有 2 棵子树），则直接将根结点删除，合并后的新结点成为根；若双亲结点不是根结点，且关键字个数减少到 ，则又要与它自己的兄弟结点进行调整或合并操作，并重复上述步骤，直至符合 B 树的要求为止。

   B+ 树的基本概念

   B+ 树是应数据库所需而出现的一种 B 树的变形树。

一棵 阶的 B+ 树需满足下列条件：

1. 每个分支结点最多有 棵子树（孩子结点）。
2. 非叶根结点至少有两棵子树，其他每个分支结点至少有 棵子树。
3. 结点的子树个数与关键字个数相等。
4. 所有叶结点包含全部关键字及指向相应记录的指针，叶结点中将关键字按大小顺序排列，并且相邻叶结点按大小顺序相互链接起来。(支持顺序查找)
5. 所有分支结点（可视为索引的索引）中仅包含它的各个子结点（即下一级的索引块）中关键字的最大值及指向其子结点的指针。（类似分块查找）

阶的 B+ 树与 阶的 B 树的主要差异如下：

1. 在 B+ 树中，具有 个关键字的结点只含有 棵子树，即每个关键字对应一棵子树；而在 B 树中，具有 个关键字的结点含有 棵子树。
2. 在 B+ 树中，每个结点（非根内部结点）的关键字个数 的范围是 （根结点：）；在 B 树中，每个结点（非根内部结点）的关键字个数 的范围是 （根结点：）。
3. 在 B+ 树中，叶结点包含信息，所有非叶结点仅起索引作用，非叶结点中的每个索引项只含有对应子树的最大关键字和指向该子树的指针，不含有该关键字对应记录的存储地址。
4. 在 B+ 树中，叶结点包含了全部关键字，即在非叶结点中出现的关键字也会出现在叶结点中；而在 B 树中，叶结点包含的关键字和其他结点包含的关键字是不重复的。

分支结点的某个关键字是其子树中最大关键字的副本。通常在 B+ 树中有两个头指针：一个指向根结点，另一个指向关键字最小的叶结点。因此，可以对 B+ 树进行两种查找运算：一种是从最小关键字开始的顺序查找，另一种是从根结点开始的多路查找。

B+ 树的查找、插入和删除操作和 B 树的基本类似。只是在查找过程中，非叶结点上的关键字值等于给定值时并不终止，而是继续向下查找，直到叶结点上的该关键字为止。所以，在 B+ 树中查找时，无论查找成功与否，每次查找都是一条从根结点到叶结点的路径。

在 B+ 树中，非叶结点不含有该关键字对应记录的存储地址。可以使一个磁盘块可以包含更多个关键字，使得 B+ 树的阶更大，树高更矮，读磁盘次数更少，查找更快。