春暖花开，是时候学一波MySQL了

为什么要了解索引?

索引，对于每个开发人员来说，熟悉而陌生。熟悉是在获取数据时，不管是操作关系还是非关系数据库，多多少少都会用到它。陌生的是，很多人仅停留在使用层面，而没有对它进行深层次的掌握，以至于造成对索引的滥用或错用。本文以MySQL为例，决定从数据结构的角度阐述索引的底层结构，不同引擎下的实现原理以及常见的索引优化原则。

主存及磁盘读取原理

【为什么要了解存取原理】

一般来说，索引本身也很大，由于内存容量的限制，不可能全部存储在内存中，因此索引往往以文件的形式存储的磁盘上，所以索引查找过程中就要产生磁盘I/O消耗，相对于内存存取，I/O存取的消耗要高几个数量级，所以评估一个索引的合理性及效率的标准是：查找过程中磁盘I/O的存取次数。

【主存存取原理】

目前计算机使用的主存基本都是随机读写存储器（RAM），现代RAM的结构和存取原理比较复杂，此处抽象出一个二维模型来说明RAM的工作原理。

①   结构：主存是一系列的存储单元组成的矩阵，每个存储单元存储固定大小的数据。每个存储单元有唯一的地址，通过一个行地址和一个列地址可以唯一定位到一个存储单元。

②   读取：则将地址信号放到地址总线上传给主存，主存读到地址信号后，解析信号并定位到指定存储单元，然后将此存储单元数据放到数据总线上，供其它部件读取。

③   写入：系统将要写入单元地址和数据分别放在地址总线和数据总线上，主存读取两个总线的内容，做相应的写操作。

④   结论：因为不存在机械操作，主存存取的时间仅与存取次数呈线性关系，两次存取的数据的“距离”不会对时间有任何影响，先取B0再取B1和先取B0再取C2的时间消耗是一样的。

【磁盘存取原理】

一个磁盘由大小相同且同轴的圆形盘片组成，磁盘可以转动（各个磁盘必须同步转动）。在磁盘的一侧有存储装置，它固定了一组磁头，磁盘的整体结构示意图如下：

上图的各个专业术语解释如下：

①   读写头：磁头

②   磁道：盘片被划分成一系列同心环，圆心是盘片中心，每个同心环叫做一个磁道。

③   柱面：所有半径相同的磁道组成一个柱面

④   扇区：磁道被沿半径线划分成一个个小的段，每个段叫做一个扇区，每个扇区是磁盘的最小存储单元，有的地方页称作块

⑤   磁盘上数据必须用一个三维地址唯一标示：柱面号、盘面号、块号(磁道上的盘块)。

读/写磁盘上某一指定数据需要下面3个步骤：

①   首先移动臂根据柱面号使磁头移动到所需要的柱面上，这一过程被称为定位或查找（这部分时间称之为寻道时间，代价最高，最大可达到0.1s左右）。

②   所有磁头都定位到了10个盘面的10条磁道上(磁头都是双向的)。

③   这时根据盘面号来确定指定盘面上的磁道。盘面确定以后，盘片开始旋转，将指定块号的磁道段移动至磁头下，旋转一般耗时较少。

核心数据结构

【二叉搜索树】

定义：

①   所有非叶子结点至多拥有两个儿子（ Left 和 Right ）

②   所有结点存储一个关键字

③   非叶子结点的左指针指向小于其关键字的子树

④   右指针指向大于其关键字的子树

示例：

特点：

①   B 树的搜索：若根结点的关键字值等于查找的关键字，成功。否则，若小于根结点的关键字值，递归查左子树。若大于根结点的关键字值，递归查右子树。若子树为空，查找不成功

②   相比连续内存空间的二分查找（数组实现）的优点是，改变 B 树结构不需要移动大段的内存数据

③   B树在经过多次插入与删除后，有可能导致不同的结构，上图的右边部分

④   实际使用的 B 树都是在原 B 树的基础上加上平衡算法，即“平衡二叉树”,如红黑树（感兴趣的可阅读JDK1.8集合类的部分源码）

⑤   如何保持 B 树结点分布均匀的平衡算法是平衡二叉树的关键

【B- 树】

定义：

①   定义任意非叶子结点最多只有M个儿子；且M>2；

②   根结点的儿子数为[2, M]；

