索引是存储引擎用于快速找到记录的一种数据结构, 它能提高查询性能.

索引基础

索引是在存储引擎层实现的, MySQL支持以下几种索引类型:

索引的类型

B-Tree索引

InnoDB使用了B+Tree, 特点是:

• 非叶子节点只存储键值信息。
• 所有叶子节点之间都有一个链指针。
• 数据记录都存放在叶子节点中。

截屏2020-02-24上午6.37.31.png

B+Tree的高度一般都在2~4层。mysql的InnoDB存储引擎在设计时是将根节点常驻内存的，也就是说查找某一键值的行记录时最多只需要1~3次磁盘I/O操作.

数据库中的B+Tree索引可以分为聚集索引（clustered index）和辅助索引（secondary index）。上面的B+Tree示例图在数据库中的实现即为聚集索引，聚集索引的B+Tree中的叶子节点存放的是整张表的行记录数据。辅助索引与聚集索引的区别在于辅助索引的叶子节点并不包含行记录的全部数据，而是存储相应行数据的聚集索引键，即主键。当通过辅助索引来查询数据时，InnoDB存储引擎会遍历辅助索引找到主键，然后再通过主键在聚集索引中找到完整的行记录数据.

InnoDB存储引擎中有页（Page）的概念，页是其磁盘管理的最小单位, InnoDB在把磁盘数据读入到磁盘时会以页为基本单位, 通过如下命令查看页的大小:

mysql> show variables like 'innodb_page_size';

image.png

上表的索引对以下类型的查询有效:

• 全值匹配全值匹配: 指的是和索引中的所有列进行匹配，例如前面提到的索引可用于查找姓名为Cuba Allen、出生于1960-01-01的人。
• 匹配最左前缀前面: 提到的索引可用于查找所有姓为Allen的人，即只使用索引的第一列。
• 匹配列前缀: 也可以只匹配某一列的值的开头部分。例如前面提到的索引可用于查找所有以J开头的姓的人。
• 匹配范围值: 例如前面提到的索引可用于查找姓在Allen和Barrymore之间的人。这里也只使用了索引的第一列。
• 精确匹配某一列并范围匹配另外一列: 前面提到的索引也可用于查找所有姓为Allen，并且名字是字母K开头（比如Kim、Karl等）的人。
• 只访问索引的查询: B-Tree通常可以支持“只访问索引的查询”，即查询只需要访问索引，而无须访问数据行。后面我们将单独讨论这种“覆盖索引”的优化。

B+Tree索引适用于全键值, 键值范围或键前缀查找. 其中键前缀查找只适用于根据最左前缀的查找. 且因为索引树中的节点是有序的, 索引除了按值查找外, 索引还可以用于查询中的ORDER BY操作. 即满足上面索引查询的时候, 也可以满足对应的排序要求(不需再花费额外的内存和时间).

哈希索引

哈希索引基于哈希表实现，只有精确匹配索引的所有列，索引才会生效。

哈希索引的限制：

1. 哈希索引只存储哈希值和行指针，不存储字段数据值，因此无法从索引中查询数据
2. 哈希索引无法顺序存储，无法进行排序
3. 哈希索引不支持部分匹配，必须精确匹配所有索引列
4. 哈希索引不支持范围查找
5. 哈希冲突会影响性能

可以创建自定义哈希索引(见书上的例子), 此时要避免冲突问题, 必须在where条件中带入hash值和对应列值, 只需要根据Hash值做快速的整数比较找到索引条目, 然后一一比较返回对应的行.

空间数据索引(R-Tree)

用作地理数据存储, MySQL支持的不完善, 比较好的是PostgresSQL的PostGIS.

全文索引

它查找的是文本中的关键词, 而非直接比较索引中的值. 可以在相同的列上同时创建全文索引和基于值的B-Tree索引不会有冲突, 全文索引适用于MATCH AGAINST操作, 而非普通的WHERE条件操作. 第七章会讨论更多全文索引的细节.

索引的优点

1. 大大减少服务器需要扫描的数据量
2. 可以帮助服务器避免排序和临时表
3. 可以将随机I/O变为顺序I//O

