索引模型

索引的模型主要有三种：键-值对、有序数组和搜索树

键-值对

键-值对的模型就是使用哈希表来存储数据，当发生哈希碰撞时，可以通过一个链表来解决冲突，不过链表太长的话也会影响查询效率。

键值对的特点是查询数据非常快，但是只能进行等值查询，不支持范围查询。键-值对的方式在NoSQL中应用较多，比如redis。

有序数组

有序数组的模型是将数据存储在一个数组模型中，然后要保持这个数组是有序的，这个有序可以是按照数据中某个字段的值进行有序排列。

有序数组查询数据可以直接采用二分法，因此时间复杂度是O(logN)。而且有序数组可以很方便的进行范围查询。有序数组的问题在于，为了维护数组的有序性，在插入时要移动插入位置后面所有的数据，这个代价非常大。因此有序数组适合为静态数据建立索引，静态数据一次建立就完成，不会有再有插入的需求。

搜索树

二叉搜索树也是有序的，左节点小于父节点，父节点小于右节点。二叉搜索树的查询复杂度也是o(logN)，更新的复杂度也是o(logN)，当然为了维持o(logN)的复杂度，需要二叉树保持平衡。

但是当数据量非常大时，二叉搜索树的高度会很高，这增加了搜索的时间。比如对于有一百万个节点的平衡二叉树，树的高度是20，假设磁盘随机读一个数据需要10ms，那么一个简单的查询都需要200ms，这个速度显然是不能被接受的。

为了减少二叉树的高度，N叉搜索树被发明出来，一个父节点下可以有N个子节点。对于一百万个节点的N叉搜索树，当N为100时，那么树的高度就已经降到3。

InnoDB索引模型

聚簇索引与非聚簇索引

聚簇索引并不是一种单独的索引类型，而是一种数据存储方式。当表有聚簇索引时，它的数据行实际上是放在索引的叶子节点上。相应的如果数据行是单独存放，而索引的叶子节点只保存了数据行指针的存储方式就是非聚簇索引。因为不可能把数据行同时放在两个不同的地方，所以一个表最多只能有一个聚簇索引。

然后我们比较一下聚簇索引与非聚簇索引的存储特性。直接引用《高性能MySQL》一书中关于聚簇索引与非聚簇索引比较的图片。左边是聚簇索引和主键索引和二级索引，右边是非聚簇索引的主键索引和二级索引。

聚簇索引与非聚簇索引的特点：

1. 聚簇索引的主键索引，数据行是和索引在一起的；

2. 非聚簇索引的主键索引，数据行和索引分开存储，索引中保存数据行的地址；

3. 聚簇索引的二级索引中，保存的是主键索引的值。之所以保存主键索引的值，而不是保存数据行的地址，是因为聚簇索引会发生页分裂，页分裂后数据存储的地址就会发生变化。当页地址发生变化后，只需要维护主键索引的数据即可，不需要维护二级索引，减少了索引的维护工作;

4. 非聚簇索引的主键索引和二级索引没有什么实质性的区别。

聚簇索引有些优点：

1. 可以把相关的数据保存在一起。比如一个用户的流水记录，按照用户的ID建立聚簇索引，这样用户所有的数据都会聚集在一起，因此查询时只需要读少数几个磁盘的数据块就可以获取一个用户所有的数据。
2. 数据访问更快。聚簇索引的数据行与索引在一起，因此在聚簇索引上搜索时，完成索引的搜索就找到了数据，不需要再进行一次磁盘IO。
3. 使用覆盖索引时可以直接使用页子节点中的主键值，因为二级索引的叶子节点上保存是主键值。

聚簇索引有些缺点：

1. 插入的速度严重依赖于插入的顺序。如果按照主键的顺序进行插入，插入可以很快。如果不按照主键的顺序进行插入，则可能产生页分裂。页分裂不仅影响插入的速度，而且原来一个页，现在分成两个页来存储，而两个页又没有都存满，占用了更多的磁盘空间。所以这就是为什么DBA总是建议在使用InnoDB引擎时，使用自增ID做主键；
2. 更新聚簇索引的代价很高，因为每个被更新的行会被移动到新的位置；
3. 二级索引需要两次查找，因为二级索引中存放的是主键的值，需要再进行一次回表操作；
4. 二级索引中存储主键的值，可能会导致二级索引占用更大的空间；

InnoDB的索引模型

InnoDB在MySQL5.5版本以后已经成为MySQL的默认存储引擎，我们来分析一个InnoDB的索引模型。InnoDB采用B+树的索引模型，InnoDB的主键索引是聚簇索引。

什么是B+树？ B+树比B树有什么优点？ B+树是如何插入和删除数据的？

以上问题，请参考这篇博客，写的非常简单易懂：B树和B+树的插入、删除图文详解

InnDB引擎采用B+树作为索引模型，对于m阶的B+树，等值查询时间复杂度为logm(N)，B+树的数据都在叶子节点上。B+树的叶子节点有指向下一个叶子节点的指针，因此范围查询也非常快。

