常见的索引数据结构

• key-value - 哈希表（数组）+ 链表：在数据量小的时候查询速度非常快，数据量大的时候需要遍历链表，对性能影响比较大。memcached就是使用这种数据结构。

• 数组：查询速度是最快的，但是如果存在插入中间数据的情况，就需要挪动所有后面的数据，代价太大。即：查询快，插入慢，适合存储不会变更的数据。

• 树（B+树）：折中了查询和插入数据的速度，时间复杂度都是O(N)，mysql 的 InnoDB 引擎就是使用了B+树的数据结构。

以下以user表为例

CREATE TABLE `user` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `id_card` varchar(32) DEFAULT NULL,
  `name` varchar(32) DEFAULT NULL,
  `age` int(11) DEFAULT NULL,
  `city` varchar(32) DEFAULT NULL,
  PRIMARY KEY (`id`),
  KEY `idx_id_card` (`id_card`),
  KEY `idx_age` (`age`),
  KEY `idx_age_name_city` (`age`,`name`, `city`)
) ENGINE=InnoDB

（实际情况不需要建idx_age和idx_age_name两个索引）

带索引字段查询条件的 sql 查询过程

1. 分析器判断使用哪个索引
2. 在对应字段索引树查询第一条符合条件的记录
3. 如果索引数没有包含需要查询和其他查询条件的字段，则回表到主键索引数查询整条记录
4. 继续在索引数上往下偏移，查询下一条记录，循环上一步操作
5. 如果记录不符合条件，则退出循环，查询结束

覆盖索引

假如有这么一个表，select name from user where age = 20'，通过年龄查用户姓名。在没有有idx_age_name_city索引的情况下，在idx_age索引树上查询记录后，需要在通过 id 回表到主键索引数上查询整体记录得到 name，如果存在idx_age_name_city索引，则不需要回表到主键索引就可以得到 name，减少了查询次数，因为索引已经覆盖了需要查询的字段。

当查询数据量比较大时，覆盖索引可以较大提升查询性能，是一个常用的性能优化手段。

最左前缀原则

在联合索引中，只有从左往右第一个（idx_age_name_city），就是最左边的字段（age）的查询可以使用该索引，其他字段只是为了减少回表次数，所以需要根据实际情况，将查询频率最多的子弹放在第一位。

最左前缀还有一个场景时在 like 模糊查询的情况下，只有 xx% 可以使用索引，%xx% 和 %xx 都是不能使用索引的

索引下推

在覆盖索引中，索引已经包含了需要查询的字段，则不需要回表，同样的也适用在多个查询条件的情况，例如 select name from user where age = 20 and city = '广州'，在idx_age_name_city索引树查询出符合 age 条件的记录后，不需要回表就可以判断 city 是否符合条件，也减少了回表查询次数，这个就时索引下推。

索引分类

聚簇索引和非聚簇索引

• 聚簇索引 包含索引和数据，找到了索引就可以查询到整条记录，也就是主键索引

• 非聚簇索引 非聚簇索引又叫辅助索引，只保存了数据的主键，通过非聚簇索引查询的的记录还需要通过主键值回表查询才能得到整条记录

普通索引和唯一索引对比

• 查询性能

没有太大区别。相对唯一索引，普通索引在查找到目标值得时候还会往下继续再查一次，判断是否与查询条件的值相等，不相等直接返回。但是这一次查询对整体性能影响非常小，可以忽略不计。

• 写入性能

唯一索引无法使用 change buffer，因为唯一索引在的数据在插入之前需要判断数据是否满足唯一约束，就需要从数据页到内存后再比较，涉及到随机IO的访问，是比较耗时的操作。

而普通索引是直接将数据放到 change buffer 后就直接返回成功了。MySQL 会定期的把 change buffer 数据merge到数据页，或者在需要查询数据的时候也会触发 merge。

所以，在读多写少的场景下，change buffer 反而起到副作用，没能减少IO次数，还增加了 change buffer 维护成本。

总结：在写多读少，并且程序已经能够保证数据唯一性的情况下可以使用普通索引来提高写入性能。

实践

索引创建原则

1. 频繁查询的字段可以建索引，确保符合覆盖索引原则，减少回表
2. 频繁使用的 where 条件建索引
3. 数据量小时不需要建索引
4. 区分度小（基数小）的字段不需要建索引

给字符串加索引的一些实践

1. 直接创建完整索引，这样会⽐较占⽤空间
2. 创建前缀索引，节省空间，但会增加查询扫描次数（前缀长度要根据实际情况确保区分度比较高）
3. 对于前部分大多数相同的数据，可以倒序存储，再创建前缀索引，⽤于绕过字符串本身（例如身份证号码，前部分的区分度角度，后6位的区分度高）
4. 创建 hash 字段索引，查询性能稳定，有额外的存储和计算耗，跟第三种方式一样，都不支持范围扫描。

已经建了索引，sql执行却没有走索引

少数情况下，优化器误判了扫描行数（rows），会选错索引，导致没有执行最优的查询计划。

优化器通过索引的基数判断扫描行数，基数的计算方法是抽样取 n 个数据页，统计索引字段上不同的值，然后在乘以数据页数量，得到索引基数。当数据行超过一定值时，会重新计算基数。

show index from $table_name可以查看索引信息，cardinality 代表基数值。

show index from user_info;
+-----------+------------+----------------------------+--------------+------------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| Table     | Non_unique | Key_name                   | Seq_in_index | Column_name      | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment | Index_comment |
+-----------+------------+----------------------------+--------------+------------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| user_info | 0          | PRIMARY                    | 1            | user_id          | A         | 8026541     | <null>   | <null> |      | BTREE      |         |               |
| user_info | 1          | user_info_create_time      | 1            | create_time      | A         | 5840068     | <null>   | <null> |      | BTREE      |         |               |
| user_info | 1          | user_info_update_time      | 1            | update_time      | A         | 5768171     | <null>   | <null> |      | BTREE      |         |               |
+-----------+------------+----------------------------+--------------+------------------+-----------+-------------+----------+--------+------+------------+---------+---------------+

解决方案

1. 使用analyze table $table_name重新统计索引基数
2. 在 sql 中显式指定索引select * form $table_name force index(idx_name) [where]
3. 在结果相同的情况下增加 where 条件，让优化器判断行数更准确（具体做法需要根据实际情况而定）

创建索引

-- 创建主键索引
alter table tb add primary key idx_primary_key (c1);
-- 创建单个字段的索引
alter table tb add index idx_c1 (c1);
-- 创建联合索引
alter table tb add index idx_c1_c2 (c1, c2);
-- 创建唯一索引
alter table tb add unique idx_uni_c2 (c2);
-- 创建前缀索引，10表示前10个字节
alter table tb add unique idx_uni_c2 (c2(10));