索引的本质

索引的本质

索引是帮助MySQL高效获取数据的排好序的数据结构。

数据结构角度

在了解B+树前，我们先需要了解一下二叉树。B+树是由二叉查找树，再由平衡二叉树，B树演化而来的。

二叉查找树

若我们的索引采用二叉树这样的数据结构，会存在什么问题呢？

图一

因为二叉查找树可以任意地构造，同样是2、3、5、6、7、8这五个数字，也可以按照以下的方式建立二叉查找树。

图二

相比图一，图二已经演变成链表。显然这棵二叉查找树的查询效率就低了。因此若想最大性能地构造一棵二叉查找树，需要这棵二叉查找树是平衡的，从而引出了新的定义——平衡二叉树，或称为AVL树。

AVL树

1. 对于平衡二叉树的查询速度的确很快，但是维护一棵平衡二叉树的代价是非常大的。通常来说，需要1次或多次左旋和右旋来得到插入或更新后树的平衡性。

2. 时间复杂度和树高相关。树有多高就需要检索多少次，每个节点的读取，都对应一次磁盘 IO 操作。树的高度就等于每次查询数据时磁盘 IO 操作的次数。磁盘每次寻道时间为10ms，在表数据量大时，查询性能就会很差。（1百万的数据量，log2n约等于20次磁盘IO，时间20*10=0.2s）

3. 平衡二叉树不支持范围查询快速查找，范围查询时需要从根节点多次遍历，查询效率不高。

B+树

具体可参考链接

参考链接 1
参考链接 2
参考链接 4
MySQL索引底层：B+树详解
MySQL底层数据结构的演变
MySQL索引背后的数据结构及算法原理
MySQL索引原理及慢查询优化