Mysql简叙

什么是索引

对于索引的定义你可能并不知道，但是我们日常生活中无时不刻都有用到。当你打电话给某人时，手机通讯录会按照名字的首字母分组排序，然后你就能根据用户名很快的找到对应的手机号。在看书时我们想找到相关章节我们会通过书中的目录来找到对应的页码，然后直接翻到我们想看的内容。像通讯录、目录等等这些都是索引，而索引的作用也很明显，它就是为了提高查询的效率。你试想一下，如果让你找到字典中的一个字，你只能从第一页开始找一只到找到这个字，这个效率是有多低。

在关系型数据库中，索引指的就是对数据库中一列或者多列值就行排序的存储结构。而索引的加入，能让数据库查询速度得到质的改变，特别是对于数据量大的表。提高查询效率这个是索引的作用也是我们大多数程序追求的目标，但是索引也会带来一些负面影响。例如索引需要占用磁盘空间，简单的说索引也是一种数据，它也是需要存储在服务器上。同时当原始数据进行插入和修改时，需要更新索引数据，这会导致程序的写效率的下降。所以如果正确的使用索引就显得更加重要了，正确合理的使用索引能大大提高我们程序的运行效率，反之即不能提升程序的效率，反而降低了系统写的效率。

索引类型

上面了解了什么是索引以及索引的作用，接下来我们来聊聊索引的类型。实现索引的方式不同从而导致索引的类型不同，不同的索引类型所适应的场景也不同。例如我们可以使用二叉树来实现索引，使用hash来实现索引，还可以使用B+Tree树来实现索引等等。

为什么有这么多种方式来实现索引呢？难道就没有一种最好的吗？答案是没有绝对最好的实现方式，只有在某些场景中最合适的。下面我们列举几种在Mysql中比较常用的索引类型，需要注意的是，Mysql的索引是在存储引擎层面实现的，所以不同的存储引擎在实现细节上会有差别，而且并不是所有引擎都支持所有的索引。

B+Tree

数据页

为了让你更好的了解B+Tree索引，我们这里先了解一下数据页。InnoDB中管理存储空间的最小单位就是数据页，这个大小默认是16K。数据页的类型有很多种，但是我们这里只关注表中数据存储的页类型，官方把这种页叫做索引页。这个数据页的结构长啥样呢？

页数据结构

上面就是一个数据页的大致结构，实际上会比这个复杂一点，不过这里我们关注三块，表中的数据，空闲空间，Page Directory。表中的数据就是我们数据库中表里面的数据，表中的记录数据按照顺序被存放在这个里面。空闲空间就是这个页中还没有用完的空间，每次当我们向表中插入一条数据，空间空间的大小就变小一点。

Page Directory是用来加快页中数据查询的，请注意是页中的数据，因为页的大小有16K，其他结构并占不了多大的空间，大部分空间是用来存储用户的数据的，所以为了加快在一个页内搜索速度才有了Page Directory，你可以简单的认为在一个页内搜索速度就是用的二分法，想想是不是查询很快呢。

那如果我的页里面的数据存满了呢？不用说那就再创建一个新的页呗。整个过程如下图所示：

页创建过程

注意这里面只是一个简图，为了便于理解我这里省去数据页的其他结构，只保留了用户数据。而实际上这些页的头部会保存上一页的页号和下一页的页号。正是通过这些信息，所有的页被一个个的串起来了，就是像双向链表一样。

下面我们用以下的表结构来作为示例演示：

