MySQL 系列索引

索引的出现其实就是为了提高数据查询的效率，就像书的目录一样。索引的常见模型包括哈希表、有序数组和搜索树；

索引常见模型

hash

哈希表是一种以键-值（key-value）存储数据的结构，只要输入待查找的值即key，就可以找到其对应的值即Value。哈希的思路很简单，把值放在数组里，用一个哈希函数把key换算成一个确定的位置，然后把value放在数组的这个位置。

不可避免地，多个key值经过哈希函数的换算，会出现同一个值的情况。处理这种情况的一种方法是，拉出一个链表。

假设，现在维护着一个身份证信息和姓名的表，需要根据身份证号查找对应的名字，这时对应的哈希索引的示意图如下所示：哈希表

需要注意的是，图中四个ID_card_n的值并不是递增的，这样做的好处是增加新的User时速度会很快，只需要往后追加。但缺点是，因为不是有序的，所以哈希索引做区间查询的速度是很慢的。

所以，哈希表这种结构适用于只有等值查询的场景，比如Memcached及其他一些NoSQL引擎。

有序数组

有序数组在等值查询和范围查询场景中的性能就都非常优秀。

但是，在需要更新数据的时候就麻烦了，往中间插入一个记录就必须得挪动后面所有的记录，成本太高。

所以，有序数组索引只适用于静态存储引擎。

B+树

B+Tree是为磁盘或其它辅助存储设备设计的一种平衡查找树（满足任意节点的两个子树的高度最大差为1）。

众所周知，MySQL默认存储引擎InnoDB采用的是B+Tree索引，其特点是：

高扇出性：每个树节点只存放键值，不存放数值，而由叶子节点存放数值。这样会使树节点的度比较大，而树的高度就比较低，从而有利于提高查询效率。
叶子节点存放数值，并按照值大小顺序排序，且带指向相邻节点的指针，以便高效地进行区间数据查询
所有叶子节点与根节点的距离相同(叶子结点在同一层)，因此任何查询的效率都很相似。
B+Tree的数据更新操作不从根节点开始，而从叶子节点开始，并且在更新过程中树能以比较小的代价实现自平衡。

B+Tree索引并不能找到一个给定键值的具体行。B+Tree索引能找到的只是被查找数据行所在的页。然后数据库通过把页读入到内存，再在内存中进行查找，最后得到要查找的数据。在页中的查找可以理解为二分查找。

插入：采用旋转操作使B+Tree减少页的拆分操作；

删除：使用填充因子来控制树的删除变化；

查询性能

InnoDB存储引擎中页的大小为16KB，一般表的主键类型为int（占用4个字节）或long（占用8个字节），指针类型也一般为4或8个字节，也就是说一个页（B+Tree中的一个节点）中大概存储16KB/(8B+8B)=1K个键值（因为是估值，为方便计算，这里的K取值为10^3）。也就是说一个深度为3的B+Tree索引可以维护10^3*10^3*10^3 = 10亿条记录。

在数据库中，B+Tree的高度一般都在2~4层。MysSQL的InnoDB存储引擎在设计时是将根节点常驻内存的，也就是说查找某一键值的行记录时最多只需要1~3次磁盘I/O操作。再考虑到非叶子节点基本都会缓存在数据库的Buffer_Pool中，实际的IO次数要更少一些，因此业务无需担心因为数据量的增大导致B+Tree索引的性能有严重的劣化。

正是由于B+Tree的上述优点，它成了传统关系型数据库的宠儿。当然，它也并非无懈可击，它的主要缺点在于随着数据插入的不断发生，叶子节点会慢慢分裂——这可能会导致逻辑上原本连续的数据实际上存放在不同的物理磁盘块位置上，在做范围查询的时候会导致较高的磁盘 IO，以致严重影响到性能。

LSM 树

对于写入量比较大的服务，出于性能和存储成本考虑，DBA会建议用户使用RocksDB，而RocksDB使用的是LSM-Tree（log structed merge tree）。

MySQL索引类型

首先从索引存放的内容上分为聚簇索引（主键）和非聚簇索引（二级索引）。无论是InnoDB还是RocksDB，都是索引组织表，即每个表有且只有一个聚簇索引，存放主键和records。但可以有多个二级索引，存放二级索引值和主键的值。

索引示例

