Mysql索引底层原理

常用引擎

InnoDB（聚集索引）

InnoDB的存储文件有两个，后缀名分别是.frm 和.idb，其中.frm是表的定义文件，而.idb是索引和数据文件。
InnoDB 中存在表锁和行锁，不过行锁是在命中索引的情况下才会起作用。
InnoDB 支持事务，且支持四种隔离级别（读未提交、读已提交、可重复读、串行化），默认的为可重复读；而在 Oracle 数据库中，只支持串行化级别和读已提交这两种级别，其中默认的为读已提交级别。

MyISAM（非聚集索引）

Myisam 的存储文件有三个，后缀名分别是.frm、.MYD、MYI，其中.frm是表的定义文件，.MYD是数据文件，.MYI是索引文件。
Myisam只支持表锁，且不支持事务。Myisam 由于有单独的索引文件，在读取数据方面的性能很高。

存储结构

可以用来优化查询的数据结构有哈希表，完全平衡二叉树，B树，B+树。我们使用最多的是B+树，InnoDB和Myisam都是用 B+Tree 来存储数据的。

数据结构可视化网站：

https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

Hash

为什么很少使用hash?

优点：直接计算下标，查询单一数据非常快。
缺点：如果是进行的范围查询的话，哈希索引就必须全表遍历，获得age数据，然后再依次进行比较，也就是相当于没有索引了。这样就不能优化查询效率了。

B树

d 为大于1的一个正整数，称为B-Tree的度，表示节点的数据存储个数；

h 为一个正整数，称为B-Tree的高度；

每个非叶子节点由n-1个key和n个指针组成，其中 d <= n <= 2d；

每个叶子节点最少包含一个key和两个指针，最多包含2d-1个key和2d个指针，叶节点的指针均为null；

所有叶节点具有相同的深度，等于树高h;

key和指针互相间隔，节点两端是指针;

一个节点中的key从左到右非递减排列;

所有节点组成树结构;

每个指针要么为null，要么指向另外一个节点;

关于B-Tree有一系列有趣的性质，例如一个度为 d 的B-Tree，设其索引 N 个key，则其树高h的上限为 logd((N+1)/2) ，检索一个key，其查找节点个数的线性复杂度为 O(logdN) 。从这点可以看出，B-Tree是一个非常有效率的索引数据结构。

B+树

B-Tree有许多变种，其中最常见的是B+Tree。

与B-Tree相比，B+Tree有以下不同点：

每个节点的指针上限为2d而不是2d+1;

非叶子节点不存储data，只存储key，可节省空间，增大度;

叶子节点不存储指针;

带有顺序访问指针，提高了区间访问性能;

局部性原理与磁盘预读

由于存储介质的特性，磁盘本身存取就比主存慢很多，再加上机械运动耗费，磁盘的存取速度往往是主存的几百分分之一，因此为了提高效率，要尽量减少磁盘I/O。

为了达到这个目的，磁盘往往不是严格按需读取，而是每次都会预读，即使只需要一个字节，磁盘也会从这个位置开始，顺序向后读取一定长度的数据放入内存。这样做的理论依据是计算机科学中著名的局部性原理：

当一个数据被用到时，其附近的数据也通常会马上被使用。程序运行期间所需要的数据通常比较集中。

由于磁盘顺序读取的效率很高（不需要寻道时间，只需很少的旋转时间），因此对于具有局部性的程序来说，预读可以提高I/O效率。

预读的长度一般为页（page）的整倍数。页是计算机管理存储器的最小逻辑块，硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块，每个存储块称为一页（在许多操作系统中，页得大小通常为4k），主存和磁盘以页为单位交换数据。当程序要读取的数据不在主存中时，会触发一个缺页异常，此时系统会向磁盘发出读盘信号，磁盘会找到数据的起始位置并向后连续读取一页或几页载入内存中，然后异常返回，程序继续运行。

mysql页文件配置

查看mysql页文件大小

SHOW GLOBAL STATUS like ‘Innodb_page_size’;

