MySQL - 索引原理

在MySQL数据库中，索引是一种很重要的提升查询性能的存储结构。

索引，就像是书本的目录一样，通过查询索引，可以快速的定位到数据所处位置，减少磁盘I/O次数，提高性能。
在InnoDB存储引擎中，支持的索引包含：B+树、全文索引、哈希索引。

本文将主要聚焦在由B+树实现的索引结构，全文索引基于倒排索引实现，哈希索引基于链表、哈希函数实现。

首先，看一下二分查找，要从一个有序数组中查找一个元素，通过每次的折半再折半，时间复杂度为O(logn)，如果直接顺序查找元素的话，时间复杂度为O(n)。

接着，拓展到二叉查找树，如果二叉查找树足够平衡，那么时间复杂度还可以接近二分查找。

反之，二叉查找树呈现线性状态的话，那么时间复杂度就接近于顺序查找了。

因此，B+树既然能够提升查询性能的话，那必然是一棵平衡查找树，不能出现线性状态。
二叉查找树定义：左边节点值小于根节点值，右边节点值大于根节点值，中序遍历后为从小到大排序的列表。
平衡二叉树定义：在二叉查找树的条件下，又满足左右子树任何节点高度差不超过1。

B+树的所有记录节点都是按照顺序排列，从小到大排列在叶子节点，并且每个叶子节点之间有指针进行连接。

在B+树的叶子节点中，包含了所有的节点及数据，其它非叶子节点仅仅包含指针引用。

在执行范围查找的时候，只需要在B+树上进行二分查找，然后找到底层叶子节点的起始位置，再沿着叶子节点间的双向指针顺序遍历即可，一般B+树的高度在2 ~ 4之间。

除了这个优点之外，由于非叶子节点不存储数据，经过一次磁盘I/O操作，就可以加载大量的节点，然后在内存中高效执行二分查找，再去找到数据所在叶子节点即可。

由B+树来实现的索引包含：聚集索引、非聚集索引。

每张表有且仅有一个聚集索引，通常情况下，是采用主键来作为聚集索引。
聚集索引根据每张表的主键来构造B+树，在叶子节点则存储整张表的行记录数据。
聚集索引是逻辑连续的，因此，在范围查找、根据主键排序的时候，效率特别高。

与聚集索引相反的是非聚集索引，又称为辅助索引，它的叶子节点并不存储行记录数据。
每张表可以拥有多个非聚集索引，通过非聚集索引查找数据会遍历找到叶子节点，再通过叶子节点指向的聚集索引的指针，再去聚集索引上遍历然后查找对应的行记录数据，也因此通过非聚集索引查找数据比通过聚集索引慢了一倍的速度。

基于B+树两类索引实现的应用包含有：联合索引、覆盖索引。

索引既可以使用单独的列，又可以使用多个列组合起来使用，这就是联合索引。
比如有这么一张表，包含有主键id及name、age组成的联合索引及一个addr普通字段。

mysql> desc test;
+-------+--------------+------+-----+---------+-------+
| Field | Type         | Null | Key | Default | Extra |
+-------+--------------+------+-----+---------+-------+
| id    | int(11)      | NO   | PRI | 0       |       |
| name  | varchar(30)  | YES  | MUL | NULL    |       |
| age   | int(11)      | YES  |     | NULL    |       |
| addr  | varchar(200) | YES  |     | NULL    |       |
+-------+--------------+------+-----+---------+-------+

mysql> show index from test;
+-------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| Table | Non_unique | Key_name | Seq_in_index | Column_name | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment | Index_comment |
+-------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| test  |          0 | PRIMARY  |            1 | id          | A         |           0 |     NULL | NULL   |      | BTREE      |         |               |
| test  |          1 | union_x  |            1 | name        | A         |           0 |     NULL | NULL   | YES  | BTREE      |         |               |
| test  |          1 | union_x  |            2 | age         | A         |           0 |     NULL | NULL   | YES  | BTREE      |         |               |
+-------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+

当然，由于采用的B+树实现的，联合索引底层叶子节点的数据也是按多列顺序排列。
对于联合索引，需要符合最左原则，才可以使用到索引。