如上图所示，可以直接通过聚簇索引找到全部的records，但是通过二级索引需要先找到对应的主键，再拿着获得的主键到聚簇索引查找records，这个过程称为回表。这里要注意的一点是，虽然B+Tree的特点决定了二级索引肯定是连续的，但是回表到聚簇索引上就可能是离散的了。因此有时候用户会比较困扰，为什么只通过二级索引扫描了1000行，但是会产生MB级别的IO，因为最坏的情况可能是这1000行分布在1000个主键的page上面。

由于MySQL是索引组织表，因此即使用户剪标没有指明primary key，DB也会分配一个隐藏的row_id列作为主键。不过，在这里DBA一般建议用户还是在创建表的时候显示指明一个有自增属性的ID作为主键。

聚簇索引（又称主键索引）

聚簇索引就是按照每张表的主键构造一颗B+树，叶子节点中存放整张表的行记录数据，叶子节点即为数据页，每个数据页通过双向链表进行链接。

聚簇索引的存储并不是物理上连续的，而是逻辑上连续的:

页通过双向链表链接，页按照主键的顺序排序;

每个页中的记录也是通过双向链表进行维护，物理存储同样可以不按照主键存储;

在多数情况下，查询优化器倾向于采用聚簇索引。因为聚簇索引能够在B+树索引的叶子结点上直接找到数据，有利于对于主键的排序查找和范围查找。查询优化器能够快速发现某一段范围的数据页需要扫描。

二级索引（又称辅助索引、非聚簇索引）

叶子节点除了包含键值以外，每个叶子节点中的索引行中还包含一个书签（相应行数据的聚集索引键，即主键值）。该书签用来告诉InnoDB存储引擎哪里可以找到与索引相对应的行数据。二级索引的书签就是相应行数据的聚簇索引键（页级别）。

当通过二级索引来寻找数据时，InnoDB 存储引擎会遍历二级索引并通过页级别的指针获取指向主键索引的主键。然后再通过主键索引来找到完整的行记录。

唯一索引

顾名思义唯一索引不允许两行具有相同的索引值。因此主键也是一种特殊的唯一索引。

对于查找，唯一索引和普通索引的区别(差别很小)：

对于普通索引来说，查找到满足条件的第一个记录后，需要查找下一个记录，直到碰到第一个不满足条件的记录。
对于唯一索引来说，由于索引定义了唯一性，查找到第一个满足条件的记录后，就会停止继续检索。

对于更新，唯一索引和普通索引的区别（普通索引更优）：

唯一索引的更新不能使用change buffer，实际上也只有普通索引可以使用
对于唯一索引来说，所有的更新操作都要先判断这个操作是否违反唯一性约束。比如，要插入(4,400)这个记录，就要先判断现在表中是否已经存在k=4的记录，而这必须要将数据页读入内存才能判断。如果都已经读入到内存了，那直接更新内存会更快，就没必要使用 change buffer 了。

联合索引

联合索引是指对表上的多个列进行索引，符合向左匹配原则。联合索引的键值的数量不是1，而是大于等于2。键值都是排序的，通过叶子节点可以逻辑上顺序地读出所有数据。

要点：联合索引已经对每个键值进行了排序处理（可与 order by结合使用）；

create table buy_log(
   user_id int unsigned not null,
   buy_date date
   primary key (user_id),
   key idx_a_b(user_id, buy_date)
)

每个叶子节点包含的键值个数: select * from buy_log where user_id =2; 优化器优先选择单个索引，因为该索引的叶子节点包含单个键值，所以理论上一个页存放的记录应该更多。
能否利用多个键值的联合索引: 联合索引的每个字段都是有序的，order by 能够利用这些有序的数据，但需要满足向左匹配原则： select * from buy_log where user_id = 1 order by buy_date desc limit 3; 优化器使用了联合索引，因为第二个字段 buy_date 是有序的。

优化项：因为每次修改需要修改全部索引的B+Tree，所以索引创建多了会导致写入性能的下降，索引肯定不是越多越好。在创建索引的时候我们需要尽量创建多个索引列的联合索引。

覆盖索引

覆盖索引（covering index）指一个查询语句的数据只用从二级索引中就能够取得，不必从数据表（查询聚簇索引）中读取（不用回表）。也可以称之为实现了索引覆盖。

