简单的聊聊索引的那些事儿

工作经历中，随着业务数据长时间积累，Mysql的数据也稍微有一定的量，于是乎当时我们进行一次服务端慢查询大排查，确定慢查询属于哪个工程并且将其优化掉。我工程内也有一个，大体是MQ订阅到的taskid，taskid关联task的log表去找最近的一条记录的时间，然后根据时间校验是否放行做相应业务处理。我explain下，发现当时写的时候，log表的taskid也没有建索引，当log表的记录积累起来后，这个查询会显得很慢，建索引后有立竿见影的效果，当然这只是一个非常简单的场景。其实这里还衍生出一个问题：当log表数据量过大时候修改表结构，会造成一段时间的锁表。虽然有些方式可以避免锁表，但是“合理时机”创建索引还是很重要的。知其然，要知其所以然，来看看索引的那些事儿。

目录：

• 相关知识准备
• 聊聊BTree和B+Tree
• MyISAM和InnoDB的索引实现
• InnoDB的主键选择和优化
• 通过原理理解最左前缀

相关知识准备

磁盘存储：

Mysql数据一般以文件的形式存储在磁盘上，读取数据时需要在磁盘上进行IO操作。当需要从磁盘读取数据时，系统会将数据逻辑地址传给磁盘，磁盘的控制电路按照寻址逻辑将逻辑地址翻译成物理地址，即确定要读的数据在哪个磁道，哪个扇区。为了读取这个扇区的数据，需要将磁头放到这个扇区上方，为了实现这一点，磁头需要移动对准相应磁道，这个过程叫做寻道，所耗费时间叫做寻道时间，然后磁盘旋转将目标扇区旋转到磁头下，这个过程耗费的时间叫做旋转时间。

计算机局部性原理：

当一个数据被用到时，其附近的数据也通常会马上被使用。

磁盘预读：

由于磁盘顺序读取的效率很高（不需要寻道时间，只需很少的旋转时间），因此对于具有局部性的程序来说，预读可以提高I/O效率。预读的长度一般为页（page）的整倍数。页是计算机管理存储器的逻辑块，硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块，每个存储块称为一页（在许多操作系统中，页得大小通常为4k），主存和磁盘以页为单位交换数据。当程序要读取的数据不在主存中时，会触发一个缺页异常，此时系统会向磁盘发出读盘信号，磁盘会找到数据的起始位置并向后连续读取一页或几页载入内存中，然后异常返回，程序继续运行。

索引的目的：

上边内容可以看出磁盘IO非常耗时，所以索引归根结的目的：减少耗时磁盘IO次数，提高获取数据的性能。

聊聊BTree和B+Tree

BTree有如下特点:

1. 所有键值分布在整颗树中；
2. 任何一个关键字出现且只出现在一个结点中；
3. 搜索有可能在非叶子结点结束；
4. 在关键字全集内做一次查找,性能接近二分查找；

B+Tree是BTree的变体，也是一种多路搜索树, 它与BTree的不同之处在于:

1. 所有关键字存储在叶子节点,非叶子节点并不存储真正的data；
2. 为所有叶子结点增加了一个链指针；

MyISAM和InnoDB的索引实现

MyISAM主键索引策略：

MyISAM表的主键索引（Primary key）如图所示。可以看出MyISAM的索引文件仅仅保存数据记录的地址。MyISAM的辅助索引和主键索引在策略上没任何区别，只是主键索引多了唯一约束。（辅助索引为唯一索引也有此特性）

InnoDB主键索引策略：

可以看到叶节点包含了完整的数据记录。这种索引叫做聚集索引。因为InnoDB的数据文件本身要按主键聚集，所以InnoDB要求表必须有主键（MyISAM可以没有），如果没有显式指定，则 MySQL 系统会自动选择一个可以唯一标识数据记录的列作为主键，如果不存在这种列，则MySQL自动为InnoDB表生成一个隐含字段作为主键，这个字段长度为6个字节，类型为长整形。

InnoDB辅助索引策略：

InnoDB辅助索引策略与MyISAM的不同是InnoDB的辅助索引data域存储相应记录主键的值而不是地址。换句话说，InnoDB的所有辅助索引都引用主键作为data域。查询数据时，首先检索辅助索引获得主键，然后用主键到主索引中检索获得记录。辅助索引强依赖于主键索引，所以合理的创建主键是非常重要的。

InnoDB的主键选择和优化

在使用InnoDB存储引擎时，如果没有特别的需要，请永远使用一个与业务无关的自增字段作为主键。从数据库索引优化角度看，使用InnoDB引擎而不使用自增主键绝对是一个糟糕的主意。上文讨论过InnoDB的索引实现，InnoDB使用聚集索引，数据记录本身被存于主索引（一颗B+Tree）的叶子节点上。这就要求同一个叶子节点内（大小为一个内存页或磁盘页）的各条数据记录按主键顺序存放，因此每当有一条新的记录插入时，MySQL会根据其主键将其插入适当的节点和位置，如果页面达到装载因子（InnoDB默认为15/16），则开辟一个新的页（节点）。如果表使用自增主键，那么每次插入新的记录，记录就会顺序添加到当前索引节点的后续位置，当一页写满，就会自动开辟一个新的页。如下图所示：

这样就会形成一个紧凑的索引结构，近似顺序填满。因为每次插入时也不需要移动已有数据，所以效率很高，也不会增加很多开销在维护索引上。如果使用非自增主键（如果身份证号或学号等），因为每次插入主键的值近似于随机，所以每次新纪录都要被插到现有索引页得中间某个位置, 此时MySQL不得不为了将新记录插到合适位置而移动数据，甚至目标页面可能已经被回写到磁盘上而从缓存中清掉，此时又要从磁盘上读回来，这增加了很多开销。只要可以，请尽量在InnoDB上采用自增字段做主键。

通过原理理解最左前缀

假设当前联合索引为：KEY a_id_state_index ( a_id , name ) 查询验证：

EXPLAIN SELECT * FROM `user` WHERE `a_id` = 5 AND `name` = 'cj_25'
EXPLAIN SELECT * FROM `user` WHERE `name` = 'cj_25' AND `a_id` = 5
复制代码

注：上面两句结果都如下图，因为mysql会对where里面的条件顺序在查询之前会被mysql自动优化

EXPLAIN SELECT * FROM `user` WHERE `a_id` = 5
复制代码

EXPLAIN SELECT * FROM `user` WHERE `name` = 'cj_25'
复制代码

为了分析还是根据数据，按照上面规则去画这颗B+树：

对于辅助索引，树的构建是按照“最左”字段的顺序构建的，当查询name时，只能顺序查找，无法使用二分。