InnoDB为了维护聚簇索引的有序性，按主键顺序插入不会引起页分裂。随机插入时，容易导致页分裂。因此一般选择自增id做主键。建表语句中常用以下方案id BIGINT UNSIGNED NOT NULL PRIMERY KEY AUTO_INCREMENT

InnoDB存储引擎必须为表指定一个主键，如果没有主键，InnoDB会选择一个唯一的非空索引代替。如果没有这样的索引，InnoDB会隐式定义一个主键来作为聚簇索引。

MySQL索引的特性

回表

我们已经知道聚簇索引的二级索引中存放的是主键的索引的值，那么通过二级索引查找数据时，首先要通过二级索引索引拿到主键索引的值，然后通过主键值去查询数据。通过主键值再去查询数据的这个过程称为回表。

最左前缀原则

每一个查询都维护一个索引时，需要建立很多索引，索引不仅占用磁盘空间，而且维护成本也很大。索引很多时，每插入一条数据，都需要向每个索引中插入一条主键值。为了减少索引的数量，可以建立联合索引，联合索引就是可以使用多个列一起建立一个索引。建立索引时要优先在已经存在的索引上扩展成联合索引，或者在已经存在的联合索引上继续添加字段。因为，索引越多，维护成本就越高，还会导致插入速度变慢等负面效应。

假设建立一张表，如下：

CREATE TABLE `t` (
  `id` int(11) NOT NULL,
  `a` varchar(32) DEFAULT NULL,
  `b` varchar(32) DEFAULT NULL,
  `c` int(11) DEFAULT NULL,
  PRIMARY KEY (`id`),
  KEY `a_b` (`a, b`),
) ENGINE=InnoDB
复制代码

这个表除了在id上建立主键索引外，还在列a和b上建立了一个联合二级索引a_b。当使用where条件where a = 'xxx' and b = 'yyy'时，可以使用索引a_b，当where条件是where a = 'xxx'时也可以使用该索引，但是单where条件是where b = 'yyy'时就不能使用该索引了。这就是最左前缀原则。

对于联合索引和最左前缀原则，还有一点需要注意的是：模糊查询和范围查询都会导致联合索引上该查询列之后的列失效。

举例来说：对于表t中的联合索引a_b如果有一个查询select * from t where a like 'test%' and b = 'luck'，会导致联合索引只使用a列来命中，b列失效了，因为在列a上已经有了模糊查询。

索引下推

select * from t where a like 'test%' and b = 'luck';
复制代码

刚刚已经分析了，这个查询会导致列b部分索引不能命中，因此a进行模糊查询命中后，就要回表查询。

如果索引上有这样四条数据，那么其是否回表的结果如下所示：

不过在mysql的5.6版本以后做了一个优化，引入了索引下推，在遍历索引的过程中，会对索引中包含的字段优先进行判断，过滤掉不满足条件的数据，减少回表的次数。

索引优化

联合索引应该怎么建

前面已经介绍了联合索引和最左前缀原则，通过联合索引可以减少索引的数量。那么建立联合索引时，应该遵循什么样的原则呢？

1. 区分度大的优先放在前面。比如一张全球人口的用户表，该表有性别，国籍，年龄等字段。那么一般情况下国籍的区分度就要比性别的区分度更高，比如满足中国人这个条件的要比满足男人这个条件的人要更少。因此建立联合索引时国籍优先考虑放在性别的前面。

2. 可以枚举的值优先放在前面。还是刚刚这张用户表，假设我们建立了(国籍，年龄，性别)这样一个联合索引key_a，如果我要查找中国男性用户，那么这个联合索引就没法用了。可是如果我们建立了(性别，国籍，年龄)这样一个联合索引key_b，这种情况下，我们要查找中国18岁的用户，那么这个索引还能用吗？当然可以，我们可以在查询时通过IN条件指定IN(男性，女性)。这样最左前缀原则能够满足。

细心的读者会发现，第一点和第二点可能会发生冲突，那么该如何决策呢？索引的选择没有唯一的标准，很多原则之前都是相互冲突的，需要根据具体的情况进行权衡。比如上面的案例中，如果将性别放在后面，虽然区分度高，但是很多情况下会导致索引直接无法命中，而将性别放在最前面，虽然区分区没有那么大，但是能保证索引命中，性能不会下降很多，所以可以考虑将性别往前放。

还有一些查询条件，需要进行范围查询或者排序，那么范围查询和排序的字段就要尽量往后放，因为范围查询以后的字段索引是不能命中的。

要不要用唯一索引

对于查询而言，普通索引命中第一条记录后还要继续往下找，而唯一索引立即就可以返回了。但是磁盘存储是以分页的形式进行存储，最小的分页是4K，当读到第一条记录时，大概率剩下的数据也在这4K的分页里，这4K的分页已经被加载进了内存。所以两者查询带来的性能影响区别不大。

对于写而言，普通索引数据插入会先写入change buf里来加速写操作。但是唯一索引为了保证唯一性，不能使用change buf，唯一索引要先查找是否已经存在相同的索引数据，不存在则插入。