CREATE TABLE `t_student` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `name` varchar(255) COLLATE utf8mb4_bin NOT NULL COMMENT '名字',
  PRIMARY KEY (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_bin;

而对应的数据页如下：

页内数据和页之间的结构

从上面的数据页编号可以看出，为什么不是递增的呢？因为在物理上这些数据页并不是连续的，它只能保证页内的数据是物理上连续的。再说如果表中存储了很多数据，要保证这些页全部是物理上连续的也不太现实。这里说的的连续是指在硬盘上物理连续，因为顺序I/O和随机I/O它们的效率是不一样的，特别是针对于机械硬盘。

索引

如果现在我们要通过ID查询一条数据该怎么办呢？如果不做任何优化的情况下你只能从第一个数据页开始遍历，然后在页内你可以通过Page Directory快速查找你要找的数据是不是在其中。如果找到了就返回，如果没找到继续读取下一个数据页，然后查找，如此反复下去。

我们前面说过，数据页之间在物理上不是连续的，这就会导致一个问题，如果数据位置靠后，那么会有大量的随机I/O。

总结上面两点我们现在的问题主要有两点，第一我们无法快速的知道我们的数据存在那个数据页中，只能通过从第一个数据页节点往后依次遍历（注意：页内是能通过二分法快速定位的）。这样也就导致了第二个问题，遍历页时大量随机I/O。如果现在我们能快速找到我们的数据存在哪个页，那是不是就能解决上面两个问题呢？

二叉树

如果我们将每个页中最小值和页号作为用户数据，然后把这些数据放入到页中形成一个二叉树，二叉树的查询就跟二分法一样，那是不是我们就能提高搜索速度呢？

使用二叉树作为索引

按照我们上面说的，我们使用二叉树做索引将数据存好了。现在如果我要搜索ID为12的同学，我该怎么搜呢？首先我不需要遍历每个页，我从第一层节点开始搜索，因为12最靠近7，所以选右节点页21号；然后判断12靠近10，所以选页9号，然后再页9号里面通过二分法找找到数据12号同学小蓝（页内查找）。

通过上面这种方法，我们原先需要经过读取4次随机I/O，然后进行4次页内查找才能找到，现在变成3次随机I/O，1次页内查找。从上面我们可以知道，我们查询的消耗为树高度+1加上页内查找，而每次读取页为随机I/O。假设我们有100万条数据，每页能容纳100条数据，对应的二叉树叶子节点就为1万个，那么树的层高至少为14层（2^14），那么每次查询需要15次随机I/O和一次页内查找。假设每次随机I/O需要10ms，那么算下来15次随机I/O需要耗时150毫秒，想象这该得有多慢，所以我们必须要降低树的高度，这样才能减少随机I/O的次数。

B+Tree

上面我们知道如果想加快查询速度还需要降低树的高度，那么如何降低树的高度呢？如果我们不是使用二叉树，简单的说就是节点不再是存储两个节点，而是存储多个节点呢？这样是不是就能降低树的高度呢？

首先我们需要明白一点，我们对页内数据的查找肯定是比多次读去随机I/O要快的，我们降低了树的高度，减少了随机I/O次数，增加了页内搜索的次数。一次页内搜索先比与多次随机I/O读取的消耗我们几乎可以忽略不计。

使用B+Tree作为索引

按照我们之前的说法，我们将数据如上图存放（PS:请饶恕我没有耐心画全，因为真的很麻烦，而且没有合适的画图软件，求推荐）。经过修改之后，我们还是假设存100万条数据，每页能存放100条数据。如果树高为1，则我们能存100个页，如果树高为2，那我们能存1万个页（100100）。如果树高为3，那能存100万个页（100100*100）。

现在再来分析我们的查询消耗，我们需要3次随机I/O加上一次页内查找。之前忘记说了，我们的数据存在叶子节点，查找数据位于哪个页需要搜索的次数为树的高度次，最后还要读取数据所在的页，所以这又是一次随机I/O，所以是树的高度+1次。我们还是假设每次随机I/O需要10ms，那么这次搜索大概需要30ms左右，相比于之前的150ms时间大大的减少了。

聚族索引

经过上面的分析，我想你对B+Tree索引有了了解。在Innodb中，我们常说到一句话即索引即数据，数据即索引，这里面讲的就是聚族索引。我们将数据存放在数据页中，这里的数据指的是表中的整行记录，包括了所有字段，而数据本身就是索引。

聚族索引有两个特点：使用主键的大小进行记录和页的排序。页内的记录是按照顺序存放形成一个单链表。而各个存放用户数据的页也是根据页内主键大小按顺序存放形成一个双向链表。存放页信息的节点和存放用户数据的节点不在同一个层级，在同一层的的页也是根据主键大小形成按顺序组成一个双向链表。第二点就是整颗B+Tree树存放了完整的用户记录。

二级索引

而作为二级索引就没有这个待遇了，它只保存了索引列和主键的信息。例如下面的表：

CREATE TABLE `t_member` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `name` varchar(64) COLLATE utf8mb4_bin DEFAULT NULL,
  `age` int(11) NOT NULL,
  `phone` varchar(32) COLLATE utf8mb4_bin DEFAULT NULL,
  `sex` varchar(32) COLLATE utf8mb4_bin DEFAULT NULL,
  PRIMARY KEY (`id`),
  KEY `name_index` (`name`) USING BTREE,
  KEY `age_sex_index` (`age`,`sex`) USING BTREE
) ENGINE=InnoDB AUTO_INCREMENT=10001 DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_bin;

在这个表结构中存在一个主键索引ID，也就是我们前面说的聚族索引。而剩下的name_index和age_sex_index则是二级索引，所以在这个表中会有三颗B+Tree树索引。其中name_index这颗树页中只存放了name和id字段信息，而age_sex_index这棵树中只存放了age，sex和id字段信息。

回表

例如现在我按名字查找用户SQL如下:

SELECT * FROM t_member WHERE `name` = '小明';

这个查询会使用name_index索引，在该索引中查询到数据之后就能获取到这条数据的id，然后我们通过id再回到聚族索引中获取到这条数据的全部信息，这个过程我们就叫回表。

索引覆盖

