B+树和MySQL InnoDB索引

B+树可能不是InnoDB的最优选择，但是它一定是能够满足当时设计场景的需要，从B+树作为数据库底层的存储结构到今天已经过了几十年的时间，我们不得不说优秀的工程设计确实有足够的生命力。

References

InnoDB存储引擎支持以下几种常见的索引：

  • 哈希索引（Hash）
    除了Memory引擎和NDB集群引擎支持哈希索引外，InnoDB引擎会根据表的使用情况自动为表生成哈希索引（自适应哈希索引, adaptive hash index），当InnoDB注意到某些索引值被使用非常频繁时，会在内存中基于B-Tree索引之上再创建一个哈希索引，不过这是完全内部的行为，不能人为干预是否在表中生成哈希索引，有必要也可以关闭此功能。
  • 全文索引（Full-Text）
    全文索引是一种特殊的索引，它查找的是文本中的关键词，而不是直接比较索引中的值，全文索引和其它几种索引的匹配方式完全不一样。它有许多要注意的细节，如停用词、词干和复数、布尔搜索等。全文索引更类似于搜索引擎做的事，而不是简单的WHERE条件匹配。比如查找一个单次“Hello”在哪些文档中出现的位置。普通索引根据key查找文档信息，全文索引根据文档中的信息查找文档的key。全文索引通常使用倒排索引（inverted index）实现，由于有Lucene这种专业的全文搜索引擎，实际上MySQL的全文索引也没多大用处。
  • B+数索引（B-Tree）
    B+树索引就是传统意义上的索引（B不是二叉(binary)，而是代表平衡(balance)），这是目前关系型数据库系统中最常用和最为有效的索引。B+树索引的构造类似于二叉树，根据键值（Key Value）快速找到数据。由于B+树涉及的内容比较多，下面慢慢来说。

在介绍B+树索引之前，先了解下相关的算法和数据结构，有助于更好的理解B+树索引的工作方式。

  • 二分查找法

二分查找法（binary search）也称为折半查找法，用来查找一组有序的记录数组中的某一记录。其基本思想是：将记录按有序化（递增或递减）排列，在查找过程中采用跳跃式查找，即先以有序数列的中点位置为比较对象，若要找的元素小于该中点元素，则查找范围缩小为左半部分，否则为右半部分。通过一次比较，将查找区间缩小一半。如下图所示：
binary-search.gif

从上图可以看出，用了5次找到了639这个数，如果是顺序查找需要21次，因此二分查找法的效率比顺序查找要好（平均来说）。如果查22这个数，顺序查找只需1次，而二分查找需要5次。对于这32个数来说，顺序查找的平均查找次数为16.5次，二分查找的平均查找次数为4.0625次。最坏的情况下，顺序查找的次数为32，而二分查找为5.

  • 二叉查找树和平衡二叉树

二叉查找树（Binary Search Tree）是一种经典的数据结构，在二叉查找树中，左子树的键值总是小于根的键值，右子树的键值总是大于根的键值。因此可以通过中序遍历得到键值的排序输出。下图中的二叉查找树经过中序遍历后输出：2、3、5、6、7、8. 二叉查找树体现了二分查找的思想。
binary-search-tree.png

二叉查找树可以任意的构造，上图同样的数字也可按照下图的方式建立二叉查找树。
binary-search-tree2.png

显然这颗二叉查找树的效率就降低了，因此若想最大性能的构造一个二叉查找树，就需要这颗二叉查找树是平衡的，从而引出了新的定义——平衡二叉树，或称为AVL树。

平衡二叉树首先要符合二叉查找树的定义，其次必须满足任何节点的两个子树的高度最大差为1.平衡二叉树的查找性能是比较高的，但不是最高的，只是接近最高性能。最好的性能需要建立一颗最优二叉树，但是最优二叉树的建立和维护需要大量的操作，因此一般只需建立一颗平衡二叉树即可。

