MySQL 索引

Created at 2019-08-14 Updated at 2020-07-29 Category 基础 Tag MySQL views

表

MySQL 使用 InnoDB 存储表时，会将表的定义和数据索引等信息分开存储，其中前者存储在 .frm 文件中，后者存储在 .ibd 文件中。

索引

索引工作原理

索引存储了指向表中某一行的指针

当某个 SQL 语句运行时，数据库会检查在查询的列上是否有索引，如果有索引，数据库会接着检查使用这个索引做查询是否合理，因为有些场景下，使用索引比全表扫描更加低效。

可以强制数据库使用索引。

B+Tree 索引

B 树

叶子节点和非叶子节点都存储数据
通过中序遍历获得所有节点

为什么 b 树适合做索引

高度低
每个节点可以存储 j 个记录，如果将节点大小设置为页大小，可以利用预读特性，减少磁盘 IO。

局部性原理

内存读写快，磁盘读写慢
磁盘预读：磁盘读写并不是按需读取，而是按页读取，一次读一页的数据。如果未来要读的数据就在这一页中，可以避免未来的磁盘 IO，提高效率。

数据库系统将索引的一个节点的大小设置为页的大小，使得一次 I/O 就能完全载入一个节点。并且可以利用预读特性，相邻的节点也能够被预先载入.

B+ 树

非叶子节点不再存储数据，数据只存储在叶子节点上
相同层次的页面之间用双向链表连接
在 B+ Tree 中，一个节点中的 key 从左到右递增排列

每颗 B+ 数由很多页面组成，B+ 数的页面可分为

叶子节点：存储记录的所有内容。
非叶子节点：存储索引值和对应的页号

与 b 树的比较

范围查找，定位 min 和 max 之后，中间叶子节点就是结果集，不需要中序遍历。
叶子节点存储实际记录行，适合大数据量磁盘存储，非叶子节点存储记录的主键值，用于查询加速，适合内存存储。

与红黑树的比较

更少的查找次数：平衡树查找操作的时间复杂度和树高 h 相关，O(h)=O(logdN)，其中 d 为每个节点的出度。红黑树的出度为 2，而 B+ Tree 的出度一般都非常大，所以红黑树的树高 h 很明显比 B+ Tree 大非常多，查找的次数也就更多。
利用磁盘预读特性

hash 索引

哈希索引操作的平均复杂度都是 O(1),内存表默认使用 hash 索引。

但是 hash 函数计算后的结果是随机的，在磁盘上随机放置，失去了有序性。所以无法对范围查询和排序进行优化，无法利用前缀索引。

InnoDB 不支持哈希索引，用户无法手动创建哈希索引。

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

全文索引

MyISAM 存储引擎支持全文索引，用于查找文本中的关键词，而不是直接比较是否相等
查找使用 MATCH AGAINST 而不是普通的 WHERE
全文索引使用倒排索引实现，它记录着关键词到其所在文档的映射
InnoDB 存储引擎在 MySQL5.6.4 版本中也开始支持全文索引

空间数据索引

MyISAM 存储引擎支持空间数据索引（R-Tree），可以用于地理数据存储。空间数据索引会从所有维度来索引数据，可以有效地使用任意维度来进行组合查询。
必须使用 GIS 相关的函数来维护数据。

从物理角度

聚集索引

主索引上直接存放数据，次索引存储主键的值。

因为次索引存储主键的值，所以不建议使用过长的字段作为主键。

InnoDB 是聚簇索引。
优势：

查询条目比较少时，不用回到物理行找数据。
辅助索引使用主键作为“指针”而不是地址值，减少了当出现行移动或者数据页分裂时辅助索引的维护工作。

劣势：碰到不规则数据插入时，造成频繁的页分裂。

如果表定义了 PK，则 PK 就是聚集索引；
如果表没有定义 PK，则第一个非空 unique 列是聚集索引；
否则，InnoDB 会创建一个隐藏的 row-id 作为聚集索引；

一般来讲，使用一个业务无关的自增（ AUTO_INCREMENT ）ID，可以保证数据在插入时会被按顺序写入。假设我们使用 UUID 作为聚簇索引，在插入数据的时候，聚簇索引所被插入的位置将变得完全随机。大量的随机插入会导致页分裂和碎片非常多。

非聚簇索引

InnoDB 中普通索引是非聚簇索引，叶子节点存储主键值。通过普通索引查找记录会先由普通索引找到主键，然后通过主键索引找到行记录。

MyISAM 中主索引和次索引一样，都保存指向物理地址的指针。

从逻辑角度

普通索引
唯一索引
主键索引
组合索引
外键索引
空间索引