索引类型

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

哈希表

哈希表是一种以键 - 值（key-value）存储数据的结构，我们只要输入待查找的键即 key，就可以找到其对应的值即 Value
不可避免地，多个 key 值经过哈希函数的换算，会出现同一个值的情况。处理这种情况的一种方法是，拉出一个链表。
哈希表这种结构适用于只有等值查询的场景。比如 Memcached 及其他一些 NoSQL 引擎

有序数组

而有序数组在等值查询和范围查询场景中的性能好
有序数组索引只适用于静态存储引擎。比如你要保存的是 2017 年某个城市的所有人口信息，这类不会再修改的数据。

二叉搜索树

极客时间，二叉搜索树

二叉搜索树的特点是：父节点左子树所有结点的值小于父节点的值，右子树所有结点的值大于父节点的值。
这样如果你要查 ID_card_n2 的话，按照图中的搜索顺序就是按照 UserA -> UserC -> UserF -> User2 这个路径得到。这个时间复杂度是 O(log(N))。
当然为了维持 O(log(N)) 的查询复杂度，你就需要保持这棵树是平衡二叉树。为了做这个保证，更新的时间复杂度也是 O(log(N))。

N叉搜索树

二叉树是搜索效率最高的，但是实际上大多数的数据库存储却并不使用二叉树。其原因是，索引不止存在内存中，还要写到磁盘上。
每一次的下钻搜索都需要读一次磁盘IO，当树越高的时候磁盘的IO就会很大，因此会产生磁盘IO瓶颈，对于基于磁盘的一般采用N叉树解决
“N 叉”树中的“N”取决于数据块的大小。

以 InnoDB 的一个整数字段索引为例，这个 N 差不多是 1200。这棵树高是 4 的时候，就可以存 1200 的 3 次方个值，这已经 17 亿了。考虑到树根的数据块总是在内存中的，一个 10 亿行的表上一个整数字段的索引，查找一个值最多只需要访问 3 次磁盘。其实，树的第二层也有很大概率在内存中，那么访问磁盘的平均次数就更少了。

N 叉树由于在读写上的性能优点，以及适配磁盘的访问模式，已经被广泛应用在数据库引擎中了。

InnoDB 索引模型

InnoDB索引结构

聚簇索引与非聚簇索引：聚簇索引包含了所有数据，非聚簇索引至包含了主键ID，需要回表查询其他的数据
主键索引与非主键索引
1. 如果语句是 select * from T where ID=500，即主键查询方式，则只需要搜索 ID 这棵 B+ 树；
2. 如果语句是 select * from T where k=5，即普通索引查询方式，则需要先搜索 k 索引树，得到 ID 的值为 500，再到 ID 索引树搜索一次。这个过程称为回表。
  也就是说，基于非主键索引的查询需要多扫描一棵索引树。因此，我们在应用中应该尽量使用主键查询。

索引维护

顺序插入，直接在树末尾插入数据，不会使得树进行数据移动等其它操作
中间数据插入，需要在树中间插入数据，如果对应位置满了无法再添加，则需要进行页分裂
主键长度要小，节点占用的空间小，一个磁块容纳的节点数就越多，B+树层级就越小；因此一般采用自增主键

索引查询

引用

回表，查询索引中没有包含返回字段的值，则需要再次查询主键索引中的数据，称为回表

覆盖索引：索引中覆盖了返回字段，包含了返回字段就不用回表从主键索引中查询了

联合索引左匹配原则

最左前缀原则

索引下推：
MySQL5.6之后引入，在索引中存在条件字段时会先索引和判断是否满足，过滤掉不满足的数据记录，减少回表次数
如:select * from tuser where name like '张%' and age=10 and ismale=1;

图 3 中，在 (name,age) 索引里面我特意去掉了 age 的值，这个过程 InnoDB 并不会去看 age 的值，只是按顺序把“name 第一个字是’张’”的记录一条条取出来回表。因此，需要回表 4 次。
图 4 跟图 3 的区别是，InnoDB 在 (name,age) 索引内部就判断了 age 是否等于 10，对于不等于 10 的记录，直接判断并跳过。在我们的这个例子中，只需要对 ID4、ID5 这两条记录回表取数据判断，就只需要回表 2 次。

普通索引和唯一索引

引用极客时间林晓斌

||普通索引|唯一索引|
|—|—|—|
|是否重复|可重复|不可重复|
|索引逻辑|查询时找到了满足条件的值还会继续找下去，直到找到不满足的值|查找到了满足条件的值则会停止|
|数据变更-在内存|修改内存数据|修改内存数据|
|数据变更-不在内存| 数据写入 buffer中| 读取磁盘数据，再执行修改|

索引逻辑： InnoDB在索引的时候会读取索引树的磁盘快，一般而言，一个块上有上千条数据，而满足条件继续查找和满足条件停止查找，其实对于磁盘来说读取次数基本一致，因此效率差异基本忽略

数据变更的逻辑： InnoDB在数据变更的时候会判断数据是否在内存中，如果在内存中的话则直接保存在内存，如果不在内存的话则存在两种情况

普通索引的情况，如果为普通索引，MySQL不需要判断磁盘的数据，则直接将数据写在change buffer中，待下一次读取数据时将change buffer数据写入磁盘中，MySQL也会定时刷数据到次哦按
这里change buffer是一块持久化的空间，在内存中存在，也在磁盘中有拷贝；
在写入多的情况下会连续写入change buffer中，减少读磁盘的次数，从而提升效率。
唯一索引的情况，MySQL因为需要判断数据唯一性，因此不会使用change buffer，而直接读取磁盘的数据进行操作，因此效率会低

