本文旨在对mysql的索引的系统性的聊一聊。
什么是索引
索引是一种数据结构，用于提高数据库查询的效率。它可以通过建立在表的列上的索引来加速SELECT查询操作。
索引的类别
- 聚簇索引: 聚簇索引是一种将数据存储在索引中，索引及数据, 数据及索引, 用于MySQL中InnoDB存储引擎的B+树索引结构。
- 非聚簇索引: 及数据与索引分开的都是非聚簇索引, 如二级索引, 非聚簇的联合索引等, 如MyISAM存储引擎中使用MYD和MYI分开存储数据和索引, 使用B+树索引结构但不存储数据, 使用指针跳转到数据。
不同存储引擎的索引
这里主要列举常见存储引擎:
- InnoDB: 一定有一个聚簇索引, 可以有多个二级索引。
- MyISAM: 有多个非聚簇索引通过指针跳转到数据。
- Memory: 使用Hash索引, 数据存储在内存中。
- Archive : 只有单个非聚簇索引, 不支持二级索引
- CSV : 不支持任何索引
B+树索引
MySQL中最为常用的就是InnoDB存储引擎, 它使用了B+树索引结构。
B+树是一种多路平衡查找树, 其体现了: 二叉搜索树->AVL树->B树->B+树的结构优化。
- 二叉搜索树的缺点是可能节点分布不均匀让树呈现出一种倾斜的状态, 导致查询效率趋近于链表的O(n), 因此出现了AVL树(平衡二叉搜索树)。
- AVL树的缺点是不够矮胖, 枝叶不够多, 导致高度过高, 查询效率依然不高。
- B树是一种特殊的M叉树, 其每个节点可以存储多个数据, 并且每个节点可以有多个子节点, 但其使用中序遍历会导致读取数据需要反复节点跳跃访问数据, 且每个节点内都有数据占用空间, 导致上面数据页在16KB的情况下能指向的子节点会变少, 导致树的高度变高。
- B+树是一种特殊的B树, 其每个节点只通过Hash存储索引, 数据存储在叶子节点(数据页)中, 且叶子节点之间使用双向链表连接, 内部数据之间用单向链表连接, 其叶子节点的高度相差不超过1, 且最底下的节点内有数据占用空间, 导致上面数据页在16KB的情况下能指向的子节点会变多, 导致树的高度变低。
且B+树在数据页为16KB的情况下理论上4层可以处理10亿数据, 时间复杂度为O(longN), 根节点放在内存中, 其余节点放在磁盘中, 每次查询最多需要进行3次磁盘IO, 且B+树的高度是非常稳定的, 因此B+树是一种非常优秀的索引结构。
Hash索引
Hash索引是一种在等值查询时比B+树索引更高效的索引结构, 但其缺点也十分明显:
- 范围查询效率低下会退化为O(n)
- 哈希值的计算方式导致其在大量重复的列中会产生哈希碰撞, 导致查询效率降低, 接近于链表的O(n)。
- hash是对联合索引的键合并相加进行计算, 因此无法像B+树一样使用索引的最左前缀原则。
- hash方式存储的数据是没有顺序的, ORDER BY需要对数据进行重排序, 因此无法用于排序。
其用于Memory等存储引擎中。
总结
以上就是对MySQL索引的系统性聊一聊的内容。
