MySQL数据库索引的底层实现原理和优化策略

原文链接：https://www.leahy.club/archives/mysqlindex

MySQL的索引主要有BTree索引、Hash索引、全文索引。

重点讨论BTree（后面涉及到的BTree都是指B+Tree）索引的实现原理。

MySQL的官方定义：索引（index）是帮助MySQL高效获取数据的数据结构，也就是说索引本质上是数据结构。而我们最常用的是使用BTree数据结构作为索引的底层实现。

因为数据库最核心的功能在于数据查找，因此需要高效的查找算法和相应的数据结构。一般我们查找使用的是二叉查找树，或者其升级版红黑树。但是在MySQL中使用的是BTree。

首先简要回顾一下BTree的结构。

定义：阶为M的BTree有如下特性：

数据项存储在树叶上

非叶子节点和根节点都是由分支（分支指向儿子）和关键字（索引信息）组成，分支个数为M，关键字个数为M-1

非叶子节点的儿子数量在M/2到M之间，根节点在2到M之间

树叶都在相同的深度上，且有L/2到L个数据项，L另外设定。

如上图所示，为一个M为5的BTree。每个非树叶节点由四个关键字和五个分支组成。其查找的时间复杂度是 $l o g_{M}^{N}$ ,其中N是节点个数。

L的数量一般由分页的大小决定，比如一个分页是4KB，一个数据项大小为32B, 因此可以计算得到L为16。其实M的合适大小也可以计算出来，比如一个分支大小为4B，一个关键字大小为32B，那么由 $4 * M + 32 （ M - 1 ） = 4096$ ，那么M约等于114。

那么为什么选择BTree作为索引的底层实现而不是红黑树？

主要有两点：

因为对于一个数据库来说，其数据量很大，从而导致其索引也很大。从而需要将索引存储在磁盘中，由于磁盘的IO操作是极其耗时的，因此高效索引的关键在于减小磁盘IO次数。举个例子，对于31个节点而言，一个5阶BTree的高度是3，一个红黑树的最小高度是5。而树的高度基本决定了磁盘的IO次数，所以使用BTree性能要提升很多。
BTree有个特点是相邻的数据，在物理上也是相邻的，因为BTree的node的大小设为一个页，而一个节点上存有多个相邻的关键字和分支信息，每个节点只需要一次IO就能完全载入，相当于一次IO载入了多个相邻的关键字和分支，所以说在BTree中相邻的数据在物理上也是相邻的。而红黑树不具有这个特性，其大小相邻的数据，在物理结构上可能距离相差很大。由于程序的局部性原理，如果我们在索引中采用了预加载的技术，每次磁盘访问的时候除了将访问到的页加载到磁盘，我们还可以基于局部性原理加载几页相邻的数据到内存中，而这个加载是不需要消耗多余磁盘IO时间的。因此，由于局部性原理，以及BTree存储结构物理上的特性，所以BTree的索引性能比红黑树要好很多。

MyIsAM VS InnoDB的索引

MyIsAM索引的实现使用BTree作为索引结构，叶节点的数据项存储的是数据记录的地址。

InnoDB索引的实现使用的也是BTree，不同的是叶节点的数据项直接记录了完整的数据而不是数据的地址，这种方式叫做聚集索引。MyIsAM中的就称为非聚集索引，主要是为了与InnoDB的聚集索引相对应。

同时，InnoDB的辅助索引的数据项记录的是主键的值而不是地址。而在MyIsAM中辅助索引是独立的，其存储的还是索引对应的地址。

由此我们可以知道，为什么在InnoDB中不建议使用过长的字段作为主键了，因为所有的辅助索引都引用了主键，主键过长会导致辅助索引过大，同时在BTree中分裂调整是一个很耗时的操作，会涉及到多次IO操作（但依旧比红黑树耗时低），所以使用自增属性作为主键是一个很好的选择。

索引的优化策略

MySQL的优化主要分为结构优化和查询优化。对于索引的结构化优化，一旦了解了索引底层原理，那么选择高性能的策略成为了一种必然。

满足最左前缀原则，需要根据情况，建立对应的联合索引
选择选择性高的索引值，即重复度低的索引值
永远使用一个与业务无关的自增字段作为主键

PS：最左前缀原则：在MySQL建立联合索引时会遵循最左优先的原则，在检索数据时从联合索引的最左边开始匹配。
https://blog.codinglabs.org/articles/theory-of-mysql-index.html

为什么要使用联合索引？

减少开销。建一个联合索引(col1,col2,col3)，实际相当于建了(col1),(col1,col2),(col1,col2,col3)三个索引。每多一个索引，都会增加写操作的开销和磁盘空间的开销。对于大量数据的表，使用联合索引会大大的减少开销！
覆盖索引。对联合索引(col1,col2,col3)，如果有如下的sql: select col1,col2,col3 from test where col1=1 and col2=2。那么MySQL可以直接通过遍历索引取得数据，而无需回表，这减少了很多的随机io操作。减少io操作，特别的随机io其实是dba主要的优化策略。所以，在真正的实际应用中，覆盖索引是主要的提升性能的优化手段之一。
效率高。索引列越多，通过索引筛选出的数据越少。有1000W条数据的表，有如下sql:select from table where col1=1 and col2=2 and col3=3,假设假设每个条件可以筛选出10%的数据，如果只有单值索引，那么通过该索引能筛选出1000W10%=100w条数据，然后再回表从100w条数据中找到符合col2=2 and col3= 3的数据，然后再排序，再分页；如果是联合索引，通过索引筛选出1000w10% 10% *10%=1w，效率提升可想而知！