为什么是 B+ 树？
索引的常见模型有很多种：哈希表，有序数组，二叉搜索树等等。不过他们都有各自的局限性：
使用哈希表这种结构作为索引模型的缺点是数据在哈希表的排布不是有序的，如果要做范围查询，性能会比较差，适用于只有等值查询的场景；
有序数组在等值查询和范围查询的场景非常优秀，但是在我们向有序数组中插入一条记录时，就需要挪动后面所有的记录，复杂度为 O(N)，成本太高，有序数组索引只适用于静态存储引擎，比如你要保存的是2017年某个城市的所有人口信息，这样的数据不需要再修改，可以使用有序数组；
一棵平衡的二叉搜索树的增删改查的时间复杂度均为O(logN)，但是实际上大多数的数据库存储却并不使用二叉树。其原因是，索引不止存在于内存中，还要写到磁盘上。一棵具有 100万个节点的平衡二叉树，树的高度为 20。每向下访问到一个节点就要浪费一次磁盘 IO，很显然细长的二叉树也不是最优的方案。
为什么 B+ 树适合存储MySQL 索引？
- B+ 树很适合磁盘存储，能够充分利用局部性原理，磁盘预读；
- 很低的树高度，能够存储大量数据，极大的减少磁盘 IO；
- 索引本身占用的内存很小
- 能够很好的支持单点查询，范围查询，有序性查询；
若有收获，就点个赞吧
0 人点赞