通过上面我们知道通过二级索引查询数据是需要回表的，毫无疑问回表是有消耗的，有没有什么办法可以优化一下？答案是索引覆盖。例如我通过姓名查找用户这个需求，我只是想查找这个用户的手机号，那么我们可以优化一下索引，我们创建一个由name和phone组成的索引，然后只返回name和phone这两个字段。

ALTER TABLE `t_member`
DROP INDEX `name_index` ,
ADD INDEX `name_phone_index` (`name`, `phone`) USING BTREE ;

我们将查询语句修改为如下：

SELECT `name`,phone FROM t_member WHERE `name` = '小明';

在上面的查询中，我们可以通过name_phone_index这个二级索引直接获取到name和phone信息，所以省去了去聚族索引中再次查找的必要，从而省去了回表的消耗，这种方式我们就叫做索引覆盖。

最左匹配

现在我们有个查询如下：

SELECT * FROM t_member WHERE phone = '15202405150';

现在我想问的是这个查询能用到索引吗？如果看懂了B+Tree索引那么你的心里一定有了答案，这个是无法用到索引的。我们直接使用EXPLAIN分析结果看看：

expalin结果.png

从上面的结果可以看出确实用不到索引。对于索引name_phone_index而言，它在页中的数据长这样：

name_phone_index页内数据

这时候的数据的排序规则是name+phone，在索引内能保证的是name+phone是有序的，而对于phone来说并不是有序的，同时对于name是有序的。如果我们通过name来查询，这个时候是能用到该索引的，而这个原则我们就叫做最左匹配原则。所以在创建索引时，索引的顺序是很重要的。

根据这个原则，我们可以省去一些不必要的索引。例如我们根据name创建了一个name_index索引，然后又根据name和phone创建了一个name_phone_index索引，这个时候我们去掉name_index索引。因为根据最左匹配原则，通过name查询时可以利用到索引的，而name_index就没有存在的必要了。

索引下推

例如现在我们有如下的查询：

SELECT * FROM t_member WHERE `name` LIKE '陈%' AND phone = '111111'

这个查询我们会利用到name_phone_index索引，但是这个索引使用会有一些限制，因为我们的查询中存在name like '陈%'，这样会导致我们无法使用的phone来进行匹配了。那是不是在这个查询中，phone这个字段的索引是不是就毫无作用了呢？答案是否定的。

回表过程

这个查询会先通过name筛选到id为1和2的记录满足条件，然后接着根据id通过回表的方式到聚族索引中找到对应的记录，然后判断phone的条件。那能不能优化一下呢？

在Mysql5.6之前是没有优化的，但是在5.6及以后的版本中，Mysql会通过索引下推的****方式来****减少回表的次数。在name_phone_index中筛选name符合要求的数据后，然后会接着在该索引中判断phone是不是满足条件，从而减少了回表的次数。在本示例中，它会取消蓝色线这次回表，因为在name_phone_index中就能判断出该记录不服和条件了。

哈希

哈希索引是基于哈希表实现的，只有精确匹配了所有索引列的查询才有效。简单的说，对于索引列的每行数据都会计算出一个哈希码（hashcode）。对于相同的数据其计算出的hash码是唯一的，但是需要注意的是不同的哈希码计算出来的数据也有可能相同，这个取决于哈希算法。算出哈希码之后，会在哈希表中保存一个指向原始数据的指针，然后通过该指针获取到原始数据。而hash索引适合的是精确值的搜索，这个是它的优势。但是它无法使用像like查询，范围查询等。

其实哈希索引跟Java中的HashMap很像，不过需要注意的是Innodb引擎是不支持hash索引的，在Mysql中Memory的默认索引类型就是Hash。鉴于我们使用的最多的是Innodb引擎，这部分只是就不具体提了。

全文索引

全文索引是一种特殊的索引类型，它查找的是文本中的关键字，而不是直接比较索引中的值。需要注意的是，全文检索它并不是像like一样的查询，在like查询中像'%world%'这种它是无法使用的索引的，即使像'world%'这种它能使用到索引也存在很大的限制。

考虑到该索引平常使用的较少这里面就不详细的介绍了。因为在很多情况下有其他很好的代替产品，像ElasticSearch，Solr等这些能提供更好的全文检索功能。如果项目只是需要简单的使用全文检索又不想引入其他组件，可以考虑使用Mysql中提供的全文索引。

总结

总的来说，Mysql中的索引有很多种类型，而且索引的实现是靠存储引擎来实现的。即使索引都叫B+Tree它也会因为引擎的不同而有所不同，同时不同的引擎支持的索引类型也不相同。但实际上我们现在使用较多的引擎就是Innodb，而Innodb中使用最多的就是B+Tree索引。所以我们在学习过程中推荐先了解Innodb相关的索引知识，然后再去学习其他引擎的索引相关知识。