B树和B+树

B 树是为磁盘或其他直接存取的辅助存储设备而设计的一种平衡搜索树。B 树类似于红黑树，但它们在降低磁盘I/O操作数方面要更好一些。许多数据库系统使用 B 树或者 B 树的变种（如 B+树）来存储信息。

B 树中所有结点的孩子个数的最大值称为 B 树的阶，通常用 m 表示，一棵 m 阶 B 树或为空树，或是具有以下性质的 m 叉树：

在每个结点中含有n个关键字$key_1, key_2, …, key_n$，以非降序存放，使得$key_1\le key_2\le …\le key_n$。
关键字$key_i$对存储在各子树中的关键字范围加以分割，如果$k_i$为任意一个存储在以当前结点为根结点的子树中的关键字，则有：$k_1\le key_1\le k_2\le key_2\le …\le k_n\le key_n\le k_{n+1}$。
每个叶子结点具有相同的深度。
每个结点所包含的关键字个数有上界和下界。除了根结点以外的所有非叶子结点至少有$\lceil m/2 \rceil - 1$个关键字，至多有$m-1$个关键字。

由上述性质的第四点可知，除了根结点以外的每个内部结点至少有$\lceil m/2 \rceil $个孩子，如果树非空，根结点至少有一个关键字。一个内部结点至多可有 m 个孩子。

B 树上大部分的操作所需的磁盘存取次数与 B 树的高度是成正比的。如果$n \ge 1$，那么对任意一棵包含 n 个关键字、高度为 h、阶数为 m 的 B 树 T，有：
$$
log_m(n+1) \le h \le log_{\lceil m/2 \rceil}((n+1)/2) + 1
$$

在 B 树上进行查找与二叉搜索树类似，只是每个结点都是多个关键字的有序表，在每个结点上所做的不是两路分支决定，而是根据该结点的子树所做的多路分支决定。

B 树上的查找包含以下两个基本操作：

下面通过一个例子来说明 B 树的查找操作。假设需要在上图中的B树上查找是否存在关键字42，查找的具体步骤如下：

注：当查找到叶子结点（对应指针为空指针），则说明树中没有对应的关键字，查找失败。

下面通过一个具体的实例来总结B树插入操作的方法。（设该B树的阶数 m = 5 ）

继续插入22、97和41。由于结点中的关键字个数没有到达其最大值，因此可以直接插入。另外，B树中每个结点的关键字都是升序排列的，因此将22插在39的前面，将41和97插在39的后面。

继续插入53。注意，由于该B树的阶为5，因此每个结点最多只能有$5-1=4$个关键字，此时该结点已经有4个关键字了（一般称这种结点为满的（full）结点），因此要对该结点进行分裂（split）操作。该操作将一个满的结点按其中间关键字（median key）（位于$\lceil m/2 \rceil $处）分为两部分，左部分放在原结点处，右部分放在新结点处，中间位置的结点插入原结点的父结点（如果没有父结点就创建一个新结点）。但是如果父结点也是满的，就必须在插人新的关键字之前将其分裂，最终满结点的分裂会沿着树向上传播。

B 树中的删除操作与插入操作类似，但要稍微复杂一些，即要使得删除后的结点中的关键字个数$\ge \lceil m/2 \rceil - 1$，因此将涉及结点的合并问题。下面通过具体的实例来总结B树的删除操作。

（1）当被删除的关键字 k 不在终端结点（最低层非叶子结点）中时，可以**用 k 的前驱（或后继）k’ 来替代 k，然后在相应的结点中删除 k’**。

在上图中，首先删除关键字80（用其前驱78替代），然后在终端结点中删除78，因此只需讨论删除终端结点中关键字的情形。

（2）当被删除的关键字在终端结点中时，分下列三种情况讨论：

若被删除关键字所在的结点关键字个数$\ge \lceil m/2 \rceil $，表明删除该关键字后仍满足B树的定义，则可直接删除该关键字。
若被删除关键字所在结点删除前的关键字个数$= \lceil m/2 \rceil - 1$,且与此结点相邻的右（或左）兄弟结点的关键字个数$\ge \lceil m/2 \rceil $，则需要调整该结点、右（或左）兄弟结点及其双亲结点，以达到新的平衡。

如上图所示，当删除关键字65时，其右兄弟关键字个数$\ge \lceil m/2 \rceil $，因此将65的父结点71替换65，再用右兄弟结点中的关键字74替换父结点，最后直接删除右兄弟中的结点74。
若被删除关键字所在结点删除前的关键字个数$= \lceil m/2 \rceil - 1$,且与此结点相邻的左、右兄弟结点的关键字个数均$= \lceil m/2 \rceil - 1$，则将关键字删除后与左（或右）兄弟结点及双亲结点中的关键字进行合并。

由上图所示，当删除结点5时，其右兄弟结点的关键字个数均$= \lceil m/2 \rceil - 1$，因此先删除5，然后将60合并到65结点中。