B 树
相比二叉搜索树，B 树（B-tree）或称 B-树中每一个节点未必只有两个分叉（实际上，可以拥有更多的分叉），其次，所有底层节点的深度都是完全一致的，从这个意义上讲，它不失为一种理想平衡的搜索树。
从整体上看，B 树会显得更宽、更矮。
由于 B 树也属于平衡搜索树，所以它也具有某种方法来自平衡。
B 树可以理解为是平衡的多路（multi-way）搜索树。
若将多路搜索树中的每一个节点称作超级节点，那么每一个超级节点都可以看成是由若干个二路节点经过适当的合并以后得到的，具体来说：
- 每 2 代合并：4 路
- 每 3 代合并：8 路
- ...
- 每 \(d\) 代合并：\(m=2^d\) 路，\(m-1\) 个关键码
从上可以看出，B 树在逻辑上与 BBST 完全等价。但 B 树也有其存在的原因，具体来说，多级存储系统中使用 B 树，可针对外部查找，大大减少 I/O 次数。
我们知道，二叉搜索树的查找的逐层递进的，其最坏时间复杂度为 \(O(h)\)，\(h\) 为树的高度，注意这里每访问一层实际上就是一次 I/O 操作，对于平衡二叉搜索树来说，它会适当的降低树的高度，以尽量减小最坏时间复杂度，以 AVL 树为例，若有 \(n=10^9=1G\) 个记录，那么每次查找需要 \(log_2 10^9=30\) 次 I/O 操作，每次只读出一个关键码，得不偿失。
对于以上情况，若使用 B 树，则能充分利用外存对批量访问的高效支持，将此特点转化为优点，每下降一层，都以超级节点为单位，读入一组关键码。
所谓 \(m\) 阶 B 树，即 \(m\) 路平衡搜索树（\(m>=2\)）。
阶次 \(m\) 给出了 B 树中每个超级节点规模的上限和下限（以 \(n\) 来表示节点中所含的关键码数）：
- 上限：内部节点各有
- 不超过 \(m\) 个分支：\(A_0,A_1,A_2,...,A_n\)
- 不超过 \(m-1\) 个关键码：\(K_1<K_2<...<K_n\)
- 下限：内部节点的分支数 \(n+1\) 也不能太少
- 其余：\(\lceil m/2\rceil\leq n+1\)
- 树根：\(2\leq n+1\)
既然如此，我们也用超级节点所拥有分支数的下限和上限来命名 B 树，故亦称作 (\(\lceil m/2\rceil,m\)) 树。比如 \(m=5\) 时，每个节点的分支数自然不得超过 5，同时一般节点所拥有的分支数也不得少于 3，所以我们也可以称之为 (3, 5) 树。特别的，对于 4 阶 B 树而言，自然也可以称之为 (2, 4) 树，(2, 4) 树在 B 树中具有非常独特的作用和地位，(2, 4) 树与红黑树有不解的渊源。