mysql> explain select * from test where name = 1 and age = 1;
+----+-------------+-------+------+---------------+------+---------+------+--------+-------------+
| id | select_type | table | type | possible_keys | key  | key_len | ref  | rows   | Extra       |
+----+-------------+-------+------+---------------+------+---------+------+--------+-------------+
|  1 | SIMPLE      | test  | ALL  | union_x       | NULL | NULL    | NULL | 997182 | Using where |
+----+-------------+-------+------+---------------+------+---------+------+--------+-------------+

mysql>  explain select * from test where age = 1 and name = 1;
+----+-------------+-------+------+---------------+------+---------+------+--------+-------------+
| id | select_type | table | type | possible_keys | key  | key_len | ref  | rows   | Extra       |
+----+-------------+-------+------+---------------+------+---------+------+--------+-------------+
|  1 | SIMPLE      | test  | ALL  | union_x       | NULL | NULL    | NULL | 997182 | Using where |
+----+-------------+-------+------+---------------+------+---------+------+--------+-------------+

mysql>  explain select * from test where name = 1;
+----+-------------+-------+------+---------------+------+---------+------+--------+-------------+
| id | select_type | table | type | possible_keys | key  | key_len | ref  | rows   | Extra       |
+----+-------------+-------+------+---------------+------+---------+------+--------+-------------+
|  1 | SIMPLE      | test  | ALL  | union_x       | NULL | NULL    | NULL | 997182 | Using where |
+----+-------------+-------+------+---------------+------+---------+------+--------+-------------+

mysql>  explain select * from test where age = 1;
+----+-------------+-------+------+---------------+------+---------+------+--------+-------------+
| id | select_type | table | type | possible_keys | key  | key_len | ref  | rows   | Extra       |
+----+-------------+-------+------+---------------+------+---------+------+--------+-------------+
|  1 | SIMPLE      | test  | ALL  | NULL          | NULL | NULL    | NULL | 997182 | Using where |
+----+-------------+-------+------+---------------+------+---------+------+--------+-------------+

通过以上四个例子可以看到，联合索引如果按照其中一个列去查询的话，那就必须按照最左原则。
现在有联合索引<name,age>，通过name去查询可以用到索引，而通过age就无法使用索引。
如果同时使用name和age的话，在查询的where条件后面可以调整name和age的顺序且不影响索引的使用。

在联合索引的基础上，又产生了一种覆盖索引，也就是直接从非聚集索引上就可以查到数据。

mysql>  explain select name,age from test where age = 1;
+----+-------------+-------+-------+---------------+---------+---------+------+--------+--------------------------+
| id | select_type | table | type  | possible_keys | key     | key_len | ref  | rows   | Extra                    |
+----+-------------+-------+-------+---------------+---------+---------+------+--------+--------------------------+
|  1 | SIMPLE      | test  | index | NULL          | union_x | 38      | NULL | 997182 | Using where; Using index |
+----+-------------+-------+-------+---------------+---------+---------+------+--------+--------------------------+

由于name、age组成了联合索引，通过非聚集索引（辅助索引）就可以找到name和age。
通过覆盖索引查询则无需再去聚集索引查询数据，可以减少磁盘I/O。

上文提到B+树高度一般在2 ~ 4层，这是由InnoDB存储引擎数据组织方式决定的。

在磁盘中，最小的存储单元扇区，每一个扇区大小为512字节。
在文件系统中，最小的存储单元是块，每一个块大小为4KB。
在InnoDB中，最小的存储单元是页，每一页大小为16KB。

在数据表中，数据都是存储在页上，一页16KB，如果一行数据1KB，那么一页可以存储16行数据。
假设主键大小为8字节，指针大小为6字节，则一个非叶子节点页可以存储16*1024/(8+6)=1170个单元。

如果高度为2，每个单元都指向一个页，那么可以存储1170*16=18720条记录。
如果高度为3，那么可以存储1170*1170*16=21902400条记录，大概2000万条。
如果高度为4，那么可以存储1170*1170*1170*16=25625808000条记录，大概200亿条。

一般来说，一张表数据量到了2000万条算多的了，不至于到200亿条。因此，B+树高度一般在2-4层，对于磁盘来说，1秒可以进行100次磁盘I/O操作，加载3层B+树，需要3次磁盘I/O，也就是0.03秒。