这篇文章收录在我的 Github 上 algorithms-tutorial，另外记录了些算法题解，感兴趣的可以看看，转载请注明出处。
我们面临一个实际的问题：就是在大规模的数据存储中，实现数据索引查询的背景下，这样会导致二叉查找树结构由于树的深度过大而导致磁盘 I/O 读写过于频繁，进而导致查询效率低下。
那么我们需要一种机制减少树的深度：这也就是 B 树的思想，采用多叉树结构
(一) 基本概念：
m阶(m 必须是奇数) B-树是一个 m 路树 (即每个节点最多可以含有 m 个子节点)
一棵 B-树是一棵平衡的 m 路搜索树，它或者是空树，或者它一般具有以下性质：
- 根结点的儿子数为[2, M]
- 除根结点以外的非叶子节点的儿子数为[M/2, M]
- 每个结点存放至少M/2-1（取上整）和至多M-1个关键字
- 每个节点的关键字比它的子节点个数少 1 (叶结点除外)
- 所有的叶子都在同一个层级
B-树具有良好的平衡性(因为其所有的叶子都在同一个层级)
优点：保证只有少数的磁盘访问，解决数据结构不在主存中的数据存储问题。
B 树 可以为系统最优化地对大块数据进行读和写的操作，普遍运用在数据库和文件系统。
(二) 基本操作：
1、查找元素：
B-树的搜索，从根结点开始，对结点内的关键字（有序）序列进行二分查找，如果命中则结束，否则进入查询关键字所属范围的儿子结点；重复，直到所对应的儿子指针为空，或已经是叶子结点；
例如：1.在一棵 5 阶B-树中查找元素 29
4.gif
首先29比根节点值大，所以找根节点的右子数，然后再根据值得判断，发现 29 介于 28 和 48 之间，然后在从中间子树继续查找下去。
2.同样在该树查找一个不存在元素 54
5.gif
2、插入元素：
在插入一个元素到一棵 B-树中的叶子节点时(可能该树只有一个根结点)，结果导致该叶子包含的元素个数加 1。
这时候就需要讨论：
第一步：如果该节点的元素个数还没达到 m，则插入完后无需处理
比如：在 B-树中插入元素 3
14.gif
第二步：如果该节点元素个数达到 m 时，这时候将元素插入到合适的位置，将最中间的元素取出，成为该节点的父节点元素，然后将其余左右元素拆成两个新节点
比如：在 B-树中插入元素 44
13.gif
第三步刚才的操作可能导致父节点的元素个数达到 m，这时候用情况 2 迭代处理，直到如果遇到根结点元素个数达到 m，则最中间元素将成为新的根结点。
比如：在 B-树中插入元素 45
6.gif
3、删除元素：
我们需要分两种情况进行讨论：
一、如果该元素存在于叶子结点，直接删除它，无需进行其它处理。
7.gif
二、如果该元素存在于非叶子节点，那么删除它将会留下一个空位，这时候我们需要一些处理来填充该位置
因为节点的元素个数在 [M/2, M] 的范围内，所以比如这里我们以 5 阶B-树为例，判断节点元素是否充足即满足个数则至少拥有三（2 + 1）个元素的节点才算是有充足的元素。
1.如果被删元素的左子树拥有足够的元素，这时候我们只需拿左子节点的最大值元素上来填充即可
例如：在 B-树中删除元素 23
8.gif
2.当左子树不够元素而右子树元素充足时，这时候我们拿右子树的最小值元素上来进行填充
例如：在 B-树中删除元素 35
10.gif
3.当左右子树所含元素均不足时，但左子树的左边兄弟节点的元素个数充足，这时我们需要拿左边的兄弟节点来进行调整。
例如：在 B-树中删除元素 16
![Upload 12.gif failed. Please try again.]
4.当左右子树所含元素均不足时，但左子树的左边兄弟节点的元素个数也不足时，这时候我们还是拿左子树的最大值元素进行填充，之后再将该节点与其他节点合并形成新的节点。
例如：在 B-树中删除元素 40
11.gif
最大容纳量计算：
假设这是有棵 m 阶 B-树，则每层所能容纳最多元素个数为：
根节点: m - 1
level1: m(m - 1)
level2: m^2(m - 1)
...
leveln: m^n(m - 1)
因此一棵树高为 h 的 B-树最多能容纳的元素为 m^(h + 1) - 1 即(将上面式子相加)
例如：一课 5 阶 B-树的高度为 2，则该树所能容纳最多元素个数为 5^3 - 1 = 124
(三) 2-3 树：
当 m = 3 时，此时的 B-树又称为 2-3 树，因为之前实验课要求 Java 实现 2-3 树，实现细节就不细说，我放在 Github 上面，感兴趣的可以去看一看。
参考资料：
网友评论