平衡二叉树的查询速度的确很快，但是维护一颗平衡二叉树的代价是非常大的。通常来说，需要1次或多次左旋(Left Rotation)和右旋(Right Rotation)来得到插入或更新后树的平衡性。除了插入操作，还有更新和删除操作都是通过左旋或优选来完成的，因此维护一颗平衡树是有一定开销的，不过平衡二叉树多用于内存结构对象中，因此维护的开销相对较小。
left-rotation.gif

multi-rotation.gif

  • B树

B树也称B-树,它是多路树（Multiway Tree, m-way tree）的一个特殊版本。那什么又是多路树？很简单，多路树可以有多个子节点，比如二叉树有两个节点一样。m阶的多路树指其中一棵树可以有m个子节点。m路树中的节点由关键字段（key fields）和指向子节点的指针组成。
描述一颗B树时需要指定它的阶数，阶数表示了一个结点最多有多少个孩子结点，一般用字母m表示阶数。当m取2时，就是我们常见的二叉搜索树。B树在节点中存储大量键值同时能够将树的高度保持相对较小。
一颗m阶的B树定义如下：

  1. 每个结点最多有m-1个关键字。
  2. 根结点最少可以只有1个关键字。
  3. 非根结点至少有Math.ceil(m/2)-1个关键字。
  4. 每个结点中的关键字都按照从小到大的顺序排列，每个关键字的左子树中的所有关键字都小于它，而右子树中的所有关键字都大于它。
  5. 所有叶子结点都位于同一层，或者说根结点到每个叶子结点的长度都相同。

B树通过分裂和合并来维护B树的属性，下图演示一个3阶的B树添加一个新值：
m-way-tree-3-degree.gif

  • B+树

B+树通过二叉查找树，再由平衡二叉树，B树演化而来。B+树有B树和索引顺序访问方法（ISAM，是不是很熟悉？对，这也是MyISAM引擎最初参考的数据结构）演化而来，B+树和B树的区别在于，B树的关键字段(key field)和数据可以存储为内部节点（internal node）和叶子节点(leaf node)，但是在B+树中，数据只能存储为叶子节点，关键字段只能存储为内部节点。
1_fxAlyQVV3uT4de912FLHfA.jpeg

B+树为了保持平衡可能会对插入的键值做拆分页（split）操作，类似于平衡二叉树的旋转。
b+tree.gif

  • B+树索引

在数据库中B+树的高度一般在2~4层，也就是说查找某一键值的行记录时最多只需要2到4次I/O，当前一般的机械磁盘至少可以做到100次I/O，2~4次的I/O意味着查询时间只需0.02~0.04秒。数据库中的B+树索引可以分为聚簇索引（clustered index）和二级索引（secondary index,也叫非聚簇索引（non-clustered index）或辅助索引），但内部都是B+树，叶子节点存放所有数据。
Snipaste_2021-03-21_22-43-25.png

每个InnoDB表都有一个特殊的索引叫聚簇索引，聚簇索引包含行数据，除聚簇索引外的所有索引都称为二级索引（secondary index）。

  • 当表定义了PRIMARY KEY，InnoDB优先使用PK作为聚簇索引
  • 如果没有定义PK，MySQL选第一个所有列都是非空（NOT NULL）的唯一索引（UNIQUE index）作为聚簇索引
  • 如果表既没有PK，也没有合适的唯一索引，InnoDB内部生成一个隐藏的聚簇索引叫做GEN_CLUST_INDEX（在一个包含row ID的合成列上，row ID是一个6字节的自增字段）。

以上图数据为例，聚簇索引的结构如下图所示
Snipaste_2021-03-23_22-52-00.png

同B+树数据结构一样，每个数据页都通过一个双向链表来进行链接。由于实际的数据页只能按照一棵B+树进行排序，因此每张表只能拥有一个聚簇索引。在多数情况下，查询优化器倾向于采用聚簇索引。因为聚簇索引能够在B+树索引的叶子节点上直接找到数据。此外，由于定义了数据的逻辑顺序，聚簇索引能够特别快地访问针对范围值的查询。查询优化器能够快速发现某一段范围的数据页需要扫描。

