索引模型

  1. Hash Index 哈希索引，最优时间复杂度 O(1)
  2. B+Tree B+树索引（默认索引类型）时间复杂度 O(logN)

_

索引应用

  1. 使用 N 叉树代替平衡二叉树，从而减少文件系统的目录层级，一来是操作系统对目录层级的深度有限制，二来是减少磁盘寻址次数提高性能；
  2. 保持有序（为了查询性能）；

B-Tree / B+Tree

  1. B+Tree 非叶子节点不保存数据只保存索引，相反 B-Tree 所有节点（包括叶子节点）都会保存数据；
  2. B+Tree 的所有叶子节点通过链表方式串连，而 B-Tree 则没有；
  3. B+Tree 的叶子节点数据，包含索引字段值及主键 ID，且按照索引字段值进行排序；

索引类型

  1. 主键索引，叶子节点保存的是整行数据，也被称为聚簇(读 cu)索引（Clustered Index）；
  2. 非主键索引，叶子节点保存的是主键数据，称为二级索引（Secondary Index），通过二级索引查询的数据需要回表操作（即在二级索引上查询得到主键值，再根据主键值回表查询主键索引中的数据）；
  3. 覆盖索引，此类型的索引是为了避免回表查询的问题，较常用于组合索引；
  4. 组合索引，多个列组合成为一个索引；
  5. 前缀索引，将值的特定前缀长度构建索引树，对于 BLOB / TEXT 类型强制要求，也可对 BINARY 的前缀字节及 VARCHAR 的前缀字符作为索引值，前缀的长度需要在 SQL 中指定；

覆盖索引

覆盖索引是为了解决数据回表的问题，如 select identity,name from tuser where identity=’xxx’; 若存在组合索引 (identity, name)，由于索引上存在了 identity 和 name 两个字段值，覆盖了 SELECT 语句的返回要求，这个时候就不需要回表查询操作，因而得名为覆盖索引_。不过这是典型的以空间换时间，除了组合索引，单个字段的索引有时候也可以作为覆盖索引返回结果，如 select id, identity from t_user where identity like ‘4401%’，存在索引 index (identity)，且索引上的数据包含了 identity 及主键 id，因此也不需要再回表查询。

值得一提的是，如果 t_user 表中仅有 identity 索引，但查询语句调整为 select identity,id from t_user where identity=’xxx’; 也会利用到覆盖索引的功能减少回表操作，这是因为二级索引上的值包含了 identity 及主键 ID 的值，所以无需通过回表获取相应的数据。

最左前缀原则

最基础的是单个字符串索引的前缀匹配，如 name like ‘张三%’ 就可以利用索引查询，若是 ‘%张三’ 或 ‘%张三%’ 都不能使用索引进行查询；同样适用于联合索引的匹配，如存在联合索引 index(a,b,c,d)，以下的查询方式都能够使用索引。

  • where a = ‘xxx’
  • where a like ‘xxx%’
  • where a = ‘xxx’ and b = ‘yyy’
  • where a = ‘xxx’ and b = ‘yyy’ and c = ‘zzz’
  • where a = ‘xxx’ and b = ‘yyy’ and c = ‘zzz’ and d = ‘kkk’

值得一提的是，a like ‘xxx%’ 也符合最左前缀原则（仅组合索引的第一个索引有效），联合索引可以参考官方文档的说明https://dev.mysql.com/doc/refman/5.7/en/multiple-column-indexes.html

If the table has a multiple-column index, any leftmost prefix of the index can be used by the optimizer to look up rows. For example, if you have a three-column index on (col1, col2, col3), you have indexed search capabilities on (col1), (col1, col2), and (col1, col2, col3).

前缀索引

1. BLOB / TEXT

如果使用 BLOB 及 TEXT 字段的全值构建索引会占用非常大的空间，因此建立索引的时候只会使用到该字段值的前缀部分，以减少索引的空间占用，参考官方文档 https://dev.mysql.com/doc/refman/5.7/en/column-indexes.html#column-indexes-prefix。

Index Prefixes

With _colname`(N)syntax in an index specification for a string column, you can create an index that uses only the first _N`_ characters of the column. Indexing only a prefix of column values in this way can make the index file much smaller. When you index a BLOB or TEXT column, you must specify a prefix length for the index. For example:

— 前十个字节作为索引 CREATE TABLE test (blob_col BLOB, INDEX(blob_col(10)));

BLOB / TEXT 也不适用于排序，因为索引是建立在字段值前缀部分基础上，因为默认的排序只会是前缀部分顺序而非全值排序。参考文档 https://dev.mysql.com/doc/refman/5.7/en/glossary.html#glos_clustered_index。