③   除根结点以外的非叶子结点的儿子数为[M/2, M]；

④   每个结点存放至少M/2-1（取上整）和至多M-1个关键字；（至少2个关键字）

⑤   非叶子结点的关键字个数=指向儿子的指针个数-1；

⑥   非叶子结点的关键字：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]；

⑦   非叶子结点的指针：P[1], P[2], …, P[M]；其中P[1]指向关键字小于K[1]的子树，P[M]指向关键字大于K[M-1]的子树，其它P[i]指向关键字属于(K[i-1], K[i])的子树；

⑧   所有叶子结点位于同一层；

示例：

特点：

①   关键字集合分布在整颗树中

②   任何一个关键字出现且只出现在一个结点中

③   搜索有可能在非叶子结点结束

④   其性能等价于在关键字全集内做一次二分查找

⑤   自动层次控制

⑥   在插入结点时，如果结点已满，需要将结点分裂；删除结点时，需将兄弟结点合并

【B+树】

定义：

B+树是B-树的变体，定义基本相同，除了：

①   内节点不存储data，只存储key；叶子节点不存储指针

示例：

局部性原理与磁盘预读：

当一个数据被用到时，其附近的数据也通常会马上被使用，所以在查找数据时，磁盘会找到数据的起始位置并向后连续读取一页或几页载入内存中，而且磁盘顺序读取的效率很高（不需要寻道时间，只需很少的旋转时间）

特点：

①   新建节点时，直接申请一个页的空间，保证一个节点物理上也存储在一个页里，计算机存储分配都是按页对齐的，实现了一个node只需一次I/O

②   内部结点（相对于外部结点而言）并没有指向关键字具体信息的指针，因此其内部结点相对B树更小（做索引的值范围一般很小，而行记录的具体信息可能很大）

③   盘块所能容纳的关键字数量也越多（数量的算法后续章节会讲），一次性读入内存中的关键字也越多，可以和参与和关键字比较的样本更大，使比较结果更精确，间接降低了IO读写次数，这是被选为做索引数据结构的重要原因

④   很多文件系统都采用它作为索引的数据结构

【带有顺序访问指针的B+Tree】

定义：

①   增加了顺序访问指针

②   一般在数据库系统或文件系统中使用

示例：

特点：

①   适合遍历

②   适合区间访问

③   MySQL索引的实现采用它作为数据结构

不同引擎下的实现方式

【Innodb实现】

【Innodb特点】

①   聚簇索引，辅助索引，采用的同一数据结构，只是存储的内容不一样

②   聚集索引：按每张表的主键构造的一颗B+树，叶节点中存放着整张表的行记录数据

③   辅助索引：页级别不包含行的全部数据，叶节点除了包含键值以外，还包含了一个书签，用来告诉InnoDB哪里可以找到与索引相对应的行数据，就是聚集索引的键，这个查找过程有的地方称之为书签查找

不选用大字段做主键：因为辅助索引中包含主键，所以如果主键很大，会导致辅助索引很大。

【MyIASM索引实现】

【MyIASM索引特点】

①   叶节点的data域存放的是数据记录的地址，索引文件为MYI文件，数据文件为MYD文件

②   主索引和辅助索引（Secondary key）在结构上没有任何区别，只是主索引要求key是唯一的，而辅助索引的key可以重复

索引创建及更新策略

【索引创建策略】

①   cardinality：不重复记录的预估值

②   区分度: cardinality / count(*)，这是一个介于0和1之间的小数,

越接近1区分度越高,越适合做索引

结论：

①   在访问表中很少一部分时使用B+树索引才有意义

②   对于性别字段、地区字段、类型字段，他们可取值范围很小，区分度很低，或称为低选择性

【索引更新策略】

①   更新涉及的操作：insert和update

②   如果每次更新，DB压力大，更新时间长

③   更新时机：1/16的数据已发生了改变 或 stat_modified_counter>2000 000 000

④   统计样本：随机对对8个叶子节点进行采样分析：Cardinality=(P1+P2+...+P8)*A/8

⑤   Cardinality只能是预估值，无法获得精确值

⑥   每次得到的Cardinality值可能不同页可能相同（如果总的叶子节点数量小于4，则每次相同）

索引优化策 略

【推荐自增ID作为主键】

