（一）维基百科
在计算机科学中，B树（英语：B-tree）是一种自平衡的树，能够保持数据有序。这种数据结构能够让查找数据、顺序访问、插入数据及删除的动作，都在对数时间内完成。B树，概括来说是一个一般化的二叉查找树（binary search tree）一个节点可以拥有2个以上的子节点。与自平衡二叉查找树不同，B树适用于读写相对大的数据块的存储系统，例如磁盘。B树减少定位记录时所经历的中间过程，从而加快存取速度。B树这种数据结构可以用来描述外部存储。这种数据结构常被应用在数据库和文件系统的实现上。
B树是一种多路平衡查找树，它的每一个节点最多包含K个孩子，K被称为B树的阶。K的大小取决于磁盘页的大小。
演示地址：https://www.cs.usfca.edu/~galles/visualization/BTree.html,可以在此网站上演示查询节点、插入节点、删除节点等操作。
（二）B树特征
- 若根结点不是叶子节点则至少有两个子女。
- 每个中间节点都包含k-1个元素和k个孩子，其中 m/2 <= k <= m
- 每一个叶子节点都包含k-1个元素（关键字），其中 m/2 <= k <= m,比如5阶B树，2<=关键字个数<=4
- 所有的叶子结点都位于同一层。
- 每个节点中的元素从小到大排列，节点当中k-1个元素正好是k个孩子包含的元素的值域分划。
（三）B树搜索
以3阶的B树举例（3阶指的是每个节点最多有3个子节点）
- 每个节点占用一个盘块的磁盘空间，一个节点上有两个升序排序的关键字和三个指向子树根节点的指针，指针存储的是子节点所在磁盘块的地址。
- 两个关键词划分成的三个范围域对应三个指针指向的子树的数据的范围域。
- 以根节点为例，关键字为17和35，P1指针指向的子树的数据范围为小于17，P2指针指向的子树的数据范围为17~35，P3指针指向的子树的数据范围为大于35。
模拟查找关键字29的过程：
- 根据根节点找到磁盘块1，读入内存。【磁盘I/O操作第1次】
- 比较关键字29在区间（17,35），找到磁盘块1的指针P2。
- 根据P2指针找到磁盘块3，读入内存。【磁盘I/O操作第2次】
- 比较关键字29在区间（26,30），找到磁盘块3的指针P2。
- 根据P2指针找到磁盘块8，读入内存。【磁盘I/O操作第3次】
- 在磁盘块8中的关键字列表中找到关键字29。
分析上面过程，发现需要3次磁盘I/O操作，和3次内存查找操作。由于内存中的关键字是一个有序表结构，可以利用二分法查找提高效率。而3次磁盘I/O操作是影响整个B-Tree查找效率的决定因素。B-Tree相对于AVLTree缩减了节点个数，使每次磁盘I/O取到内存的数据都发挥了作用，从而提高了查询效率。
（四）B-树中插入关键字（构建B-树）
因为对于 m 阶的 B-树来说，在定义中规定所有的非终端结点（终端结点即叶子结点，其关键字个数为 0）中包含关键字的个数的范围是[⌈m/2⌉-1,m-1]，所以在插入新的数据元素时，首先向最底层的某个非终端结点中添加，如果该结点中的关键字个数没有超过 m-1，则直接插入成功，否则还需要继续对该结点进行处理。
假设现在图 3 的基础上插入 4 个关键字 30、26、85 和 7
图 3： 3阶B-树（深度为4，省略了叶子结点）
插入关键字 30 ：从根结点开始，由于 30 < 45，所以要插入到以 b 结点为根结点的子树中，再由于 24 < 30，插入到以 d 结点为根结点的子树中，由于 d 结点中的关键字个数小于 m-1=2，所以可以将关键字 30 直接插入到 d 结点中。结果如下图所示：
图 4 插入关键字30后的B-树
插入关键字 26：从根结点开始，经过逐个比较，最终判定 26 还是插入到 d 结点中，但是由于 d 结点中关键字的个数超过了 2，所以需要做如下操作：
- 关键字 37 及其左右两个指针存储到新的结点中，假设为 d’ 结点；
- 关键字 30 存储到其双亲结点 b 中，同时设置关键字 30 右侧的指针指向 d’；
经过以上操作后，插入 26 后的B-树为
图 5 插入关键字26后的B-树
插入关键字 85：从根结点开始，经过逐个比较，最终判定插入到 g 结点中，同样需要对 g 做分裂操作：
- 关键字 85 及其左右两个指针存储到新的结点中，假设为 g’ 结点；
- 关键字 70 存储到其双亲结点 e 中，同时设置 70 的右侧指针指向 g’ ；
经过以上操作后，插入 85 后的结果图为
图 6 插入 85 的效果图
图 6 中，由于关键字 70 调整到其双亲结点中，使得其 e 结点中的关键字个数超过了 2，所以还需进一步调整：
- 将 90 及其左右指针存储到一个新的结点中，假设为 e’ 结点；
- 关键字 70 存储到其双亲结点 a 中，同时其右侧指针指向 e’ ;
最终插入关键字 85 后的 B-树为：
图 7 插关键字85后的B-树
插入关键字 7：从根结点开始依次做判断，最终判定在 c 结点中添加，添加后发现 c 结点需要分裂，分裂规则同上面的方式一样，结果导致关键字 7 存储到其双亲结点 b 中；后 b 结点分裂，关键字 24 存储到结点 a 中；结点 a 同样需要做分裂操作，最终 B-树为：
图 8 插入关键字7后的B-树
（五）B-树中删除关键字
B树删除的一些规则
下面以5阶B树为例，介绍B树的删除操作：
原始B树结构如下图所示：
- 删除21关键字
删除21节点后，子树还剩下2两个关键字，不需要进行元素移动，所以这次删除操作直接删除21即可。
- 删除27关键字
由于27是非叶子节点，所以我们得先找出27的后继节点28，用28去替换27的位置，然后删除28即可。
然后删除28，删除后如下图：
删除后发现，当前叶子结点的记录的个数小于2，而它的兄弟结点中有3个记录（当前结点还有一个右兄弟，选择右兄弟就会出现合并结点的情况，不论选哪一个都行，只是最后B树的形态会不一样而已），我们可以从兄弟结点中借取一个key。所以父结点中的28下移，兄弟结点中的26上移,删除结束。结果如下图所示：
- 删除32关键字
删除之后，31子树只有一个关键字，所以需要进行元素移动。
当删除后，当前结点中只有一个key，而左右两边的兄弟结点中也仅有2个key，不能借了。所以只能让父结点中的30下移和这个两个孩子结点中的key合并，成为一个新的结点，当前结点的指针指向父结点。结果如下图所示:
- 删除40
删除40后当前节点的关键字数量小于2，并且兄弟结点中没有多余key的借，所以父结点中的key下移，和兄弟节点合并，合并后的指向当前结点的指针就指向了父结点，如下图：
但是上图中的41节点也不满足关键字数量大于2的限制，所以同理，父节点下移，然后和左边的兄弟节点合并成一个新的节点，如下图：
至此，合并后结点当前结点满足条件，删除结束。
上述示例中B树删除整体流程图如下：
