5、MySQL为什么使用 B+树 来作索引【高频】
- 首先，B树其实就是多叉平衡树，它最多有 M 个子节点，一个节点内最多有 M-1 个数据，每个数据都由 索引 和 记录 组成。相比于平衡二叉树，B树的高度更小，从而减少IO次数。但它也有很大的问题：为了查询某个记录，B树每次IO都需要把一个节点内的数据加载到内存中，与目标的索引进行比对，这会占用内存空间
- B+树其实就是B树的升级：
- 只有叶子节点才会存放 索引 和 记录，并形成一条链表；而非叶子节点只存放索引
- 所有的索引和记录都统一汇集到叶子节点中，形成一条链表
因此，对于单点查询、范围查询、插入删除，B+树都拥有更高的性能
- 单点查询：
- B 树进行单个索引查询时，最快可以在 O(1) 的时间内就查到，但有时需要访问到叶子节点才能找到索引。所以 B 树的查询效率 波动较大。平均来看，会比 B+ 树稍快一些。
- 但是，如果数据量相同，B+树的一个节点内可以存放更多的索引，因此 B+ 树比 B 树高度更小，查询底层节点的磁盘 I/O次数会更少。
- 范围查询：
- B+ 树所有叶子节点间有一个链表进行连接，所以可以直接在链表上进行范围查询，而 B 树只能通过一个节点一个节点的比对，，范围查询效率不如 B+ 树。
- 所以 对于大量的单个索引查询的场景，可以考虑 B 树，比如nosql的MongoDB；存在大量范围检索的场景，适合使用 B+树，比如数据库
- 删除和插入效率：
- 由于B+所有的记录 都保存在叶子节点中，而非叶子节点中只有一部分记录的索引。也就是说，B+树的叶子节点中有很多冗余节点。所以，当删除一个索引时，往往只需要在叶子节点中移除这个节点，非叶子节点并不需要做出调整 或者只需要做一些很小的调整；插入也是同样，就算节点饱和，存在节点的分裂，但是最多只涉及树的一条路径。
- 而 B树的所有节点既存索引，又存记录，删除和插入节点的时候树形的变化非常复杂