①   不使用自增ID都是业务上的考虑

②   因为InnoDB数据文件本身是一颗B+Tree，非单调的主键会造成在插入新记录时数据文件为了维持B+Tree的特性而频繁的分裂调整，十分低效，而使用自增字段作为主键则是一个很好的选择，因为它影响的始终是后边的节点。

③   备注：虽然旋转也是维护树的平衡的一种方式，但是它的作用是减少拆页，仍无法完全避免拆页

【选择区分度高的字段作为索引】

以下是选择一个区分度低的作为索引，请看：

①   一个辞典中全是以a和b开头的单词

②   按照首字母建立一个目录(索引)

③   那么目录上一共就两条,每条的范围对应差不多半本辞典，每次查到后首字母后还得遍历半本词典才能找到具体单词，那这个目录(索引)效率极低，可以说毫无用处

以下是选择一个区分度高的作为索引，请看：

一个班级的学生信息以学号做索引,那么区分度为1，只要找到学号就能直接找到相对应的学生信息,这个索引就非常有效

【索引字段尽量小】

①   IO次数取决于b+数的高度h

②   假设当前数据表的数据为N，每个磁盘块的数据项的数量是m，则有h=㏒(m+1)N

③   当数据量N一定的情况下，m越大，h越小；

④   m = 磁盘块的大小/数据项的大小，磁盘块的大小也就是一个数据页的大小，是固定的

⑤   如果数据项占的空间越小，数据项的数量越多，树的高度越低。

⑥   这就是为什么每个数据项，即索引字段要尽量的小

⑦   这也是为什么b+树要求把真实的数据放到叶子节点而不是内层节点，一旦放到内层节点，磁盘块的数据项会大幅度下降，导致树增高，增加IO次数

【联合索引最左匹配特性】

①   比如(name,age,sex)的时候，b+数是按照从左到右的顺序来建立搜索树的

②   比如当(张三,20,F)这样的数据来检索的时候，b+树会优先比较name来确定下一步的所搜方向，如果name相同再依次比较age和sex，最后得到检索的数据

③   当(20,F)这样的没有name的数据来的时候，b+树就不知道下一步该查哪个节点，因为建立搜索树的时候name就是第一个比较因子，必须要先根据name来搜索才能知道下一步去哪里查询

④   当(张三,F)这样的数据来检索时，b+树可以用name来指定搜索方向，但下一个字段age的缺失，所以只能把名字等于张三的数据都找到，然后再匹配性别是F的数据了

【联合索引后续键值有序】

①   Create table buy_log (user_id,buy_date)

②   建立索引(user_id,buy_date)

③   select * from buy_log where user_id=1 order by buy_date limit 3

④   在上述联合索引中，buy_date已经排好序了，根据该索引取出数据后，无须再排序，数据库也不会再进行排序操作，从而提高了查询性能

【索引覆盖（Using index）】

①   从辅助索引中查询记录，不走聚集索引，因前者远小于后者（辅助索引不包含具体行记录信息），故可减少IO次数

②   在大多数引擎中，只有当查询语句所访问的列是索引的一部分时（如建立的联合索引为a，b，查询的字段也是a，b），索引才会覆盖

③   如Select count(*) from buy_log（建表语句见上个章节），该表有辅助索引，而且访问的字段刚好被索引覆盖，所以索引被优化器选择

大数据量的删除策略

【索引删除消耗】

①   DML都会产生额外的对索引的操作（如删除时涉及节点的合并），消耗额外的IO

②   删除数据的速度和创建的索引的数量成正比

【删除策略】

①   由于会导致业务暂停，与上下游约定一个执行时间

②   完整备份

③   记录索引的DDL

④   删除索引

⑤   使用删除条件建立临时索引

⑥   删除无用数据

⑦   重建索引

参考文献：

①   《高性能MySQL》

②   《MySQL技术内幕：SQL优化编程》

③   《MySQL技术内容：Innodb存储引擎》

参考资源：

http://blog.codinglabs.org/articles/theory-of-mysql-index.html

https://www.cnblogs.com/youngerchina/p/5624460.html

http://blog.csdn.net/cangchen/article/details/44818485

http://blog.csdn.net/weixin_30531261/article/details/79312676

http://blog.codinglabs.org/articles/theory-of-mysql-index.html