MySQL 索引

2021/05/20 database 共 3936 字,约 12 分钟
Bob.Zhu

概念

一句话简单来说,索引的出现其实就是为了提高数据查询的效率,就像书的目录一样。

索引模型

索引的出现是为了提高查询效率,但是实现索引的方式却有很多种,所以这里也就引入了索引模型的概念。 可以用于提高读写效率的数据结构很多,这里我先给你介绍三种常见、也比较简单的数据结构,它们分别是 哈希表、有序数组和搜索树。

哈希表

哈希表是一种以键 - 值(key-value)存储数据的结构,我们只要输入待查找的键即 key,就可以找到 其对应的值即 Value。哈希的思路很简单,把值放在数组里,用一个哈希函数把 key 换算成一个确定的 位置,然后把 value 放在数组的这个位置。 不可避免地,多个 key 值经过哈希函数的换算,会出现同 一个值的情况。处理这种情况的一种方法是,拉出一个链表。(Bob:其实,对于哈希碰撞,有多种解决方 案,比如 再开放地址法、再哈希法、链地址法)

哈希表

图中,User2 和 User4 根据身份证号算出来的值都是 N,但没关系,后面还跟了一个链表。假设,这时候 你要查 ID_card_n2 对应的名字是什么,处理步骤就是:首先,将 ID_card_n2 通过哈希函数算出 N; 然后,按顺序遍历,找到 User2。

需要注意的是,图中四个 ID_card_n 的值并不是递增的,这样做的好处是增加新的 User 时速度会很快, 只需要往后追加。但缺点是,因为不是有序的,所以哈希索引做区间查询的速度是很慢的。 你可以设想下,如 果你现在要找身份证号在[ID_card_X, ID_card_Y]这个区间的所有用户,就必须全部扫 描一遍了。 所以, 哈希表这种结构适用于只有等值查询的场景,比如 Memcached 及其他一些 NoSQL 引擎。

使用哈希表索引有以下一些限制:

  • 哈希索引数据不是按照索引值顺序存储的,无法用于排序。
  • 哈希索引不支持部分索引列匹配查找,因为哈希索引始终是使用索引列的全部内容来计算哈希值的。 例如在数据列(a,b)上建立哈希索引,如果查询的列只有a就无法使用该索引。
  • 哈希索引只支持等值比较查询,不支持任何范围查询。

有序数组

有序数组在等值查询和范围查询场景中的性能就都非常优秀。还是上面这个根据身份证号查名字的例子,如果我 们使用有序数组来实现的话,示意图如下所示:

有序数组

这里我们假设身份证号没有重复,这个数组就是按照身份证号递增的顺序保存的。这时候如果你要查 ID_card_n2 对应的名字,用二分法就可以快速得到,这个时间复杂度是 O(log(N))。 同时很显然,这个索引结构支持范围查询。 你要查身份证号在[ID_card_X, ID_card_Y]区间的 User,可以先用二分法找到 ID_card_X(如果不存在 ID_card_X,就找到大于 ID_card_X 的第一个 User),然后向右遍历,直到查到第一个大于 ID_card_Y 的身份 证号,退出循环。 如果仅仅看查询效率,有序数组就是最好的数据结构了。但是,在需要更新数据的时候就麻烦了,你 往中间插入一个记录就必须得挪动后面所有的记录,成本太高。 所以,有序数组索引只适用于静态存储引擎,比如你要 保存的是 2017 年某个城市的所有人口信息,这类不会再修改的数据。

B-Tree索引

二叉搜索树也是课本里的经典数据结构了。还是上面根据身份证号查名字的例子,如果我们用二叉搜索树来实现的话,示 意图如下所示:

搜索树

B+树是一个平衡的多叉树,从根节点到每个叶子节点的高度差值不超过1,而且同层级的节点间有指针相互链接。

CREATE TABLE People (
   last_name  varchar(50)    not null,
   first_name varchar(50)    not null,
   dob        date           not null,
   gender     enum('m', 'f') not null,
   key(last_name, first_name, dob)
);

B-Tree索引-左前缀匹配

可以利用B-Tree索引进行全关键字、关键字范围和关键字前缀查询,当然,如果想使用索引,你必须保证 按索引的最左边前缀(leftmost prefix of the index)来进行查询:

  • 匹配全值(Match the full value):对索引中的所有列都指定具体的值
  • 匹配最左前缀(Match a leftmost prefix):你可以利用索引查找last name为Allen的人,仅仅使用索引中的第1列。
  • 匹配列前缀(Match a column prefix):例如,你可以利用索引查找last name以J开始的人,这仅仅使用索引中的第1列。
  • 匹配值的范围查询(Match a range of values):可以利用索引查找last name在Allen和Barrymore之间的人,仅仅使用索引中第1列。
  • 匹配部分精确而其它部分进行范围匹配(Match one part exactly and match a range on another part):可以利用索引查找last name为Allen,而first name以字母K开始的人。
  • 仅对索引进行查询(Index-only queries):如果查询的列都位于索引中,则不需要读取元组的值(覆盖索引)。