为什么Mysql页文件默认16kb就够了呢

假设我们一行数据大小为1K,那么一页就能存16条数据，也就是一个叶子节点能存16条数据;
再看非叶子节点，假设主键ID为bigint类型, 那么长度为8B，指针大小在Innodb源码中为6B，-共就是14B,那么一页里就可以存储16K/14=1170个(主键+指针)，那么：
- 一颗高度为2的B+树能存储的数据为: 1170 * 16 = 18720条
- 一颗高度为3的B+树能存储的数据为: 1170 * 1170 * 16 = 21902400 (千万级条)。

所以在InnoDB中B+树高度一般为1-3层，它就能满足千万级的数据存储。在查找数据时一次页的查找代表一次I/O, 所以通过主键索引查询通常只需要1-3次IO操作即可查找到数据。所以也就回答了我们的问题，1 页=16k这么设置是比较合适的，是适用大多数的企业的，当然这个值是可以修改的，所以也能根据业务的时间情况进行调整。

B-/+Tree索引的性能分析

一般以使用磁盘I/O次数评价索引结构的优劣。

先从B-Tree分析，根据B-Tree的定义，可知检索一次最多需要访问h个节点。数据库系统的设计者巧妙利用了磁盘预读原理，将一个节点的大小设为等于一个页，这样每个节点只需要一次I/O就可以完全载入。

为了达到这个目的，在实际实现B-Tree还需要使用如下技巧：

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

B-Tree中一次检索最多需要h-1次I/O（根节点常驻内存），渐进复杂度为O(h)=O(logdN)。一般实际应用中，度d是非常大的数字，通常超过100，因此h非常小（通常不超过3）。

综上所述，用B-Tree作为索引结构效率是非常高的。B+Tree之所以更适合外存索引，原因和内节点度d有关。从上面分析可以看到，d越大索引的性能越好，而度的上限取决于节点内key和data的大小：

1	dmax = floor(pagesize/(keysize+datasize+pointsize))

floor表示向下取整。由于B+Tree内节点去掉了data域，因此可以拥有更大的度，拥有更好的性能。

MySQL索引实现

在MySQL中，索引属于存储引擎级别的概念，不同存储引擎对索引的实现方式是不同的。

MyISAM索引实现

索引文件仅仅保存数据记录的地址，索引文件和数据文件是分离的；
主索引和辅助索引（Secondary key）在结构上没有任何区别，只是主索引要求key是唯一的，而辅助索引的key可以重复；
索引检索的算法为首先按照B+Tree搜索算法搜索索引，如果指定的Key存在，则取出其data域的值，然后以data域的值为地址，读取相应数据记录。

InnoDB索引实现

虽然InnoDB也使用B+Tree作为索引结构，但具体实现方式却与MyISAM截然不同。

数据文件本身就是索引文件，都存储在后缀为.idb的文件中；
叶节点data域保存了完整的数据记录, 而不是行地址；
因为InnoDB的数据文件本身要按主键聚集，所以InnoDB要求表必须有主键（MyISAM可以没有），如果没有显式指定，则MySQL系统会自动选择一个可以唯一标识数据记录的列作为主键，如果不存在这种列，则MySQL自动为InnoDB表生成一个隐含字段作为主键，这个字段长度为6个字节，类型为长整形；
聚集索引这种实现方式使得按主键的搜索十分高效，但是辅助索引搜索需要检索两遍索引：首先检索辅助索引获得主键，然后用主键到主索引中检索获得记录；

InnodeDB主键选择与插入优化

基于以上特点就很容易理解为什么不建议使用过长的字段作为主键？而且推荐使用整形自增主键？

所有辅助索引都引用主索引，过长的主索引会令辅助索引变得过大；
InnoDB数据文件本身是一颗B+Tree，非单调的主键会造成在插入新记录时数据文件为了维持B+Tree的特性而频繁的分裂调整，十分低效，而使用自增字段作为主键则是一个很好的选择；

联合索引