聚簇索引对主键查询有很高的性能，不过它的二级索引（secondary index，非主键索引）中必须包含主键列，所以如果主键列很大的话，其他的所有索引都会很大。若表上的索引较多的话，主键应尽可能的小。二级索引的存在并不影响数据在聚簇索引中的组织，因此每张表上可以有多个二级索引。当通过二级索引来寻找数据时，InnoDB存储引擎会遍历辅助索引并通过叶子节点的指针获得指向主键索引的主键，然后再通过主键索引来找到一个完整的行记录。此处以index(userid, buy_date)为例，叶子节点包含了索引的数据和主键。
Snipaste_2021-03-23_22-52-42.png

若想通过此索引查询price数据，只能先找到对应的主键，再用主键去聚簇索引中获取price，这个过程叫回表，因为消耗了太多次的I/O操作需要尽量避免。如果二级索引中已经包含了需要查询的数据，比如此处查询buy_date数据，那么就可以直接返回数据而不需要回表，称之为覆盖索引。覆盖索引有很多优点如内存占用小、减少硬盘I/O次数等，但是并不是每个索引都能做成覆盖索引，需要根据实际做出取舍。没有最好的，只有最合适的。（其实这么多乱七八糟的装逼名词说的都是一件事，理解意思就行）

索引可以包含一个或多个列的值。如果索引包含多个列，那么列的顺序也十分重要，因为MySQL只能高效地使用索引的最左前缀(leftmost prefix)。创建一个包含两个列的索引，和创建两个只包含一列的索引是大不相同的。在一个多列索引中，索引列的顺序意味着索引首先按照最左列进行排序，其次是第二列，等等。当ORDER BY、GROUP BY和DISTINCT等子句的查询需求和索引列的顺序一致时，就可以通过索引按照升序或者降序进行扫描。
其实理解了B+树的构造就不难理解为什么最左前缀匹配必须和索引列的顺序一致了，以上表index(userid, buy_date)为例，直接查询buy_date是不能走索引的，因为在这个索引中buy_date并不是有序的，而即使不查buy_date只查询userid却可以走索引，因为userid在这个索引中是有序的。看如下的几条查询:

EXPLAIN SELECT id, userid, buy_date, price FROM `buy_log` WHERE userid = 3;
+------+-------------+---------+------+-----------------+--------+---------+-------+------+-------+
| id   | select_type | table   | type | possible_keys   | key    | key_len | ref   | rows | Extra |
+------+-------------+---------+------+-----------------+--------+---------+-------+------+-------+
|    1 | SIMPLE      | buy_log | ref  | userid,userid_2 | userid | 4       | const | 2    |       |
+------+-------------+---------+------+-----------------+--------+---------+-------+------+-------+
1 row in set (0.000 sec)

EXPLAIN SELECT id, userid, buy_date, price FROM `buy_log` WHERE userid = 3 AND buy_date = STR_TO_DATE('2009-01-01', '%Y-%m-%d');
+------+-------------+---------+------+-----------------+----------+---------+-------------+------+-----------------------+
| id   | select_type | table   | type | possible_keys   | key      | key_len | ref         | rows | Extra                 |
+------+-------------+---------+------+-----------------+----------+---------+-------------+------+-----------------------+
|    1 | SIMPLE      | buy_log | ref  | userid,userid_2 | userid_2 | 8       | const,const | 1    | Using index condition |
+------+-------------+---------+------+-----------------+----------+---------+-------------+------+-----------------------+
1 row in set (0.000 sec)

