什么是索引
是一类可以提高数据查询速度的数据结构或者算法的集合
实现索引的方式
有序数组
散列表
跳表
AVL 平衡二叉树
红黑树
B+ 树
。。。各种其它的树
MySql 索引
MySql 中 InnoDB 索引是用过 B+树来进行实现的
B+ 树特点
一个 M 叉树
除了根节点以外每个节点包含 M/2+1 到 M 个子节点
一个节点有 N 个元素和 N+1 个指向子节点的指针
所有叶子节点的高度相同
内部节点不存储数据
叶子结点存储真正的数据
叶子结点之间通过双向链表连接
在实现上我们把索引 B+ 树的节点作为一个数据页，存储在磁盘上。每个数据页的大小根据系统 IO 的大小进行设置的通常是 4 KB。我们可以通过 getconfig PAGE_SIZE 来查看，在操作系统中会按照页为单位读取磁盘或内存中的数据。我们在设置 M 的时候需要考虑尽量让每个节点的大小等于一个页的大小，这样可以减少 IO 操作。
B+ 树优点
和其他搜索树类似，它支持快速 O(log N) 的进行查询
支持快速范围查询，哈希表和平衡二叉树不支持
相对于红黑树和平衡二叉树，B+ 树压缩了层高，减小了查询数据时遍历的节点数，可以减小磁盘 IO
由于上一点 B+ 树比其它结构更适合存储在外部存储上，外部存储的空间远大于内存中可以存储的大小，所以 B+ 树可以支持更打规模的索引。
索引维护
对于插入，更新或者删除操作都会涉及到索引树的修改
删除数据的时候，可能会导致对应的 B+ 树节点的元素数量少于 M/2 的情况。此时有两种处理的情况：
当前节点相邻的兄弟节点，有多的子节点转移到当前的节点
如果当前节点相邻的兄弟节点没有多余的节点可以转移到当前节点，我们需要将两个兄弟节点合并成一个新的节点，并且递归判断父节点是否满足 B+ 树的约束。
插入数据的时候，可能会导致节点的元素超过 M-1 的情况。此时我们需要将这个节点分裂成为两个节点，然后递归的考察当前节点的父节点是否满足 B + 树的约束。
更新操作的过程可以看做先删除然后插入
索引空洞
通过上面我们可以看到 B + 树维护索引的过程中，频繁的插入删除会导致，一个节点上存储的索引或者元素个数变的稀疏，会出现大小不同的空洞，这写空洞占用了存储空间但并不实际存储任何数据。
性能降低：大量磁盘空洞的出现会导致我们在查询数据的时候，需要扫描更多的节点，而更多的 B+ 树节点意味着更多磁盘 IO 消耗。
额外磁盘空间消耗：大量的空洞不存储任何数据
我们可以通过重建表的方式减少主键索引的空洞
我们可以通过 alter table Student engine=InnoDB 来重建表 Student
我们扫描所有的 Student 的行，通过这些行生成新的 B+ 树索引表，存储到临时文件中。在上面这个过程中我们使用一个 raw log 日志文件记录此时表 Student 上所有的操作。在新的 B+ 树索引存储完成后，将 raw log 上的操作应用到新的索引上，最后用新的 B+ 树索引替换 Student 的数据文件
InnoDB 的表实际是怎么存储的
在 InnoDB 中索引分为主键索引和非主键索引：如果我们在创建表的时候没有指定主键索引 InnoDB 会默认分配一个 RowID 作为主键索引
主键索引
Mysql 中的表是根据主键建立的一颗 B+ 树 , 树的叶子结点存储的是完整一行数据
非主键索引
其它非主键的索引也会根据索引的键值建立一颗 B+ 树，树的叶子结点存储的是主键的值
主键索引和非主键索引的区别
Shell
Copy
CREATE TABLE student(id int primary key, name varchar(32), age int, grade int,
score int, index(name)) engine=InnoDB;
对于上面这个 student 表上面有两个索引
一个是 id 的主键索引，另一个是 name 的非主键索引
下面我们往这个 student 表中插入一些简单的数据方便我们后续进行分析，下面是插入后的数据：
Shell
Copy
mysql> SELECT * from student;
+----+-------+------+-------+-------+
| id | name | age | grade | score |
+----+-------+------+-------+-------+
| 0 | ben | 10 | 3 | 61 |
| 1 | alex | 11 | 3 | 81 |
| 2 | alice | 13 | 2 | 24 |
| 3 | zoe | 9 | 1 | 64 |
| 4 | jod | 12 | 4 | 66 |
| 5 | ken | 12 | 3 | 46 |
| 6 | amy | 10 | 4 | 66 |
| 7 | peter | 11 | 4 | 56 |
| 8 | frank | 12 | 3 | 76 |
| 9 | marsh | 9 | 2 | 35 |
| 10 | mark | 10 | 3 | 85 |
+----+-------+------+-------+-------+
11 rows in set (0.00 sec)
在我们执行 select * from student where id = 0 的时候，会直接在主键索引树上查找结果，但是对于 select * from student where name = "ben" 则会需要先在 name 的索引树上查询到对应数据项的主键，然后再次从主键索引树上进行查找，这个过程称为回表。
主键索引设置成自增的必要性
因为 B+ 树上结构的特定，主键按照自增顺序进行插入的，可以保证主键索引的结构是紧凑的，不会出现大量的页分裂的情况。相反非主键索引由于其插入绝大部分场景下都是随机写入的，所以会有大量页分裂的情况，磁盘的空间是不紧凑的也就意味着扫描相同的行，在主键上扫描会比非主键上扫描需要的磁盘 io 更少。
当然某些场景我们可以不需要使用自增索引，比较简单的键值对存储的场景。此时将键值对的键作为主键索引，在查询的时候可以避免回表操作。但这种场景使用 Mysql 来进行存储性能是很差的，因为非连续的键在存储的时候会有大量的也分裂和合并操作。
回表
先在特定的索引树上查询到对应数据项的主键，然后再次从主键索引树上进行查找，这个过程称为回表
由于回表操作的所以在普通索引上查询的时候会比主键索引上需要额外的 IO 操作，下面我们可以想下通过什么方式可以尽量避免这个回表的出现影响我们的性能。
索引覆盖
查询的所有字段都在非主键索引中包含，不需要回表的过程我们称为索引覆盖
把上面的查询 select * from student where name = "ben" 改为 select id from student where name = "ben" 由于 ID 的值已经包含在 name 索引树上，所以不需要进行回表查询，减少索引树的查询次数可以调高查询性能。
常规索引覆盖的手段就是对于高频查询请求简历联合索引，这个联合索引包含我们需要查询的数据不需要进行回表查询，所以提高性能。
Shell
Copy
mysql> explain select * from student where name = "ben";
+----+-------------+---------+------------+------+---------------+------+---------+-------+------+----------+-------+
| id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra |
+----+-------------+---------+------------+------+---------------+------+---------+-------+------+----------+-------+
| 1 | SIMPLE | student | NULL | ref | name | name | 131 | const | 1 | 100.00 | NULL |
+----+-------------+---------+------------+------+---------------+------+---------+-------+------+----------+-------+
1 row in set, 1 warning (0.00 sec)
mysql> explain select id from student where name = "ben";
+----+-------------+---------+------------+------+---------------+------+---------+-------+------+----------+-------------+
| id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra |
+----+-------------+---------+------------+------+---------------+------+---------+-------+------+----------+-------------+
| 1 | SIMPLE | student | NULL | ref | name | name | 131 | const | 1 | 100.00 | Using index |
+----+-------------+---------+------------+------+---------------+------+---------+-------+------+----------+-------------+
1 row in set, 1 warning (0.00 sec)
联合索引
联合索引的索引项在 B+ 树中是按照字段顺序进行组织的, 比如上面的表 student 中我们创建一个(age，score, grade) 的索引，这颗索引树中的索引项就是类似 "11_81_3" 这种形式进行组织的。
Shell
Copy
// 创建索引
CREATE INDEX age_score_grade ON student (age, score, grade);
// 查询表中的索引
SHOW INDEX from student;
+---------+------------+-----------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+---------+------------+
| Table | Non_unique | Key_name | Seq_in_index | Column_name | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment | Index_comment | Visible | Expression |
+---------+------------+-----------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+---------+------------+
| student | 0 | PRIMARY | 1 | id | A | 11 | NULL | NULL | | BTREE | | | YES | NULL |
| student | 1 | name | 1 | name | A | 11 | NULL | NULL | YES | BTREE | | | YES | NULL |
| student | 1 | age_score_grade | 1 | age | A | 5 | NULL | NULL | YES | BTREE | | | YES | NULL |
| student | 1 | age_score_grade | 2 | score | A | 11 | NULL | NULL | YES | BTREE | | | YES | NULL |
| student | 1 | age_score_grade | 3 | grade | A | 11 | NULL | NULL | YES | BTREE | | | YES | NULL |
+---------+------------+-----------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+---------+------------+
5 rows in set (0.00 sec)
索引最左前缀
索引最左前缀匹配是指：联合索引的最左连续 N 个字段或者字符串索引最左 M 个字符也可以作为索引加速查询
这个特性的原理我们可以根据联合索引的设计规则和 B + 树的特性分析， B + 树在每一个节点设计索引项的时候将子节点的最大索引项作为父节点的索引，所以我们在搜索节点的过程中对于联合索引 AB 的索引树搜索路径和 索引 A 的搜索路径一样。
我们可以利用这个特性，把很多联合索引合并，这样可以减少很多索引树的创建和维护的开销
这个特性还可以对具体的一个字段的做到做前缀匹配的功能，比如 select * from student where name = "b*" 就可以用到 (name,age) 这个索引进行加速查询
索引下推优化
在前面最左前缀匹配的过程中，如果没有完全命中，就需要全部回表进行一个个的比对。 这样其实是比较低效的过程，我们可以利用索引项中的其它字段进行过滤减少回表查询的次数。比如我们需要在索引(age,score,grade) 查询年纪是 age = 10，grade=3 时匹配到 age 字段后，如果没有索引下推优化所有年纪是10 的学生都需要进行回表查询，而利用索引下推，我们会过滤只有当 grade = 3的学生才进行回表查询。
Shell
Copy
select * from student where age=10;
+----+------+------+-------+-------+
| id | name | age | grade | score |
+----+------+------+-------+-------+
| 0 | ben | 10 | 3 | 61 |
| 6 | amy | 10 | 4 | 66 |
| 10 | mark | 10 | 3 | 85 |
+----+------+------+-------+-------+
如果没有索引下推优化这里 我们需要回表 3 次，当使用到了索引下推优化时，grade = 4 的行被过滤掉了。
通过 explain 我们可以看到
Shell
Copy
explain select * from student where age=10 AND grade=3;
+----+-------------+---------+------------+------+-----------------+-----------------+---------+-------+------+----------+-----------------------+
| id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra |
+----+-------------+---------+------------+------+-----------------+-----------------+---------+-------+------+----------+-----------------------+
| 1 | SIMPLE | student | NULL | ref | age_score_grade | age_score_grade | 5 | const | 3 | 10.00 | Using index condition |
+----+-------------+---------+------------+------+-----------------+-----------------+---------+-------+------+----------+-----------------------+
1 row in set, 1 warning (0.01 sec)
普通索引和唯一索引
这两个索引的比较我们从两种操作的区别来进行对别
查询操作
对于普通索引来说，因为索引是唯一的所以在搜索索引的时候遇到第一个满足条件的索引项就会返回
而对于普通索引需要再继续往下遍历当假设索引项都是唯一时，普通索引需要比唯一索引多一次比较操作。
由于索引在读取的时候是按照页的方式读入到内存中，在内存中比较下一个元素的时间成本是非常小的，除非极端情况当前匹配的索引项是这个页的最后一个此时我们需要额外读入一个索引页进行比较。通常情况下一个索引页会包含上千个索引项，此时额外读入另一个索引页的概率就是上千分之一，也可以近视忽略不计。所以在索引本身占用空间不大的情况下两者在查询性能上几乎相同。
更新操作
在将更新操作前我们需要看下 Mysql 更新数据的逻辑，如果数据页已经加载在内存中，直接在内存中更新就可以了。如果不在内存在 InnoDB 会将这些操作先写入 change buffer 中，这样减少了读取数据页到磁盘的操作。当后面有查询操作时，将 change buffer 中的操作应用到相关页上。唯一索引需要判断数据的唯一性，判断唯一性需要将数据页读到内存中，所以不能利用这个特性进行优化。对于写多读少的场景 change buffer 会有大量的性能提升，而对于写完立即查询的场景优化比较有限，因为此时写完立即查询就会触发 change buffer 的 merge 操作，还需要维护 change buffer 的开销。
字符串索引
在有必要为字符串创建索引的时候，字符串长度其实是非常大的如果不加以限制可能会导致我们的索引占用空间很大。我们可以在创建字符串索引的时候指定索引的字节长度，这样就可以节省索引所占用的空间。在限定特定的字符串长度作为索引以后，索引的匹配是按照最左前缀规则进行匹配的，由于精度的丢失就可能增加额外的索引扫描次数。扫描次数的增加往往是因为，我们缩小了索引长度而带来的索引区分度降低导致的。此时我们可以用一些小技巧在一些特定的业务场景，及时缩小了索引长度，索引区分度也相对比较好。
身份证号，手机号 这类前面大量字节位相同，后面的字节区分度高；我们可以将这类字符串倒序后存储
完全无规则且长度较长的字符串，我们可以使用 hash 算法 的 hash 值作为索引，比如图片名称，文章名称等等
索引选择
数据库索引的选择是在，优化器里面的工作。通常优化器会选择一个执行代价最小的索引去执行。这个最小代价的评估标准有：扫描行数，访问磁盘的 io 数，主键索引和非主键索引，是否排序等待因素。
扫描行数怎么计算，更具索引上不同值的个数进行分析，不同值的个数也称为 Cardinality 基数。我们可以通过 show index from student 来进行查看
Shell
Copy
+---------+------------+-----------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+---------+------------+
| Table | Non_unique | Key_name | Seq_in_index | Column_name | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment | Index_comment | Visible | Expression |
+---------+------------+-----------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+---------+------------+
| student | 0 | PRIMARY | 1 | id | A | 11 | NULL | NULL | | BTREE | | | YES | NULL |
| student | 1 | name | 1 | name | A | 11 | NULL | NULL | YES | BTREE | | | YES | NULL |
| student | 1 | age_score_grade | 1 | age | A | 5 | NULL | NULL | YES | BTREE | | | YES | NULL |
| student | 1 | age_score_grade | 2 | score | A | 11 | NULL | NULL | YES | BTREE | | | YES | NULL |
| student | 1 | age_score_grade | 3 | grade | A | 11 | NULL | NULL | YES | BTREE | | | YES | NULL |
+---------+------------+-----------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+---------+------------+
5 rows in set (0.03 sec)
InnoDB 中基数是怎么计算的，是通过采样进行计算的，当变更的数据行超过总行数一定百分比时，会选取一定数量的数据页进行采样统计。这两个值可以通过 innodb_stats_persistent 进行设置。
索引选择失效
基数统计不正确，使用 analyze table t 重新统计索引信息
Shell
Copy
analyze table student;
+---------------+---------+----------+----------+
| Table | Op | Msg_type | Msg_text |
+---------------+---------+----------+----------+
| db.student | analyze | status | OK |
+---------------+---------+----------+----------+
1 row in set (0.00 sec)
虽然通过 explain 语句看起来不是最优的选择，但实际执行很优。这种有很多情况可以导致 innoDB 没有用上最优的索引，但是其实它可能消耗更小的磁盘 IO。比如在 InnoDB 中的比较操作时，如果优化器发现结果集会扫描的比例占整个表一个很大的比例的时候，它会放弃使用索引。这是因为使用一个不紧凑的非主键索引进行大量的扫描，并且还需要进行回表操作的效率其实不如直接对主键索引进行全表扫描来的高效。
可以看到下面这个例子
Shell
Copy
mysql> explain select * from student where age > 12;
+----+-------------+---------+------------+-------+-----------------+-----------------+---------+------+------+----------+-----------------------+
| id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra |
+----+-------------+---------+------------+-------+-----------------+-----------------+---------+------+------+----------+-----------------------+
| 1 | SIMPLE | student | NULL | range | age_score_grade | age_score_grade | 5 | NULL | 1 | 100.00 | Using index condition |
+----+-------------+---------+------------+-------+-----------------+-----------------+---------+------+------+----------+-----------------------+
1 row in set, 1 warning (0.00 sec)
mysql> explain select * from student where age > 8;
+----+-------------+---------+------------+------+-----------------+------+---------+------+------+----------+-------------+
| id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra |
+----+-------------+---------+------------+------+-----------------+------+---------+------+------+----------+-------------+
| 1 | SIMPLE | student | NULL | ALL | age_score_grade | NULL | NULL | NULL | 11 | 100.00 | Using where |
+----+-------------+---------+------------+------+-----------------+------+---------+------+------+----------+-------------+
1 row in set, 1 warning (0.01 sec)
InnoDB 选择器的一些异常情况,比如下面的例子：
Shell
Copy
// 给学生表新增一个 score 索引
create index score on student (score);
Query OK, 0 rows affected (0.03 sec)
Records: 0 Duplicates: 0 Warnings: 0
// 给学生表新增一个 grade 索引
create index grade on student (grade);
Query OK, 0 rows affected (0.01 sec)
Records: 0 Duplicates: 0 Warnings: 0
show index from student;
+---------+------------+-----------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+---------+------------+
| Table | Non_unique | Key_name | Seq_in_index | Column_name | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment | Index_comment | Visible | Expression |
+---------+------------+-----------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+---------+------------+
| student | 0 | PRIMARY | 1 | id | A | 11 | NULL | NULL | | BTREE | | | YES | NULL |
| student | 1 | name | 1 | name | A | 11 | NULL | NULL | YES | BTREE | | | YES | NULL |
| student | 1 | age_score_grade | 1 | age | A | 5 | NULL | NULL | YES | BTREE | | | YES | NULL |
| student | 1 | age_score_grade | 2 | score | A | 11 | NULL | NULL | YES | BTREE | | | YES | NULL |
| student | 1 | age_score_grade | 3 | grade | A | 11 | NULL | NULL | YES | BTREE | | | YES | NULL |
| student | 1 | score | 1 | score | A | 10 | NULL | NULL | YES | BTREE | | | YES | NULL |
| student | 1 | grade | 1 | grade | A | 4 | NULL | NULL | YES | BTREE | | | YES | NULL |
+---------+------------+-----------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+---------+------------+
7 rows in set (0.00 sec)
// 查询年纪等于 3 成绩在 30 到 80 直接的学生信息，并按成绩排序取其中最低一个
explain select * from student where grade = 3 AND score between 30 and 80 order by score limit 1;
+----+-------------+---------+------------+-------+---------------+-------+---------+------+------+----------+------------------------------------+
| id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra |
+----+-------------+---------+------------+-------+---------------+-------+---------+------+------+----------+------------------------------------+
| 1 | SIMPLE | student | NULL | range | score,grade | score | 5 | NULL | 8 | 45.45 | Using index condition; Using where |
+----+-------------+---------+------------+-------+---------------+-------+---------+------+------+----------+------------------------------------+
1 row in set, 1 warning (0.00 sec)
我们可以发现在上面的查询中 grade= 3 的 rows 行数只有 5 个，而我们的语句没有使用 grade 索引而选择了 score 索引，这是因为我们在查询语句上制定了按照 score 进行排序，且只获取其中的一个；这会让优化器的算法认为通过 score 索引的代价更低，因为 score 索引在 B+ 树是天然有序存储的。如果我们去掉 order by score 或者 limit 1 再或者调大 limit 的值，都会选择 grade 索引。
Shell
Copy
mysql> explain select * from student where grade = 3 AND score between 30 and 80 limit 1;
+----+-------------+---------+------------+------+---------------+-------+---------+-------+------+----------+-------------+
| id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra |
+----+-------------+---------+------------+------+---------------+-------+---------+-------+------+----------+-------------+
| 1 | SIMPLE | student | NULL | ref | score,grade | grade | 5 | const | 5 | 72.73 | Using where |
+----+-------------+---------+------------+------+---------------+-------+---------+-------+------+----------+-------------+
1 row in set, 1 warning (0.01 sec)
mysql> explain select * from student where grade = 3 AND score between 30 and 80 order by score;
+----+-------------+---------+------------+------+---------------+-------+---------+-------+------+----------+-----------------------------+
| id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra |
+----+-------------+---------+------------+------+---------------+-------+---------+-------+------+----------+-----------------------------+
| 1 | SIMPLE | student | NULL | ref | score,grade | grade | 5 | const | 5 | 72.73 | Using where; Using filesort |
+----+-------------+---------+------------+------+---------------+-------+---------+-------+------+----------+-----------------------------+
1 row in set, 1 warning (0.00 sec)
mysql> explain select * from student where grade = 3 AND score between 30 and 80 order by score limit 5;
+----+-------------+---------+------------+------+---------------+-------+---------+-------+------+----------+-----------------------------+
| id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra |
+----+-------------+---------+------------+------+---------------+-------+---------+-------+------+----------+-----------------------------+
| 1 | SIMPLE | student | NULL | ref | score,grade | grade | 5 | const | 5 | 72.73 | Using where; Using filesort |
+----+-------------+---------+------------+------+---------------+-------+---------+-------+------+----------+-----------------------------+
1 row in set, 1 warning (0.00 sec)
对于这种异常情况我们应该怎么处理
使用 force index 命令指定特定的查询索引
修改 查询语句 把
新建更合适的索引，或者移除无用的索引
Foreversmart