如果业务上能保证唯一，则尽量使用普通索引，如果业务上不能保证唯一则考虑使用唯一索引。

要不要用UUID做主键

使用InnoDB引擎时，DBA会建议你使用自增ID做主键，而不要使用随机的UUID做主键，因为非递增的主键会导致频繁的页分裂，从而降低了插入的效率。所以一般情况下，我们会在表中添加一个自增ID字段，用该字段来作表的主键。使用自增ID做主键时，如果需要按照UUID查询用户信息时，查找就需要回表，查找的效率会低一点。

关于这一点认识，我是这样理解的：

1. 如果表中只需要一个UUID的唯一索引，那么就可以使用UUID来做主键；
2. 如果不满足条件1就用自增ID做索引；
3. 如果不知道怎么选，那么用自增ID做索引好了，这样至少不会有错。

覆盖索引

覆盖索引就是索引上的数据已经能满足该查询的需要，就不需要进行回表操作，减少IO操作，从而达到优化查询速度的目标。

在一张用户表上

CREATE TABLE `user` (
  `id` int(11) NOT NULL,
  `id_card` varchar(32) DEFAULT NULL,
  `name` varchar(32) DEFAULT NULL,
  `age` int(11) DEFAULT NULL,
  `ismale` tinyint(1) DEFAULT NULL,
  PRIMARY KEY (`id`),
  KEY `id_card` (`id_card`),
  KEY `name_age` (`name`,`age`)
) ENGINE=InnoDB
复制代码

如果以身份证号id_card建立索引，这时有个高频查询通过身份证号码查询名称，那么这个查询每次都要回表查询。这时，如果将刚刚那个索引修改为id_card和name的联合索引，那么索引上的数据就已经可以满足查询的需求，因此不需要回表查询。

控制索引长度

索引的太长首先会占用大量的磁盘空间，其次索引太长会使索引变得臃肿，导致索引查询变慢。通过目录查询书籍指定的章节之所以快，就是因为索引足够轻量，如果索引太长那么这个优势就不明显了。而且索引里的数据和表里的数据本身就是冗余的，如果索引太长，那么磁盘空间浪费的就越多。MySQL对索引的长度也有明确限制的。

控制索引长度有几个方法：

1. 字符串使用前缀索引，可以大幅缩短索引的长度；
2. 联合索引不要建在太多字段上；

前缀索引

索引太长会导致索引变的臃肿，前缀索引就是来给索引进行减负的。

CREATE TABLE User(
  ID bigint unsigned primary key,
  email varchar(64), 
  ... 
) engine=innodb;
复制代码

有这样一张用户表，使用邮箱作为注册名。假设有这样一批用户，abcdii@163.com, abcdrr@163.com, abcdoo@163.com, abcdss@163.com。业务需求里大概率有通过用户名查找用户信息的场景，因此需要在用户名上添加索引。简单的方式直接建立普通索引key(email)，也可以使用前缀索引key(email(4))。

如果建立普通索引那么索引的长度是10，如果建立前缀索引那么索引的长度的4。假设要查询abcdoo@163.com的数据，对于普通索引首先定位到abcdoo@163.com的行，回表拿到数据，然后沿着索引继续往下找，找到abcdss@163.com已经不满足条件，于是结束查找。只进行了一次回表，因此系统判定只查找了1行。

对于前缀索引则需要查找四次，全部都要回表操作确认是否为要查找的对象，因为索引的长度为4时都能满足条件。考虑如果将前缀索引取5个长度key(email(5))，那么也只需要一次查找就能完成。这说明前缀索引可以保持很好的区分区的条件下，可以减少索引的长度。

那么该如何选择前缀索引的长度呢？

首先通过下面这条语句，计算不同列的数量

SELECT count(distinct email) as C FROM User;
复制代码

然后计算不同索引长度下不同列的数量，当不同列的长度和非前缀索引比较接近时，或者随着索引长度的增加不同列的数量不再大量增加时，差不多就是合理的前缀索引长度了。

SELECT count(distinct left(email, 4) as C4 FROM User;
SELECT count(distinct left(email, 5) as C5 FROM User;
复制代码

前缀索引对覆盖索引的影响 因为前缀索引字符串不是完整的，因此会导致覆盖索引失效，因此在建立前缀索引时要考虑到这点。

字符串前面重复度较高时怎么处理

如果遇到字符串前缀部分重复度比较高，如身份证号码。有两种解决方案，

一种是将该字符串颠倒过来存储，查询的时候也要反转字符串后再查询

SELECT * FROM t WHERE id_card = reverse('input_id_card');
复制代码

二是通过该字符串计算一个HASH值，索引建在HASH值上。但是不同的ID也可能具有相同的hash值，因此查询时需要通过身份证号精确判断。id_card_crc为ID计算crc32后的hash值字段。hash计算后索引就只占用4个字节了。

SELECT * FROM t WHERE id_card_crc = crc32('input_id_card') and id_card='input_id_card'
复制代码

这两种方法都会导致范围查询失败，这点是需要注意的。