2018-06-09

MySQL索引初探

什么是索引？

索引的出现其实就是为了提高数据查询的效率，就像书的目录一样。

索引本身也占据磁盘空间，更新和删除数据的时候也要对索引进行维护。

索引的类型

哈希

KV结构，只适用于等值查询，仅MEMORY引擎支持。

二叉查找树

从图中可以看到，我们为user表（用户信息表）建立了一个二叉查找树的索引。图中的圆为二叉查找树的节点，节点中存储了键(key)和数据(data)。

键对应user表中的id，数据对应user表中的行数据。二叉查找树的特点就是左子节点的键值小于父节点的键值，右子节点的键值大于父节点的键值。顶端的节点我们称为根节点，没有子节点的节点我们称之为叶节点。

平衡二叉查找树

二叉查找树有可能很不平衡，最坏的情况是退化成一个链表，导致查找效率低下：

为了解决这个问题，我们需要保证二叉查找树一直保持平衡，就需要用到平衡二叉树了。

平衡二叉树又称AVL树，在满足二叉查找树特性的基础上，要求每个节点的左右子树的高度差不能超过1。

B树

索引不光维护在内存中，还要持久化到磁盘里，在数据量比较大的情况下，平衡二叉树的高度会很高，而我们每查找一次数据就需要从磁盘中读取一个节点，也就是我们说的一个磁盘块，我们都知道平衡二叉树可是每个节点只存储一个键值和数据的，这种情况会进行很多次磁盘 IO，我们查找数据的效率将会极低！所以我们要想办法在一个磁盘块里尽量多放一些节点数据进去，那么二叉树就要改造成N叉树也就是树了。

从上图可以看出，B树相对于平衡二叉树，每个节点存储了更多的键值(key)和数据(data)，并且每个节点拥有更多的子节点，子节点的个数一般称为阶，上述图中的B树为3阶B树，高度也会很低。

以 InnoDB 的一个整数字段索引为例，这个 N 差不多是 1200。这棵树高是 4 的时候，就可以存 1200 的 3 次方个值，这已经 17 亿了。考虑到树根的数据块总是在内存中的，一个 10 亿行的表上一个整数字段的索引，查找一个值最多只需要访问 3 次磁盘。其实，树的第二层也有很大概率在内存中，那么访问磁盘的平均次数就更少了。

B+树

B+树是对B树的进一步优化。让我们先来看下B+树的结构图：

B+树非叶子节点上是不存储行数据的，仅存储key，而B树节点中不仅存储key，也会存储行数据。之所以这么做是因为在数据库中页的大小是固定的，innodb中页的默认大小是16KB。如果不存储数据，那么就会存储更多的键值，相应的树的阶数（节点的子节点树）就会更大，树就会更矮更胖，如此一来我们查找数据进行磁盘的IO次数有会再次减少，数据查询的效率也会更快。另外，B+树的阶数是等于键值的数量的，如果我们的B+树一个节点可以存储1000个键值，那么3层B+树可以存储1000×1000×1000=10亿个数据。一般根节点是常驻内存的，所以一般我们查找10亿数据，只需要2次磁盘IO。

InnoDB存储引擎的最小存储单元是页，页可以用于存放数据也可以用于存放键值+指针，在B+树中叶子节点存放数据，非叶子节点存放键值+指针。在MySQL中,InnoDB一页的默认大小是16k。

索引组织表通过非叶子节点的二分查找法以及指针确定数据在哪个页中，进而在去数据页中查找到需要的数据；

那么，通常一棵B+树可以存放多少行数据？

这里我们先假设B+树高为2，即存在一个根节点和若干个叶子节点，那么这棵B+树的存放总记录数为：根节点指针数*单个叶子节点记录行数。

上文我们已经说明单个叶子节点（页）中的记录数=16K/1K=16。（这里假设一行记录的数据大小为1k，实际上现在很多互联网业务数据记录大小通常就是1K左右）。

那么现在我们需要计算出非叶子节点能存放多少指针，其实这也很好算，我们假设主键ID为bigint类型，长度为8字节，而指针大小在InnoDB源码中设置为6字节，这样一共14字节，我们一个页中能存放多少这样的单元，其实就代表有多少指针，即16384/14=1170。那么可以算出一棵高度为2的B+树，能存放1170*16=18720条这样的数据记录。

根据同样的原理我们可以算出一个高度为3的B+树可以存放：1170*1170*16=21902400条这样的记录。所以在InnoDB中B+树高度一般为1-3层，这就能满足千万级的数据存储。在查找数据时，一次页的查找代表一次IO，所以通过主键索引查询通常只需要1-3次IO操作即可查到数据。

在InnoDB的表空间文件中，约定page number为3的代表主键索引的根页，而在根页偏移量为64的地方存放了该B+树的page level。如果page level为1，树高为2，page level为2，则树高为3。即B+树的高度=page level+1；

因为B+树索引的所有数据均存储在叶子节点，而且数据是按照顺序排列的。那么B+树使得范围查找，排序查找，分组查找以及去重查找变得异常简单。而B树因为数据分散在各个节点，要实现这一点是很不容易的。

总结一下B树和B+树的区别：

B树
- 叶子节点，非叶子节点，都存储数据；
- 中序遍历，可以获得所有节点。
B+树
- 数据只存储在叶子节点上，非叶子节点，不存储实际记录，在相同内存的情况下，B+树能够存储更多索引；
- 叶子之间，增加了链表，获取所有节点。对于范围查找，定位min与max之后，中间叶子节点，就是结果集，不用中序回溯。

索引的法则

如果有多个索引，MySQL会优先使用行数最少的索引
最左前缀。例如有索引INDEX(col1, col2, col3)，那么在(col1)，(col1, col2)，(col1, col2, col3)上执行WHERE，GROUP BY，ORDER BY操作的时候可以使用索引。where col1 like 'a%'这种方式也是满足最左前缀原则（最左字段上的左边字符串）的
在进行列比较或者表连接的时候，如果列有相同的数据类型和大小以及字符编码，能更好地使用索引
MIN(),MAX()索引列直接返回例如有索引INDEX(col1, col2)，考虑以下查询：
```
 SELECT MIN(col2), MAX(col2) FROM tbl WHERE col1 = 12;
```
MySQL通过(col1)索引找到节点，然后第一个(col1, col2)里面的col2就是MIN(col2)，最后一个(col1, col2)里面的col2就是MAX(col2)，因为本来就是排好序的，所以不需要在经过计算就能直接返回
索引覆盖例如有索引INDEX(col1, col2, col3)，考虑以下查询：
```
 SELECT col1, col2 FROM tbl WHERE col1 = 12;
```
因为索引INDEX(col1, col2, col3)包含了需要查询的列(col1, col2)，所以MySQL在通过索引找到匹配的时候，不需要再去找对应的行来找到其他列的值
索引下推 MySQL 5.6 引入的索引下推优化可以在索引遍历过程中，对索引中包含的字段先做判断，直接过滤掉不满足条件的记录，减少回表次数。
自增主键自增主键的插入数据模式，每次插入一条新记录，都是追加操作，都不涉及到挪动其他记录，相邻的数据在磁盘上总是相邻的，能充分利用顺序 IO。而由业务逻辑的字段做主键，则往往不容易保证有序插入，会触发页分裂，一分裂，就会有磁盘 IO 把原本的数据挪到别的位置，这样写数据成本相对较高。

一些实例

下载MySQL官网提供的测试数据库

Employees Sample Database

ALTER TABLE employees ADD INDEX ln_fn_bd (last_name, first_name, birth_date);

参考资料

← → Top