从以上看来，一般情况下，普通索引的效率是优于唯一索引。但是在写完数据之后立马会查询数据的情况下普通索引的change buffer的逻辑反而起了副作用，这时候一般解决就是改成唯一索引或者关掉change buffer。

关于change buffer是先写内存，在写磁盘，如果写完内存断电了会导致数据不一致吗
其实不会，虽然是只更新内存，但是在事务提交的时候，我们把 change buffer 的操作也记录到 redo log 里了，所以崩溃恢复的时候，change buffer 也能找回来。

优化器选择索引

引用极客时间

优化器选择索引的目的，是找到一个最优的执行方案，并用最小的代价去执行语句。在数据库里面，扫描行数是影响执行代价的因素之一。扫描的行数越少，意味着访问磁盘数据的次数越少，消耗的 CPU 资源越少。
当然，扫描行数并不是唯一的判断标准，优化器还会结合是否使用临时表、是否排序等因素进行综合判断。

优化器选择索引是根据采样统计、扫描行数预估、是否回表及开销等选择的

索引分区度

一个索引上不同的值越多，这个索引的区分度就越好。而一个索引上不同的值的个数，我们称之为“基数”（cardinality）。也就是说，这个基数越大，索引的区分度越好。
通俗的说就是索引要选择内容重复度很小的字段不要选择枚举等只有少数几个的，没有意义。

采样统计

MySQL索引的选择是根据统计信息来的，采样统计原理：
InnoDB 默认会选择 N 个数据页，统计这些页面上的不同值，得到一个平均值，然后乘以这个索引的页面数，就得到了这个索引的基数。
统计信息在每次超过表行数的1/M就会触发，在 MySQL 中，有两种存储索引统计的方式，可以通过设置参数 innodb_stats_persistent 的值来选择：

设置为 on 的时候，表示统计信息会持久化存储。这时，默认的 N是20，M是10。
设置为 off 的时候，表示统计信息只存储在内存中。这时，默认的 N是8，M是16。

有时候采用统计的数据不准确，如一个事务开启了一致性视图，那么另一个事务删掉所有数据在新插入数据的话，实际上数据的两个版本都在索引上，要等到第一个事务关闭了才正常。

扫描行数预估

根据统计信息，就可以初步预估扫描的行数，然后就自动选择正确的索引，但是MySQL索引有时候会选择扫描行数较多的主键索引或全表扫描，因为普通索引执行了后还是会走主键索引，优化器判断两次扫描的行数比直接走全表扫描或者主键索引开销更大（虽然有时候并不是这样）
这种情况就需要优化索引了

索引优化

通过explain命令查到rows的数据比实际差距大，可以执行 analyze table <t>命令重建统计信息
手动修改SQL引导走正确的索引（不容易写，适用性小）
强制走某个索引select * from t force index(a) where a between 1 and 1000 and b between 50000 and 100000 order by b limit 1这种也不建议，阿里巴巴开发手册严禁了的
新建合适的索引，或删掉不需要的索引。

字符串索引

前缀索引

字符串索引典型的就是邮箱、身份证，由于占用空间大，一个索引树节点上能放的数据变少，可能导致当存大量数据的时候出现4层树结构，一般我们不要出现树的层级加深的情况
这种场景下我们就需要减小索引的长度

索引的建立可以是直接索引整个字段，也可以取用前缀建立索引

-- 索引整个字段
mysql> alter table SUser add index index1(email);
-- 索引前6个字符
mysql> alter table SUser add index index2(email(6));

索引前N个字符，建立索引的时候空间占用就变小了。

但是索引匹配上了还需要通过主键索引再次查找到字段的完整信息然后比对，减小索引会面临问题，

对于相同的前缀会查询多条数据做匹配，导致多次回表
对于原本可以通过覆盖索引来避免回表的，由于索引中数据不全，必须得回表查询信息，导致回表

因此建立前缀索引需要控制好长度，下面给出一个计算长度的方案

-- 查询到总的不同的值的个数
select count(distinct email) as L from SUser;

-- 查询不同的长度的个数，控制可以接收损失的比例，如5%（用查询出的除以L ） 计算出有多少个不同的数据合适
select 
count(distinct left(email,4)）as L4, 
count(distinct left(email,5)）as L5, 
count(distinct left(email,6)）as L6, 
count(distinct left(email,7)）as L7
-- count(......视实际情况
from SUser;

通过以上可以确定出在满足不同数据的情况下前缀多少合适

倒序索引和 Hash索引

在比如身份证这种，前面很长一截都是相同的，因此即使建立前缀索引也无法减小索引长度，这时候可使用倒序索引或crc32()Hash索引来解决

身份证倒序后得到的数据基本上是不同的
采用crc32()Hash可以减小长度，并且大部分数据也不相同

它们的区别，主要体现在以下三个方面：

从占用的额外空间来看，倒序存储方式在主键索引上，不会消耗额外的存储空间，而 hash 字段方法需要增加一个字段。当然，倒序存储方式使用 4 个字节的前缀长度应该是不够的，如果再长一点，这个消耗跟额外这个 hash 字段也差不多抵消了。
在 CPU 消耗方面，倒序方式每次写和读的时候，都需要额外调用一次 reverse 函数，而 hash 字段的方式需要额外调用一次 crc32() 函数。如果只从这两个函数的计算复杂度来看的话，reverse 函数额外消耗的 CPU 资源会更小些。
从查询效率上看，使用 hash 字段方式的查询性能相对更稳定一些。因为 crc32 算出来的值虽然有冲突的概率，但是概率非常小，可以认为每次查询的平均扫描行数接近 1。而倒序存储方式毕竟还是用的前缀索引的方式，也就是说还是会增加扫描行数。

他们的缺点：都不支持范围查询