一星系统:
索引将相关的记录放到一起得一星.
二星系统:
索引中的数据顺序和查找中的排列顺序一致得二星.
三星系统:
索引中的列包含了查询中需要的所有列得三星.

当然，索引也并不总是最好的工具。只有当索引帮助存储引擎快速查找到记录带来的好处大于其带来的额外工作时，索引才是有效的。非常小的表，大部分直接全表扫描更有效；中到大型的表，索引非常有效。特大型的表，则建立和使用索引的代价将随之增长，需要一种技术可以区分出查询需要的一组数据，如分区技术

高性能的索引策略

独立的列

列不要进行参与计算:
where id+1=5应该改成where id=4

前缀索引和索引选择性

一种选择索引的技巧是: 选择足够长的前缀保证较高的选择性, 同时又不能太长(以便节约空间).

索引的选择性是指: 不重复的索引值(也称为基数, cardinality)和数据表的总记录数(#T)的比值, 范围从1/#T到1之间. 索引的选择性越高则查询效率越高.

balabala, 若找到了合适的前缀长度, 则可用以下语句创建前缀索引:

mysql> ALTER TABLE sakila.city_demo ADD KEY (city(7));

查询的时候where city='xxxxxxxxxx'自动会用到前缀索引
前缀索引优点是: 使索引更小.
缺点是: MySQL无法使用前缀索引做ORDER BY和GROUP BY, 也无法使用前缀索引做覆盖扫描.

多列索引

这里指多个单列索引, 不建议.

选择合适的索引列顺序

在一个多列B-Tree索引中, 索引列的顺序意味着索引先按照最左边进行排序, 其次是第二列, 等等.

经验法则: 将选择性最高的列放在索引最前列. 但特殊情况有其他的标准.

聚簇索引

InnoDB的聚簇索引实际在同一个结构中保存了B-Tree索引和数据行.
数据行存储在叶子页中, "聚簇"表示数据行和相邻的键值紧凑地存储在一起. 一个表只能有一个聚簇索引.

假设建表语句为:

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

image.png

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

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

如果语句是 select * from T where ID=500，即主键查询方式，则只需要搜索 ID 这棵 B+ 树；如果语句是 select * from T where k=5，即普通索引查询方式，则需要先搜索 k 索引树，得到 ID 的值为 500，再到 ID 索引树搜索一次。这个过程称为回表。

索引维护

B+ 树为了维护索引有序性，在插入新值的时候需要做必要的维护。
以上面这个图为例，如果插入新的行 ID 值为 700，则只需要在 R5 的记录后面插入一个新记录。如果新插入的 ID 值为 400，就相对麻烦了，需要逻辑上挪动后面的数据，空出位置。而更糟的情况是，如果 R5 所在的数据页已经满了，根据 B+ 树的算法，这时候需要申请一个新的数据页，然后挪动部分数据过去。这个过程称为页分裂。
在这种情况下，性能自然会受影响。除了性能外，页分裂操作还影响数据页的利用率。原本放在一个页的数据，现在分到两个页中，整体空间利用率降低大约 50%。当然有分裂就有合并。当相邻两个页由于删除了数据，利用率很低之后，会将数据页做合并。合并的过程，可以认为是分裂过程的逆过程。

MyISAM的数据存储

MyISAM的行数据按照数据插入的顺序存储在磁盘上, 索引也是B-Tree, 不过B-Tree的叶子节点存储的是行号(行指针). MyISAM的主键和其他索引在结构上没有不同. 如下图所示:

截屏2020-02-24下午11.41.53.png

要注意的是: InnoDB的二级索引的叶子节点存储的不是行指针, 而是主键值, 这样的好处是当行移动或数据页分裂时, 无须更新二级索引中的主键值.

在InnoDB表中按主键顺序插入行

尽量使用AUTO_INCREMENT自增列, 保证数据行是按顺序写入. 如果非顺序插入, 会有以下几个缺点:

1. 写入的目标页可能已经刷到磁盘上并从缓存中移除, 不得不先找到并从磁盘读取目标页到内存中.
2. 因为写入是乱序, InnoDB不得不频繁的做页分裂操作, 这时候需要申请一个新的数据页，然后挪动部分数据过去, 性能受影响.
3. 频繁页分裂, 页会变得稀疏和碎片.