面试时的排序算法，普通索引和唯一索引
面试时的排序算法，普通索引和唯一索引为了说明普通索引和唯一索引对更新语句性能的影响这个问题，需要先了解下change buffer。那么，这个不同带来的性能差距会有多少呢？答案是，微乎其微。若从性能的角度考虑，你选择唯一索引还是普通索引呢？选择的依据是什么呢？我们用之前 面试官：索引原理都不知道，你怎么设计表？ 中分析过的例子来一起了解下这两种索引在查询和更新中的性能影响。假设，执行查询的语句是 select id from T where k=5。这个查询语句在索引树上查找的过程，先是通过 B 树从树根开始，按层搜索到叶子节点，也就是图中右下角的这个数据页，然后可以认为数据页内部通过二分法来定位记录。
前言在前面的文章中，我们一起学习了索引的相关基础知识，也对普通索引和唯一索引的区别有了一定的了解。今天，我们一起来学习下，在不同的业务场景，普通索引和唯一索引应该怎么选择。
假设你在维护一个市民系统，每个人都有一个唯一的身份证号，而且业务代码已经保证了不会写入两个重复的身份证号。如果市民系统需要按照身份证号查姓名，就会执行类似这样的 SQL 语句：
select name from CUser where id_card = 'xxxxxxxyyyyyyzzzzz';
那么，你是不是会考虑在id_card字段上加索引呢？
由于身份证号字段比较大，并不建议把身份证号当做主键，那么现在有两个选择，要么给 id_card 字段创建唯一索引，要么创建一个普通索引。如果业务代码已经保证了不会写入重复的身份证号，那么这两个选择逻辑上都是正确的。
若从性能的角度考虑，你选择唯一索引还是普通索引呢？选择的依据是什么呢？
我们用之前 面试官：索引原理都不知道，你怎么设计表？ 中分析过的例子来一起了解下这两种索引在查询和更新中的性能影响。
假设，执行查询的语句是 select id from T where k=5。这个查询语句在索引树上查找的过程，先是通过 B 树从树根开始，按层搜索到叶子节点，也就是图中右下角的这个数据页，然后可以认为数据页内部通过二分法来定位记录。
- 对于普通索引来说，查找到满足条件的第一个记录 (5 500) 后，需要查找下一个记录，直到碰到第一个不满足 k=5 条件的记录。
- 对于唯一索引来说，由于索引定义了唯一性，查找到第一个满足条件的记录后，就会停止继续检索。
那么，这个不同带来的性能差距会有多少呢？答案是，微乎其微。
更新过程为了说明普通索引和唯一索引对更新语句性能的影响这个问题，需要先了解下change buffer。
当需要更新一个数据页时，如果数据页在内存中就直接更新，而如果这个数据页还没有在内存中的话，在不影响数据一致性的前提下，InnoDB 会将这些更新操作缓存在 change buffer 中，这样就不需要从磁盘中读入这个数据页了。在下次查询需要访问这个数据页的时候，将数据页读入内存，然后执行 change buffer 中与这个页有关的操作。通过这种方式就能保证这个数据逻辑的正确性。
需要说明的是，虽然名字叫作 change buffer，实际上它是可以持久化的数据。也就是说，change buffer 在内存中有拷贝，也会被写入到磁盘上。
将 change buffer 中的操作应用到原数据页，得到最新结果的过程称为 merge。除了访问这个数据页会触发 merge 外，系统有后台线程会定期 merge。在数据库正常关闭（shutdown）的过程中，也会执行 merge 操作。
显然，如果能够将更新操作先记录在 change buffer，减少读磁盘，语句的执行速度会得到明显提升，还能够避免占用内存，提高内存利用率。
了解了change buffer，那么如果要在这张表中插入一个新记录 (4 400) 的话，InnoDB 的处理流程是怎样的。
第一种情况是，这个记录要更新的目标页在内存中：
- 对于唯一索引来说，找到 3 和 5 之间的位置，判断到没有冲突，插入这个值，语句执行结束；
- 对于普通索引来说，找到 3 和 5 之间的位置，插入这个值，语句执行结束。
第二种情况是，这个记录要更新的目标页不在内存中：
- 对于唯一索引来说，需要将数据页读入内存，判断到没有冲突，插入这个值，语句执行结束；
- 对于普通索引来说，则是将更新记录在 change buffer，语句执行就结束了。
因为 merge 的时候是真正进行数据更新的时刻，而 change buffer 的主要目的就是将记录的变更动作缓存下来，所以在一个数据页做 merge 之前，change buffer 记录的变更越多（也就是这个页面上要更新的次数越多），收益就越大。
因此，对于写多读少的业务来说，页面在写完以后马上被访问到的概率比较小，此时 change buffer 的使用效果最好。这种业务模型常见的就是账单类、日志类的系统。
索引的选择普通索引和唯一索引，这两类索引在查询能力上是没差别的，主要考虑的是对更新性能的影响。所以，我建议你尽量选择普通索引。
在实际使用中，你会发现，普通索引和 change buffer 的配合使用，对于数据量大的表的更新优化还是很明显的。
change buffer 和 redo log刚刚提到change buffer缓存处理记录，大家一定会想到之前我们学习过的redo log 那么两者有什么区别呢？
假如现在我们要在表中插入语句：
mysql> insert into t(id k) values(id1 k1) (id2 k2);
这里，我们假设当前 k 索引树的状态，查找到位置后，k1 所在的数据页在内存 (InnoDB buffer pool) 中，k2 所在的数据页不在内存中。如图 是带 change buffer 的更新状态图。
change buffer更新状态图
这条语句的操作过程如下：
- Page 1 在内存中，直接更新内存；
- Page 2 没有在内存中，就在内存的 change buffer 区域，记录下“我要往 Page 2 插入一行”这个信息
- 将上述两个动作记入 redo log 中。
做完上面这些，事务就可以完成了。所以，你会看到，执行这条更新语句的成本很低，就是写了两处内存，然后写了一处磁盘（两次操作合在一起写了一次磁盘），而且还是顺序写的。
如果读语句发生在更新语句后不久，内存中的数据都还在，那么此时的这两个读操作就与系统表空间（ibdata1）和 redo log（ib_log_fileX）无关了。
带change buffer的读过程
- 读 Page 1 的时候，直接从内存返回。有几位同学在前面文章的评论中问到，WAL 之后如果读数据，是不是一定要读盘，是不是一定要从 redo log 里面把数据更新以后才可以返回？其实是不用的。你可以看一下图 3 的这个状态，虽然磁盘上还是之前的数据，但是这里直接从内存返回结果，结果是正确的。
- 要读 Page 2 的时候，需要把 Page 2 从磁盘读入内存中，然后应用 change buffer 里面的操作日志，生成一个正确的版本并返回结果。
所以，如果要简单地对比这两个机制在提升更新性能上的收益的话，redo log 主要节省的是随机写磁盘的 IO 消耗（转成顺序写），而 change buffer 主要节省的则是随机读磁盘的 IO 消耗。
总结今天，一起学习了普通索引和唯一索，了解了数据的查询和更新过程、hange buffer 的机制以及应用场景。
由于唯一索引用不上 change buffer 的优化机制，因此如果业务可以接受，从性能角度出发建议优先考虑非唯一索引。