有如下数据表：

CREATE TABLE People (
    last_name varchar(50) not null,
    first_name varchar(50) not null,
    dob date not null,
    gender enum('m','f') not null,
    key(last_name,first_name,dob)
)

这个建表语句在last_name、first_name、dob列上建立了一个联合索引，下图展示了该索引的存储结构。

可以看到，联合索引中的索引项会先根据第一个索引列进行排序，第一个索引列相同的情况下，会再按照第二个索引列进行排序，依次类推。根据这种存储特点，B-Tree索引对如下类型的查找有效：

全值匹配：查找条件和索引中的所有列相匹配
匹配最左前缀：查找条件只有索引中的第一列
匹配列前缀：只匹配某一列值的开头部分。这里并不一定只能匹配第一个索引列的前缀。例如在确定第一个索引列的值时，也可以在第二个索引列上匹配列前缀。在上面例子中，对于查找姓为Allen，名为J开头的人，也可以应用到索引。
匹配范围值，或者精确匹配某一列并范围匹配另外一列：例如查找姓在Allen和Barrymore之间的人，或者查找姓为Allen，名字在某一个范围内的人。
只访问索引的查询，即要查询的值在索引中都包含，只需要访问索引就行了，无需访问数据行。这种索引被称作覆盖索引。
对于上面列出的查询类型，索引除了可以用来查询外，还可以用来排序。

下面是B-Tree索引的一些限制：

如果不是从索引的最左列开始查找，则无法使用索引。例如直接查找名字为Bill的人，或查找某个生日的人都无法应用到上面的索引，因为都跳过了索引的第一个列。此外查找姓以某个字母结尾的人，也无法使用到上面的索引。
不能在中间跳过索引中的某个列，例如不能查找姓为Smith，生日为某个特定日期的类。这样的查询只能使用到索引的第一列。
如果查询中有某个列的范围查询，则该列右边的所有列都无法使用索引优化查找。例如有查询WHERE last_name=’Smith’ AND first_name LIKE ‘J%’ AND dob=’1976-12-23’，这个查询只能使用到索引的前两列，而不能使用整个索引。

通过上面列出的这些条件，可见对于一个B-TREE联合索引，索引列的顺序非常重要。

InnoDB中有一个功能叫“自适应哈希索引”，当InnoDB注意到某些索引值使用的非常频繁时，会在B-Tree索引之上再建立一层哈希索引，以加速查找效率。这是完全自动的内部行为，用户无法干预。

索引查询

多列索引

当出现对多个索引列做相交(AND)操作的查询时，代表需要一个包含所有相关列的联合索引，而不是多个独立的单列索引。

在MySql官方提供的示例数据库sakila中，表film_actor在字段film_id和actor_id上各有一个单列索引，对于下面这条查询语句，这两个单列索引都不是很好的选择：

1	SELECT film_id,actor_id FROM film_actor WHERE actor_id=1 OR film_id=1;

在老的MySql版本中，这个查询会使用全表扫描。但在MySql5.0之后，查询能够同时使用这两个单列索引进行扫描，然后将结果合并，相当于转换成下面这条查询：

1
2
3

SELECT film_id,actor_id FROM film_actor WHERE actor_id=1 
UNION
SELECT film_id,actor_id FROM film_actor WHERE film_id=1;

在MySql5.7中，执行上面查询的执行计划如下图所示：

从执行计划的type字段可以看到，MySql同时使用了两个索引，并将各自的查询结果合并。并且Extra字段描述了使用索引的详细信息。

虽然MySql在背后对查询进行了优化，使其可以同时利用两个单列索引。但是这需要耗费大量的CPU和内存资源，所以直接将查询改写成UNION的方式会更好。像这种两个列上都有索引的情况，用union代替or会得到更好的效果(注意要求两个列上都建有索引，如果没有索引，用union代替or反而会降低效率)。

如果在EXPLAIN中看到有索引合并，那就应该好好检查一下查询和表的结构，看看是不是已经是最优的。