MySQL 面试题：谈谈 MySQL 索引，B，新鲜出炉的 Java 面试真题集锦我给你们整理出来了

B 树

即二叉搜索树：

1. 所有非叶子结点至多拥有两个儿子（Left 和 Right）；

2. 所有结点存储一个关键字；

3. 非叶子结点的左指针指向小于其关键字的子树，右指针指向大于其关键字的子树；

如：

B-树

是一种多路搜索树（并不是二叉的）：

1. 定义任意非叶子结点最多只有 M 个儿子；且 M>2；

【一线大厂Java面试题解析+核心总结学习笔记+最新架构讲解视频+实战项目源码讲义】
浏览器打开：qq.cn.hn/FTf 免费领取

根结点的儿子数为[2, M]；

3. 除根结点以外的非叶子结点的儿子数为[M/2, M]；

4. 每个结点存放至少 M/2-1（取上整）和至多 M-1 个关键字；（至少 2 个关键字）

5. 非叶子结点的关键字个数=指向儿子的指针个数-1；

6. 非叶子结点的关键字：K[1], K[2], …, K[M-1]；且 K[i] < K[i+1]；

7. 非叶子结点的指针：P[1], P[2], …, P[M]；其中 P[1]指向关键字小于 K[1]的子树，P[M]指向关键字大于 K[M-1]的子树，其它 P[i]指向关键字属于(K[i-1], K[i])的子树；

8. 所有叶子结点位于同一层；

如：（M=3）

B-树的搜索，从根结点开始，对结点内的关键字（有序）序列进行二分查找，如果命中则结束，否则进入查询关键字所属范围的儿子结点；重复，直到所对应的儿子指针为空，或已经是叶子结点；

B-树的特性：

1. 关键字集合分布在整颗树中；

2. 任何一个关键字出现且只出现在一个结点中；

3. 搜索有可能在非叶子结点结束；

4. 其搜索性能等价于在关键字全集内做一次二分查找；

5. 自动层次控制；

由于限制了除根结点以外的非叶子结点，至少含有 M/2 个儿子，确保了结点的至少利用率。

所以 B-树的性能总是等价于二分查找（与 M 值无关），也就没有 B 树平衡的问题；

由于 M/2 的限制，在插入结点时，如果结点已满，需要将结点分裂为两个各占 M/2 的结点；删除结点时，需将两个不足 M/2 的兄弟结点合并；

B+树

B+树是 B-树的变体，也是一种多路搜索树：

1. 其定义基本与 B-树同，除了：

2. 非叶子结点的子树指针与关键字个数相同；

3. 非叶子结点的子树指针 P[i]，指向关键字值属于[K[i], K[i+1])的子树（B-树是开区间）；

4. 为所有叶子结点增加一个链指针；

5. 所有关键字都在叶子结点出现；

如：（M=3）

B+的搜索与 B-树也基本相同，区别是 B+树只有达到叶子结点才命中（B-树可以在非叶子结点命中），其性能也等价于在关键字全集做一次二分查找；

B+的特性：