## 什么是索引 索引是一种数据结构。 根据结构分类 * B+Tree * Hash  * 结构说明 每个磁盘块表示一个节点，顶部的磁盘块1分为数据域和指针域，17，35表示数据，P1，P2，P3表示指针，P1指向磁盘块2，P2指向磁盘块3，P3指向磁盘块4。 根据节点分类有叶子节点，根结点，中间节点。从数据组成来看，叶子节点只有数据域，非叶子节点包含数据域，指针域。 * 查找过程（查找30） 1. 加载磁盘块1到内存，发生一次磁盘I/O，使用二分法确定数据在P2指针的指向位置 2. 通过P2指针加载磁盘块3到内存，重复步骤1返回P2指针。 3. 通过P2指针加载磁盘块8，获取数据。 ## Explain 分析sql性能，以多个字段呈现。  1. id 表示执行优先级，id值降序执行 2. select_type 查询类型 * SIMPLE: 简单查询，不包含union或者自查询 * PRIMARY: 包含子查询的SQL语句的最外层查询 * SUBQUERY：第一个子查询 * UNION：UNION查询的非第一个查询 * DEPENDENT UNION：UNION查询的非第一个查询，且用到了外面查询的字段 * UNION RESULT：UNION的结果 * DEPENDENT SUBQUERY: 子查询依赖外层查询的结果 * DERIVED：衍生，查询结果被作为外查询的数据源 3. table 表名or 衍生表  id为1的table“<derived2>“表示由id为2的表衍生而来 4. type 使用索引的方式，性能关系如下: ALL < index < range < ref < eq_ref < const * const：通过主键或者唯一索引等值查询，至多返回一条数据 * eq_ref：在多表查询时，前表索引列的每一个查询结果，后表至多匹配到一行结果 * ref：与eq_ref类似，但是可能匹配多行 * range：对索引列的范围查询 * index：全索引扫描 * ALL：全表扫描 5. possible_keys 可能用到的索引 6. key 查询中实际使用的索引 7. key_len 查询优化器使用了索引的字节数 8. rows 查询结果集需要扫描的数据行数（非索引行数） 9. extra * using filesort：涉及到在内存或者磁盘中进行文件排序 * using index：查询结果用到了覆盖索引 * using temporary：用到了临时表 * using where： # 索引的算法和结构基础 ## B-Tree和B+Tree 先从B-Tree和B+Tree的数据结构谈起 ## B-Tree  ### 结构特点 * d为大于1的整数，称为B-Tree的度，表示B-Tree的宽度 * h为正整数，称为B-Tree的高度 * 每个节点由n个指针和n-1个key组成，其中d<n<2d * key和指针相互间隔，节点的两边是指针 ### 增删查改 由于B-Tree结构的特性，检索数据变得很简单：首先在根结点根据二分法查找key，找到时返回key对应的data，否则根据指针指向的节点递归查找，直到找到key对应的data，或者null指针。 在节点中插入删除key时需要维护树结构 ## B+Tree  B+Tree是B-Tree的变种，相比B-Tree，B+Tree有以下不同： * 非叶子节点中不保存data，叶子节点不保存指针 * key数量和指针数量一致 * B+Tree应用到文件系统中之后新增了方便叶子节点顺序访问的指针 小结：以上对B-Tree和B+Tree做了简单介绍，下一节结合存储器的存取原理验证为什么使用B+Tree结构 ## 为什么使用B+Tree 红黑树结构，B-Tree，B+Tree等结构都可以用来实现索引。 索引文件一般保存在磁盘中，相比内存存取，磁盘I/O消耗的时间大出了几个量级，而索引的性能与磁盘I/O的次数直接相关。 ### 主存存储原理 * 读取 当系统需要从主存读取数据时，通过【地址总线】将地址信号传到主存，解析地址信号之后读取数据并放入【数据总线】。 * 写入 系统分别将地址信号和数据放入地址总线和数据总线，主存读取之后写入主存。 总主存写入读取数据的耗时和操作次数成正比。 ### 磁盘存取原理 检索索引需要磁盘I/O操作，与主存不同，磁盘I/O存在机械运动耗时。 * 读取 磁盘收到数据的逻辑地址之后， 需要花费寻址时间和旋转时间 ### 局部性原理和磁盘预读 磁盘读取速度比内存读取速度要慢得多，为了提高效率需要降低磁盘读取的次数。通过预读来达到这个目的。 &nbsp; 预读指的是即使只需要一个字节，磁盘也会从该位置开始，顺序读取一定长度的数据返回。这样做的理论依据是计算机届的一个理论，局部性原理。 局部性原理：当一个数据被用到时，其附近的数据也通常会马上被使用。 &nbsp; **即对于满足局部性原理的程序，预读可以降低磁盘I/O次数，提交I/O效率。** &nbsp; 预读的长度一般为页（page）的整数倍，页的大小通常为4K。操作系统将内存，磁盘分割为大小相同的存储块，每个存储块称为一页，内存和磁盘以页为单位交换数据。 ### B+Tree的性能分析 根据B+Tree的定位，检索数据需要访问h个节点。数据库设计人员利用磁盘预读原理，将每一个节点的大小设为一个页大小，这样每个节点只需要一次磁盘I/O即可载入。 &nbsp; B+Tree索引检索数据时只需要h-1次的磁盘I/O（根结点常驻内存）。 &nbsp; 相比较而言，红黑树的高度h比B+Tree大得多，检索数据消耗的I/O次数也就大得多，即查询效率就越低。 &nbsp; 相比较B-Tree，B+Tree结构去掉了非叶子节点的数据域data，以便在页单位的节点中保存更多的key，以减少I/O次数。 # MySQL的索引实现 B+Tree结构的索引在不同的存储引擎下有不一样的实现，分别是MyISAM下的非聚簇索引和Innodb下的聚簇索引 ## MyISAM索引实现  叶子节点的数据域data存放的是数据记录的指针地址。 主键索引和辅助索引保持一致 ## InnoDB索引实现 * 主键索引  叶子节点的data域中保存了完整的数据行 &nbsp; * 辅助索引  叶子节点的data域中保存对应数据的主键 # 索引使用策略和优化 ## 参考文献 * [MySQL索引背后的数据结构及算法原理](https://blog.codinglabs.org/articles/theory-of-mysql-index.html)