EXPLAIN SELECT id, userid, buy_date, price FROM `buy_log` WHERE buy_date = STR_TO_DATE('2009-01-01', '%Y-%m-%d') AND userid = 3;
+------+-------------+---------+------+-----------------+----------+---------+-------------+------+-----------------------+
| id   | select_type | table   | type | possible_keys   | key      | key_len | ref         | rows | Extra                 |
+------+-------------+---------+------+-----------------+----------+---------+-------------+------+-----------------------+
|    1 | SIMPLE      | buy_log | ref  | userid,userid_2 | userid_2 | 8       | const,const | 1    | Using index condition |
+------+-------------+---------+------+-----------------+----------+---------+-------------+------+-----------------------+
1 row in set (0.000 sec)

EXPLAIN SELECT id, userid, buy_date, price FROM `buy_log` WHERE buy_date = STR_TO_DATE('2009-01-01', '%Y-%m-%d');
+------+-------------+---------+------+---------------+------+---------+------+------+-------------+
| id   | select_type | table   | type | possible_keys | key  | key_len | ref  | rows | Extra       |
+------+-------------+---------+------+---------------+------+---------+------+------+-------------+
|    1 | SIMPLE      | buy_log | ALL  | NULL          | NULL | NULL    | NULL | 7    | Using where |
+------+-------------+---------+------+---------------+------+---------+------+------+-------------+
1 row in set (0.000 sec)

从第2和第3条查询可以看出，WHERE后的子句顺序不重要，优化器会帮我们自动优化到和索引相匹配。
从第1和第2条查询可以看出，即使只使用了索引前面一部分，也可以通过索引查询。（这就是最左匹配, leftmost prefix）
从第1、第2条和第4条查询可以看出，当索引列的顺序和WHERE子句中列顺序不是从第一列开始匹配时就不能通过索引查询，只能全表扫描。（即不满足最左匹配）
因此多列索引的列顺序至关重要。考虑下这种情况，有这么一个索引(col1, col2, col3)，如下查询是否会走索引？

SELECT * FROM tbl_name WHERE col1=val1;
SELECT * FROM tbl_name WHERE col1=val1 AND col2=val2;

SELECT * FROM tbl_name WHERE col2=val2;
SELECT * FROM tbl_name WHERE col2=val2 AND col3=val3;

答案可以查看上面多列索引官方文档，那么这个查询呢？SELECT * FROM tbl_name WHERE col1=val1 AND col3=val3;，其实我们只看第一个条件就可以走索引了：SELECT * FROM tbl_name WHERE col1=val1;也就是部分索引生效，其余的条件还是要计算。实际测试下：
Snipaste_2021-03-22_14-36-38.png

EXPLAIN
SELECT * FROM `test` WHERE c1 = 2 AND c2 = 1 AND c3 = 'aaa';
+------+-------------+-------+------+---------------+------+---------+-------------------+------+-----------------------+
| id   | select_type | table | type | possible_keys | key  | key_len | ref               | rows | Extra                 |
+------+-------------+-------+------+---------------+------+---------+-------------------+------+-----------------------+
|    1 | SIMPLE      | test  | ref  | c1            | c1   | 268     | const,const,const |    1 | Using index condition |
+------+-------------+-------+------+---------------+------+---------+-------------------+------+-----------------------+
1 row in set (0.001 sec)

EXPLAIN
SELECT * FROM `test` WHERE c1 = 2;
+------+-------------+-------+------+---------------+------+---------+-------+------+-------+
| id   | select_type | table | type | possible_keys | key  | key_len | ref   | rows | Extra |
+------+-------------+-------+------+---------------+------+---------+-------+------+-------+
|    1 | SIMPLE      | test  | ref  | c1            | c1   | 5       | const |    2 |       |
+------+-------------+-------+------+---------------+------+---------+-------+------+-------+
1 row in set (0.000 sec)

EXPLAIN
SELECT * FROM `test` WHERE c1 = 2 AND c3 = 'aaa';
+------+-------------+-------+------+---------------+------+---------+-------+------+-----------------------+
| id   | select_type | table | type | possible_keys | key  | key_len | ref   | rows | Extra                 |
+------+-------------+-------+------+---------------+------+---------+-------+------+-----------------------+
|    1 | SIMPLE      | test  | ref  | c1            | c1   | 5       | const |    2 | Using index condition |
+------+-------------+-------+------+---------------+------+---------+-------+------+-----------------------+
1 row in set (0.001 sec)

