千锋教育2023版Java面试宝典Java面试200题（含美团、字节、阿里大厂真

B-tree 即 B树，B 即 Balanced，平衡的意思。

B树 是一颗多路平衡查找树。

B 树又叫平衡多路查找树。一棵m阶的B 树 (m叉树)的特性如下：

1. 根节点至少有两个孩子 。
2. 每个非根节点至少有M/2（上取整）个孩子，至多有M个孩子。
3. 每个叶子节点 至少有 M/2-1（上取整）个关键字，至多有 M-1 个关键字。并以升序排列。（注：叶子节点是没有孩子）
4. key[i] 和 key[i+1] 之间的孩子节点的值介于 key[i] 和 key[i+1] 之间。
5. 所有的叶子节点都在同一层。

1.1、B树的特性

一棵m阶B树（m>=3），或是空树，或是具有如下几个特征的树：

1. 如果是根结点，则 2 <= 根结点的孩子数 <= m；（根结点至少包含一个关键字）。
2. 非叶子节点（除根结点和叶子结点外），ceil(m/2) <= 其包含的孩子数 <= m，其包含的关键字数 = 它的孩子数-1。【注：ceil(x)：向上取整】
3. 所有叶子结点都出现在同一层，ceil(m/2)-1 <= 结点包含的 关键字数 <= m - 1；
4. 每个结点中的 关键字 从小到大排列，并且非叶子结点的k-1个 关键字 ，正好是它k个孩子包含的关键字的值域分划。
5. 【即：父结点中的第i个关键字（如果存在） < 第i个孩子中的所有关键字 < 父结点中的第i+1个关键字（如果存在）】

1.2、B树的高度

对于一个m（m>=3）阶B树，假设关键字总数目为n，高度为h：

1. 根结点至少有2个孩子（根结点至少有一个关键字），因此第二层至少有两个结点；
2. 除根和叶子结点外，其他结点至少有t=ceil(m/2)个孩子（取最小时，除根结点外，其他结点包含的关键字个数为t-1）。因此，第三层至少有2t个结点（第二层每个结点包含的关键字个数为t-1），第四层至少有 2t^2 个结点（第三层每个结点包含的关键字个数为t-1），……，第h-1层至少有2t^(h-3)个结点（第h-2层每个结点包含的关键字个数为t-1）；
3. 将所有结点包含的关键字相加：

由此可知：

1. 在B树上增删改查的磁盘IO次数为为O(logtn)，CPU时间为O(mlogtn)。
2. 在关键字总数目不变的情况下，结点包含的关键字越多，B树的高度越小。这也是为什么SQL Server中应尽量以窄键建立聚集索引。因为键越小，结点可容纳的关键字越多，B树的高度越小，从而提升了查询性能。

1.3、性能分析

1. n个关键字的平衡二叉排序的高度（lgn）比B树的高度约大lgt倍。
2. 若作为在内存中使用的表结构，B树不一定比平衡二叉树好，尤其当m较大时更是如此。
3. 这是因为B树增删改查的CPU时间：O(mlogtn)=0(lgn·(m/lgt))。
4. 而m/lgt>1，因此当m较大时，O(mlogtn)比平衡二叉排序树的CPU时间O(lgn)大得多。故，若B树仅作为在内存中使用，则应取较小的m。（通常取最小值m=3，此时B树每个内部结点孩子数目可为2或3，这种3阶的B-树称为2-3树）。

1.4、B树的补充说明

1. B树的 阶数 是指 树中 的 最多子节点个数。比如，2-3树的阶是3，2-3-4树的阶是4；
2. B-树的搜索，从根结点开始，对结点内的关键字（有序）序列进行二分查找，如果命中则结束，否则进入查询关键字所属范围的儿子结点；重复，直到所对应的儿子指针为空，或已经是叶子结点；
3. 关键字集合分布在整棵树中, 即叶子节点和非叶子节点都存放数据；
4. 搜索有可能在非叶子结点结束；
5. 其搜索性能等价于在关键字全集内做一次二分查找；