索引的本质
2021-01-17 本文已影响0人
AD刘涛
索引的本质
索引是帮助MySQL高效获取数据的排好序的数据结构。
数据结构角度
在了解B+树前，我们先需要了解一下二叉树。B+树是由二叉查找树，再由平衡二叉树，B树演化而来的。
二叉查找树
若我们的索引采用二叉树这样的数据结构，会存在什么问题呢？
图一
因为二叉查找树可以任意地构造，同样是2、3、5、6、7、8这五个数字，也可以按照以下的方式建立二叉查找树。
图二
相比图一，图二已经演变成链表。显然这棵二叉查找树的查询效率就低了。因此若想最大性能地构造一棵二叉查找树，需要这棵二叉查找树是平衡的，从而引出了新的定义——平衡二叉树，或称为AVL树。
AVL树
-
对于平衡二叉树的查询速度的确很快，但是维护一棵平衡二叉树的代价是非常大的。通常来说，需要1次或多次左旋和右旋来得到插入或更新后树的平衡性。
-
时间复杂度和树高相关。树有多高就需要检索多少次，每个节点的读取，都对应一次磁盘 IO 操作。树的高度就等于每次查询数据时磁盘 IO 操作的次数。磁盘每次寻道时间为10ms，在表数据量大时，查询性能就会很差。（1百万的数据量，log2n约等于20次磁盘IO，时间20*10=0.2s）
-
平衡二叉树不支持范围查询快速查找，范围查询时需要从根节点多次遍历，查询效率不高。
B+树
具体可参考链接
参考链接 1
参考链接 2
参考链接 4
MySQL索引底层：B+树详解
MySQL底层数据结构的演变
MySQL索引背后的数据结构及算法原理
MySQL索引原理及慢查询优化
