索引的底层实现
InnoDB存储引擎数据结构使用B+树
B+树
B+数据的基本结构如下图
为什么选用B+树
MySQL为什么要选B+树作为存储结构呢，与B树相比有哪些优点？
1. 减少磁盘访问，提高查询效率
B+树非叶子节点上是不存数据的，仅存键值，而B树节点中不仅存储键值，也会存储数据。因为数据页的大小是固定的（InnoDB中页的默认大小是16KB），如果不存储数据，那么就会存储更多的键值，相应的树的阶数N就会更大，树高就会越低，这样查询数据进行磁盘IO的次数就会大大减少，数据查询的效率也会更快。
以InnoDB的一个整数字段索引为例，阶数N大概是1200，这棵树高是4的时候，就可以存1200^3（约17亿）个值，因为根节点总是在内存中的，一个10亿行的表上一个整数字段的索引，查找一个值最多只需要访问3次磁盘。
2. 提高范围查找效率
因为B+树的所有数据均存储在叶子节点，而且是有序的，使得B+树范围查找，排序查找，分组查找以及去重查找变的简单，而B树的数据分散在各个节点上，实现起来比较困难。
普通索引和唯一索引如何选择？
普通索引不需要保证一条记录的唯一性，查询和更新操作都不需要保证数据页已经读到内存中，相反唯一索引为了保证唯一性，更新时必须要保证数据页在内存中，需要检查是否满足唯一性
查询操作的区别
- 普通索引：查找到满足条件的第一个记录后，需要查找下一条记录，直到碰到不满足的记录
- 唯一索引：查找满足条件的第一个记录就会停止检索
因为是innoDB的读写操作是以数据页为单位的，通常情况目标记录的下一个记录也会在内存中，对于普通索引来说，只是多了一次判断操作，这个CPU成本可以忽略不计，如果是目标记录恰好在某页的最后，下一条记录需要从磁盘中读取，这个I\O成本会大一些，但是这种情况出现的概率很低。
所以对于查询操作来说，唯一索引更快，但是性能差异非常小。
更新操作的区别
change buffer
当更新一个数据页时，如果数据页在内存中就直接更新，如果数据页还没有在内存中，在不影响数据一致性的前提下，InnoDB会将这些更新操作缓存再change buffer中，这样就不用从磁盘中读入数据了，大大提高了更新操作的性能。InnoDB会在下次访问这个数据页的时候将数据页读入内存然后执行change buffer中与这个页有关的操作，保证数据的最终一致性。
change buffer是可持久化的数据，也会被写到磁盘中，写入change buffer操作也会记录在redo log中。
merge：将change buffer中的操作应用到原数据页的过程称为merge，merge除了在查询操作时会触发，系统后台有线程会定期merge，数据库正常关闭（shut down）时也会执行merge操作。
优点：
- 减少读磁盘，明显提升更新操作的速度
- 数据读入内存会占用buffer pool，可以减少内存使用，提高内存利用率
使用条件：
- 唯一索引的更新操作需要判断唯一性约束，必须将数据读到内存中才能判断，因此唯一索引的更换不能使用
- 只有普通索引可使用
- change buffer使用的是buffer pool中的内存，因此不能过大。
应用场景：
- 写多读少的业务，如账单、日志类的系统
如果业务更新后马上会做查询，那么merge的操作会被触发，这样随机访问磁盘的次数不会减少还增加了change buffer的维护代价，反而起到了反作用。
索引的选择
- 在业务保证唯一性的前提下，尽量选择普通索引。
- 如果更新后面马上伴随这查询，应该关闭change buffer
change buffer和redo log
使用change buffer的更新语句执行的过程：
- 如果数据页在内存中，直接更新内存
- 如果数据页不在内存中，在change buffer中记录更新操作
- 将1或2的动作记录在redo log中
区别
- redo log主要是节省随机写磁盘的IO消耗（转为顺序写）
- change buffer主要节省随机读磁盘的IO消耗
为什么MySQL优化器会选错索引
优化器选择索引的目的是找一个最优的方案，并用最小的代价去执行语句，扫描行数是影响执行速度的代价之一，扫描行数越少，意味着访问磁盘数据越少，消耗的CPU资源也越少（扫描行数并不是唯一判断标准，还会结合是否使用临时表、是否排序等因素进行综合判断）。
在不涉及临时表和排序的情况下，选错索引肯定是在判断扫描行数的时候出错了
扫描行数如何计算的
执行语句前MySQL并不能精确的知道这个条件的记录有多少条，只能根据统计信息来估算扫描记录数。
索引的基数
一个索引上不同的值越多，这个索引的区分度就越好，而一个索引上不同的值的个数称为基数，基数越大说明区分度越好。
基数的计算
MySQL使用采样统计（选择采样而不是全表扫描是为了节省计算成本）：
- InnoDB默认会选择N个数据页，统计这些页面上的不同值得到一个平均值，然后乘以索引的页面数得到基数。
- 数据表持续更新的过程中，当变更的数据行占比超过1/M的时候，会自动触发做一次索引统计
解决方案
- 当发现explain的结果预估的rows值跟实际差距比较大可以使用
analyze table命令解决 - 使用
force index()强行选择某个索引 - 优化SQL语句引导MySQL选择更合适的索引
- 新建一个更合适的索引
字符串前缀索引
给一个字符串字段上加索引有如下两种选择：
- 整个字符串加索引：
alter table user add index idx_email(email); - 前六个字符索引：
alter table user add index idx_email(email(6));
优点
- 前缀索引的索引结构只保存了前n个字符，索引占用的空间会更小
- 使用前缀索引定义合适的长度，即可以节省空间，又不会增加太多查询成本
缺点
- 增加了查询额外扫描次数，需要查找到所有前缀匹配的记录，每条记录都要回表查询完整数据进行判断。
- 使用前缀索引会破坏覆盖索引（查询字段上都建了索引，不需要回表）对查询性能的优化
其他方式
- 倒序存储加前缀索引：当字符串的前n为重复度高的情况
- hash字段：添加一个hash字段，保存字符串字段的校验码（如crc32）
这两种方法都不支持范围查找，都会产生额外的cpu计算消耗，hash字段的查询性能更稳定，crc32计算的值冲突概率非常小。
独立索引
必须是独立的索引字段才能用到索引，在索引上使用函数、表达式都会导致不能使用索引树搜索，从而导致慢查询。
CASE1：在索引上使用函数
建表语句如下：
CREATE TABLE `tradelog` (
`id` int(11) NOT NULL,
`tradeid` varchar(32) DEFAULT NULL,
`operator` int(11) DEFAULT NULL,
`t_modified` datetime DEFAULT NULL,
PRIMARY KEY (`id`),
KEY `tradeid` (`tradeid`),
KEY `t_modified` (`t_modified`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4;
如果要查询几年内某个月的交易总数，查询语句可能如下：
select count(*) from tradelog where month(t_modified)=7;
索引上使用函数可能会导致其失去有序性，从而不能使用树搜索（不代表使用索引，可以在索引上遍历），即使没有改变索引的有序性优化器还是不能用索引快速查找，所以要避免这种写法。
CASE2：隐式类型转换
假如有如下语句：
select * from tradelog where tradeid=110717;
tradeid字段是varchar类型，如果要和数字作比较会将其转换为数字类型，对于优化器来说上述语句相当于:
select * from tradelog where CAST(tradid AS signed int) = 110717;
可以看到隐式的在索引字段上使用了函数，从而导致不能使用树搜索。
CASE3：隐式编码转换
如果在做连表查询是，驱动表和被驱动表的字段编码类型不一致，会导致索引不能使用树搜索。
参考资料
【极客时间】MySQL实战45讲：09、10、11节