使用B-tree索引有以下一些限制: 1) 查询必须从索引的最左边的列开始,否则无法使用索引。关于这点已经提了很多遍了。例如你不能利用索引查找在某一天出生的人。 2) 不能跳过某一索引列。例如,你不能利用索引查找last name为Smith且出生于某一天的人。 3) 存储引擎不能使用索引中范围条件右边的列。例如,如果你的查询语句为WHERE last_name=”Smith” AND first_name LIKE ‘J%’ AND dob=’1976-12-23’,则该查询只会使用索引中的前两列,因为LIKE是范围查询

空间索引

MyISAM 表支持空间索引,可以用作地理数据存储。和 B-Tree 索引不同,这类索引无需前缀查询。空间 索引会从所有维度来索引数据,查询时可以有效地使用任意维度来组合查询。必须使用 MySQL 的 GIS 即 地理信息系统的相关函数来维护数据,但 MySQL 对 GIS 的支持并不完善,因此大部分人都不会使用这个特性。

全文索引

通过数值比较、范围过滤等就可以完成绝大多数需要的查询,但如果希望通过关键字匹配进行查询,就需要 基于相似度的查询,而不是精确的数值比较,全文索引就是为这种场景设计的。

MyISAM 的全文索引是一种特殊的 B-Tree 索引,一共有两层。第一层是所有关键字,然后对于每一个关 键字的第二层,包含的是一组相关的”文档指针”。全文索引不会索引文档对象中的所有词语,它会根据规则 过滤掉一些词语,例如停用词列表中的词都不会被索引。

InnoDB 的索引模型

在 InnoDB 中,表都是根据主键顺序以索引的形式存放的,这种存储方式的表称为索引组织表。又因为前面我们提到的,InnoDB 使用了 B+ 树索引模型,所以数据都是存储在 B+ 树中的。 每一个索引在 InnoDB 里面对应一棵 B+ 树。 假设,我们有一 个主键列为 ID 的表,表中有字段 k,并且在 k 上有索引。 这个表的建表语句是:

create table T(
  id int primary key, 
  k int not null, 
  name varchar(16),
  index (k)
)engine=InnoDB;

InnoDB 的索引模型

从图中不难看出,根据叶子节点的内容,索引类型分为主键索引和非主键索引。

主键索引(聚簇索引)

主键索引的叶子节点存的是整行数据。在 InnoDB 里,主键索引也被称为聚簇索引(clustered index)。

聚簇索引不是一种索引类型,而是一种数据存储方式。InnoDB 的聚簇索引实际上在同一个结构中保存了 B-Tree 索引和数据行。当表有聚餐索引时,它的行数据实际上存放在索引的叶子⻚中,因为无法同时把 数据行存放在两个不同的地方,所以一个表只能有一个聚簇索引。

优点: 1) 可以把相关数据保存在一起。 2) 数据访问更快,聚簇索引将索引和数据保存在同一个 B-Tree 中,因此获取数据比非聚簇索引要更快。 3) 使用覆盖索引扫描的查询可以直接使用⻚节点中的主键值。

缺点: 1) 聚簇索引最大限度提高了 IO 密集型应用的性能,如果数据全部在内存中将会失去优势。 2) 更 新聚簇索引列的代价很高,因为会强制每个被更新的行移动到新位置。 3) 基于聚簇索引的表插入新行或 主键被更新导致行移动时,可能导致⻚分裂,表会占用更多磁盘空间。 4) 当行稀疏或由于⻚分裂导致数 据存储不连续时,全表扫描可能很慢。

非主键索引

非主键索引的叶子节点内容是主键的值。在 InnoDB 里,非主键索引也被称为二级索引(secondary index)。

回表

如果语句是 select * from T where ID=500,即主键查询方式,则只需要搜索 ID 这棵 B+ 树; 如果语句是 select * from T where k=5,即普通索引查询方式,则需要先搜索 k 索引树,得到 ID 的值为 500, 再到 ID 索引树搜索一次。这个过程称为回表。 也就是说,基于非主键索引的查询需要多扫描一棵索引树。因此,我们在应用中应该尽量使用主键查询。

覆盖索引

覆盖索引指一个索引包含或覆盖了所有需要查询的字段的值,不再需要根据索引回表查询数据。

常见的实现覆盖索引的方法是:将被查询的字段,建立到联合索引里去。 如实现:select id,age from user where age = 10; explain分析:因为age是普通索引,使用到了age索引,通过一次扫描B+树即可查询到相应的结果,这样就实现了覆盖索引

索引使用原则

  • 建立索引:查询频次较高数据创建索引
  • 使用前缀索引
  • 选择合适的索引顺序
  • 删除无用索引

TODO

参考资料

文档信息

Search

    Table of Contents