column prefix
When an index is created with a length specification, such as CREATE INDEX idx ON t1 (c1(N)), only the first N characters of the column value are stored in the index. Keeping the index prefix small makes the index compact, and the memory and disk I/O savings help performance. (Although making the index prefix too small can hinder query optimization by making rows with different values appear to the query optimizer to be duplicates.)

For columns containing binary values or long text strings, where sorting is not a major consideration and storing the entire value in the index would waste space, the index automatically uses the first N (typically 768) characters of the value to do lookups and sorts.

2. VARCHAR

对于非大字段的字符串索引，默认使用的全值构建 B+Tree 索引树，同样可以使用字符串特定长度前缀构建索引树，在某种程度上可以节省空间，但换取的是需要牺牲一定的性能，主要体现在增加回表的次数。

为什么会增加回表查询的次数？这是因为构建二级索引树的值使用的是列的前缀值，因为索引值上的内容不完整，首先就不满足覆盖索引功能需求，必须进行回表查询操作；另外，前缀索引的查询条件只能在主键索引上匹配，若存在前缀索引 name（前 2 个字符），查询条件如 WHERE name=’张三丰’ 则只能拿到 “张三” 作为条件到前缀索引上搜索出所有能匹配的主键，再通过回表匹配 “张三丰” 的值。

注意

  • 指定字符串前缀索引的数值是 character 为单位，如 VARCHAR / TEXT；
  • 而 BLOB / BINARY / VARBINARY 的前缀索引的数值是 byte 为单位；

**

索引下推

从 MySQL 5.6 引入了索引下推的方式，也是为了减少回表的次数，这里还是以组合索引 index (identity, name) 为例。

MySQL 5.6 之前要是通过 select identity,name from t_user where identity like ‘4401%’ and name=’张三’ 查询时，以最左前缀原则，计算出 440181 的值，在 B+Tree 中找到比该值大的叶子节点数据时就会回表**查询出数据后对比 name=’张三’ 这个条件，即先回表查询再匹配其他条件。

MySQL 5.6 之后引入索引下推，因为存在组合索引 (identity, name) 同时存有 identity 和 name 的数据，因此 name=’张三’ 这个条件只需要匹配在二级索引中的数据即可，再将二级索引命中的数据中获取主键再回表查询，从而减少回表的查询操作，即先匹配覆盖索引中的条件再回表查询。

自增主键

由于 B+Tree 中的节点涉及分裂和合并的操作，当插入数据时涉及节点分裂，删除数据时涉及节点的合并，但要是更新主键，就有可能同时触发分裂和合并操作。

而索引节点的分裂过程导致性能低下，这个时候自增主键就是很好解决方案，因为自增主键会一直增加，不会触发主键索引的分裂操作，另外从自增主键储存空间因素考虑，数据类型为最多是 bigint (8 字节)，int (4 字节)。

什么时候使用非自增索引？如果索引值唯一且只有一个索引，即 KV 的哈希索引类型。

索引练习

  1. CREATE TABLE `geek` (
  2.   `a` int(11) NOT NULL,
  3.   `b` int(11) NOT NULL,
  4.   `c` int(11) NOT NULL,
  5.   `d` int(11) NOT NULL,
  6.   PRIMARY KEY (`a`,`b`),
  7.   KEY `c` (`c`),
  8.   KEY `ca` (`c`,`a`),
  9.   KEY `cb` (`c`,`b`)
  10. ) ENGINE=InnoDB;

公司的同事告诉他说，由于历史原因，这个表需要 a、b 做联合主键，这个小吕理解了。

但是，学过本章内容的小吕又纳闷了，既然主键包含了 a、b 这两个字段，那意味着单独在字段 c 上创建一个索引，就已经包含了三个字段了呀，为什么要创建“ca”“cb”这两个索引？

同事告诉他，是因为他们的业务里面有这样的两种语句：

  1. select * from geek where c=N order by a limit 1;
  2. select * from geek where c=N order by b limit 1;

我给你的问题是，这位同事的解释对吗，为了这两个查询模式，这两个索引是否都是必须的？为什么呢？

分析过程

  1. 根据最左前缀原则，聚簇索引，即主键 (a,b) 字段 a 是索引，数据节点包含 a,b 的值，且按照 a 先进行排序，再对 b 排序；
  2. 索引 c 的数据节点包含是 c 及主键 a 的值，且按照 c 先进行排序，再对 a 排序；
  3. 经过 #2 的分析，我们发现 KEY c (c) 与 KEY ca (c,a) 索引重复，得出 ca (c,a) 是冗余的索引，结论是可以删除索引 ca；