面试必答题：B树、B树、B+树、B*树图文详解

B树

B树又叫二叉搜索树，倒排树结构。如下图所示

特点：

• 所有非午夜节点最多有两个子节点树（左子树和右子树）。
• 所有节点都存储关键字。节点
• 的左右子节点小于左节点，大于右节点。

缺点：

由于二叉搜索树没有平衡算法，在某些特殊情况下二叉搜索树就相当于线性树。当出现愚蠢的情况时，设计师会自然而然地降低树的高度。可以提高搜索效率。那么如何解决树高降低的问题呢？基于此，设计者在二叉树中添加了平衡算法，创建了平衡树。

二叉搜索树的查询原理是从根节点开始，匹配根节点。如果小于根节点，则插入一个左子节点。如果大于根节点，则输入正确的子节点。按照这个逻辑依次找到就可以了。后退。

另一方面，树的高度也影响查询的效率。设计师如何解决这个问题呢？
假设在大规模数据存储中实现索引查询的实际场景中，树节点中存储的元素数量是有限的。即使存储在平衡二叉树中，当存储大量数据时也会导致二叉平衡查找。由于树深度过大，树结构导致磁盘I/O读写过于频繁，进而导致查询效率低下。那么，如何减少树的深度（当然不减少要查询的数据量），基本思想如下：使用多分叉的树结构（由于树节点的元素数量有限） ，当然这个节点的子树数量也是有限的）。在此假设下，此类数据结构为 B-、B+ 和 B*。多路径搜索树不再只是双向的。

所谓平衡，就是增加了平衡算法。 B树经过多次插入和删除后，会产生不同的结构。极值点是线性无意义树的出现。通过平衡算法（左、右），使树中节点均匀分布，使得树搜索算法相当于二分搜索。因此，需要保持平衡，提高树的搜索效率；另一个是降低树的高度。

B 树

基于树高缩减，B 树是一种多向搜索树，不是二叉树。如下图所示：

属性：

• 所有非叶子节点最多有M个子节点（且M>2）。
• 根节点的子节点数量为[2, M]，其他非叶子节点的子节点数量为[M/2, M]。
• 每个节点至少存储M/2-1（向上取整），最多M-1个关键字； （至少 2 个关键字）。
• 非页面节点中的关键字数量=指向children的指针数量-1。
• 非页面节点关键字按照从左到右、从大到小的顺序排序。即A[1]