覆盖索引的一个好处是二级索引不包含整行记录的所有信息，故其大小要远小于聚簇索引，因此可以减少大量的IO操作；
统计查询时，选择二级索引可以减少IO操作；

create table buy_log(
    user_id int unsigned not null,
    buy_date date
    primary key (user_id),
    key idx_a_b(user_id, buy_date)
)

select count(*) from buy_log: 优化器查询二级索引进行统计，原因是二级索引比聚簇索引更小，每个叶子节点包含的数据条数更多。
select count(*) from buy_log where buy_date>= '2011-01-01' and buy_date < '2011-02-01': 统计查询，可以利用到覆盖索引中的信息，因此优化器会使用该联合索引。

使用前缀索引就用不上覆盖索引对查询性能的优化了。

hash 索引

hash索引在InnoDB引擎中叫作自适应哈希索引，它是由数据库自身根据数据的使用情况创建的，并不能人为的干预，所以叫作自适应哈希索引，采用的是哈希表数据结构，所以对于字典类型查询就非常的快，但是对于范围查询就无能为力了。DB可以通过innodb_adaptive_hash_index参数动态的开关hash索引。

Full-Text 索引

在B+Tree索引中，当执行select * from blog where content like %xxxx%语句时，索引会失效。全文索引可以有效的解决这种语句查询。全文索引是一种比较特殊的索引，一般都是基于倒排索引来实现的，es 也是使用倒排索引。倒排索引跟B+Tree索引一样也是一种数据结构，在辅助表中存储了单词与单词自身在一个或多个文档中所在位置的映射。现在有很多专门做全文索引的软件，例如solr、elasticsearch等，MySQL中的全文索引实现原理跟这些差不多。

前缀索引

对于字符串字段，可以添加前缀索引，使用前缀索引，定义好长度，就可以做到既节省空间，又不用额外增加太多的查询成本。在建立索引时关注的是区分度，区分度越高越好。因为区分度越高，意味着重复的键值越少。因此，可以通过统计索引上有多少个不同的值来判断要使用多长的前缀。

select count(distinct left(email, 4)）as L4 from SUser;

使用前缀索引都需要回表查询，就用不上覆盖索引对查询性能的优化了，这也是在选择是否使用前缀索引时需要考虑的一个因素。

最佳实践

创建一个合理有效的索引是每个MySQL用户必备的技能，在创建的时候，用户需要注意以下原则：

避免不必要/冗余的索引：索引需要额外的空间，此外还会拖慢写入的速度，因此只为查询常用的列创建索引，并且尽量避免一个列上创建多个索引；
选择索引列：索引列离散性越高选择性就越好，索引列类型尽量小；
最左匹配原则：如果查询的时候查询条件精确匹配索引的左边连续一列或几列，则此列就可以被用到；
联合索引：
- 经常用的列优先【最左匹配原则】
- 选择性（离散度）高的列优先【离散度高原则】
- 宽度小的列优先【最少空间原则】
覆盖索引：覆盖索引可减少数据库IO，将随机IO变为顺序IO，可提高查询性能。

无法使用索引的场景

如果没能很好的遵守以上原则，则会导致MySQL无法使用索引，从而导致扫描全表，DB过载，甚至系统崩溃等严重问题，常见的错误场景有以下几类：

CREATE TABLE person_info(
    id INT NOT NULL auto_increment,
    name VARCHAR(100) NOT NULL,
    birthday DATE NOT NULL,
    phone_number CHAR(11) NOT NULL,
    country varchar(100) NOT NULL,
    PRIMARY KEY (id),
    KEY idx_name_birthday_phone_number (name, birthday, phone_number) 
);

不按照顺序查询: SELECT * FROM person_info WHERE birthday = '1990-09-27';
ASC和DESC混用: SELECT * FROM person_info ORDER BY name, birthday DESC LIMIT 10;
非前缀匹配: SELECT * FROM person_info WHERE name LIKE '%As%';
排序列不包括索引列: SELECT * FROM person_info ORDER BY name, country LIMIT 10;
索引列上有计算: SELECT * FROM person_info WHERE DATEDIFF(birthday,'1990-09-27')=0；
范围查询之后的列: SELECT * FROM person_info WHERE name = 'Tony' and birthday < '1990-09-27' and pyhone_number='110';

MySQL 技术内幕：InnoDB存储引擎