MySQL 索引原理

1、数据结构

B Tree指的是Balance Tree，也就是平衡树。平衡树是一颗查找树，并且所有叶子节点位于同一层，如下：

非聚集索引树：

INNODB存储引擎

主键字段索引树：

非聚集索引树：

1、B+ Tree索引

大多数MySQL存储引擎默认都是B+ Tree，因为不需要进行全表扫描，只需要对树进行搜索即可，所以查询的速度会快很多。InnoDB 的 B+Tree 索引分为主索引和辅助索引。主索引的叶子节点 data 域记录着完整的数据记录，这种索引方式被称为聚簇索引。因为无法把数据行存放在两个不同的地方，所以一个表只能有一个聚簇索引。辅助索引的叶子节点的 data 域记录着主键的值，因此在使用辅助索引进行查找时，需要先查找到主键值，然后再到主索引中进行查找。

2、哈希索引

哈希索引能以 O(1) 时间进行查找，但是失去了有序性：

• 无法用于排序与分组；
• 只支持精确查找，无法用于部分查找和范围查找。

InnoDB 存储引擎有一个特殊的功能叫“自适应哈希索引”，当某个索引值被使用的非常频繁时，会在 B+Tree 索引之上再创建一个哈希索引，这样就让 B+Tree 索引具有哈希索引的一些优点，比如快速的哈希查找。

2、多列索引

在需要使用多个列作为条件进行查询时，使用多列索引比使用多个单列索引性能更好。

3、索引列的顺序

让选择性最强的索引列放在前面。索引的选择性是指：不重复的索引值和记录总数的比值。最大值为 1，此时每个记录都有唯一的索引与其对应。选择性越高，每个记录的区分度越高，查询效率也越高。这就是为什么一些枚举值的字段不建议建索引。

4、前缀索引

对于 BLOB、TEXT 和 VARCHAR 类型的列，合理使用前缀索引，只索引开始的部分字符。选择合适的前缀长度，既可以节省空间，也可以不用增加更多的查询成本。区分度越高性能越高，意味着重复的值就越少。

索引的优点

• 大大减少了服务器需要扫描的数据行数。
• 帮助服务器避免进行排序和分组，以及避免创建临时表（B+Tree 索引是有序的，可以用于 ORDER BY 和 GROUP BY 操作。临时表主要是在排序和分组过程中创建，不需要排序和分组，也就不需要创建临时表）。
• 将随机 I/O 变为顺序 I/O（B+Tree 索引是有序的，会将相邻的数据都存储在一起）。

参考B+ Tree演示地址：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

索引设计（前缀索引）：https://opensource.actionsky.com/20210120-mysql/

索引设计（MySQL的索引结构）：https://opensource.actionsky.com/20201111-mysql/