第一条和第二条都很容易理解，第三条就是上面说的只能部分走索引，可以看到第三条语句的key_len和第二条一样。

既然说到这了，就顺便再说下索引条件下推（Index Condition Pushdown）优化吧。
索引条件下推（索引下推, Index Condition Pushdown (ICP)）是MySQL5.6开始支持的一种索引查询优化。之前的版本不支持ICP，当进行索引查询时，首先根据索引来查找记录，然后再根据WHERE条件过滤记录。在支持ICP后，MySQL会在取出索引的同时，判断是否可以进行WHERE条件的过滤，也就是将WHERE的部分过滤操作放在了存储引擎层。可以减少上层SQL对记录的获取（fetch），从而提高性能。

关于ICP的使用和限制可以查看上文参考的官方文档，这里给出官方的例子以便理解：
假设一个表包含人员及其地址的信息，并且该表的索引定义为 INDEX (zipcode, lastname, firstname)。如果我们知道一个人的zipcode，但不确定lastname，可以这样搜索：

SELECT * FROM people
  WHERE zipcode='95054'
  AND lastname LIKE '%etrunia%'
  AND address LIKE '%Main Street%';

MySQL可以使用索引来扫描zipcode='95054'的人。第二部分（lastname LIKE '%etrunia%'）不能用于过滤扫描的行数。如果没有ICP，此查询必须取出zipcode='95054'所有行数据。
有了ICP，MySQL在读取整个表行之前会检查lastname LIKE '%etrunia%'。这样可以避免读取只匹配zipcode条件而不匹配lastname条件的索引对应的完整行。简言之：减少I/O。

MySQL选择B+树作为索引的数据结构的原因：（这段解建议查看上面参考链接原文，解释的非常详细）
如果我们使用B+树作为底层的数据结构，那么所有只会访问或者修改一条数据的SQL的时间复杂度都是O(log n)，也就是树的高度。

使用哈希却有可能达到O(1)的时间复杂度，看起来是不是特别的美好。但使用哈希构成的主键索引或者辅助索引对于处理范围查询或者排序性能会非常差，只能进行全表扫描并依次判断是否满足条件。全表扫描对于数据库来说是一个非常糟糕的结果，这其实也就意味着我们使用的数据结构对于这些查询没有任何效果。

B树和B+树在数据结构上其实有一些类似，它们都可以按照某些顺序对索引中的内容进行遍历，对于排序和范围查询等操作，B树和B+树相比于哈希会带来更好的性能，当然如果索引建立不够好或者SQL查询非常复杂，依然会导致全表扫描。那么为什么我们不选择B树呢？
B树与B+树的最大区别就是，B树可以在非叶结点中存储数据，但是B+树的所有数据其实都存储在叶子节点中，当一个表底层的数据结构是B树时，一条查询可以会在叶子节点和根节点、中间节点之间来回查找，这会带来大量的随机I/O。B+树中就不存在这个问题了，因为所有的数据行都存储在叶节点中，而这些叶节点可以通过『指针』依次按顺序连接，可以直接在多个子节点之间进行跳转，也不需要在不同层级的节点之间对数据进行拼接和排序，这样能够节省大量的磁盘I/O时间。

由于个人能力和时间限制，此处就不进一步分析索引的底层如：树的分裂和优化、磁盘预读等，想了解的可以查阅数据结构和操作系统等书籍资料。文中如有错误欢迎指正。

标签: none

添加新评论

ali-01.gifali-58.gifali-09.gifali-23.gifali-04.gifali-46.gifali-57.gifali-22.gifali-38.gifali-13.gifali-10.gifali-34.gifali-06.gifali-37.gifali-42.gifali-35.gifali-12.gifali-30.gifali-16.gifali-54.gifali-55.gifali-59.gif

加载中……