MySQL中Innodb的B-Tree索引

数据库

本文将介绍MySQL中Innodb的B-Tree索引的相关知识。

数据库索引是数据库开发中非常重要的一个部分，如果想写出好的查询，就必须对索引有比较深刻的理解。人们对索引的了解经常是一知半解的，这就导致很多误用的情况，不但没有提高查询性能，反而大大降低了性能。

简单地说，索引是一种数据结构，我们可以利用索引来快速找到数据。一个现实生活中的例子是查字典，查字典有很多种方式，就中文字典来说，可以使用偏旁部首、拼音、笔画数等信息来查询，这实际上就是对一个字的不同属性建立了索引信息。查字典这个场景可以类比到数据库中，字典对应数据库的一张表，每个字对应表中的一行，每行中有偏旁部署、拼音、笔画数等信息的列，然后针对这些列建立索引。

B-Tree索引

大部分情况下我们谈论到索引都是B-Tree索引。在B-Tree索引中，数据是按照顺序被存储的，因此很适合查询范围数据。B-Tree索引的节点页不存放具体数据，它存放的是索引列的值和指向下一层节点页的指针，叶子页中则存放了指向具体数据的指针，且叶子页到根的距离都是相同的。下面是B-Tree索引的示意图（图片来自《高性能MySQL(第三版)》）：

B-Tree索引

从图中可以发现，每个节点页中都保存了索引列的值，用来和具体的值进行比较，以找到合适的通往下层节点的指针。比如key1这个节点页，其左指针指向的是值小于key1的节点页，右指针指向的是值大于等于key1但小于key2的节点页。需要注意的是，每个叶子页中都保存了下一个叶子页的指针，方便直接查询下一个数据，这样就不用返回上一层重新查找了。

在同层的节点页之间，也有如下关系（key是节点页的索引列的值）：

key1 < key2 < … < keyN

在查找时，不需要进行全表扫描，而是从根节点出发，根节点保存了指向子节点的指针，存储引擎顺着这些指针向下查找，通过比较节点页的值和要查找的值就可以找到通往下层节点页的指针，直到找到匹配的一个或多个节点，如果没有找到匹配的节点，说明查询的值在表中不存在。

在上图中只画出了一层节点页，实际上可能存在很多层节点页，表中的数据数量和树的深度相关。上图中叶子页中值是顺序排列的，因此范围查找的效率很高。

B-Tree索引对于以下几类查询是适用的：

  1. 全值匹配
    对索引中的所有列进行匹配。
  2. 匹配最左前缀
    使用最左前缀规则匹配列。
  3. 匹配列前缀
    匹配某一列的值的开头部分。
  4. 匹配范围值
    匹配一个列中某个范围的值。
  5. 精确匹配某一列并范围匹配另外一列
    这个应该很好理解。
  6. 只访问索引的查询（覆盖索引）
    如果查询访问的所有列都在索引范围内，可以使用覆盖索引，这将大大提高查询的效率，因为不需要再去查找具体的数据行了。

由于数据是按顺序排列的，所以对于order by操作，只要是符合最左前缀规则的，B-Tree索引都可以提供支持。

刚才一直提到最左前缀，这到底是什么呢？用一个例子说明最合适不过了，假设有一个表如下：

1
2
3
4
5
6
CREATE TABLE user(
    last_name varchar(50) not null,
    first_name varchar(50) not null,
    birthday date not null,
    key(last_name, first_name, birthday)
);

这个表有一个索引，包含了last_name、first_name和birthday三列。以下是几种利用索引有限制的情况：

  1. 查询特定first_name的用户将不能利用索引。
  2. 查询特定birthday的用户将不能利用索引。
  3. 查询特定first_name和特定birthday的用户将不能利用索引。
  4. 查询last_name以’h’结尾的用户将不能利用索引。
  5. 当查询特定的last_name和特定的birthday时（没有指定first_name），只能利用索引的第一列。
  6. 如果某个条件是一个范围查询，则其后的所有列将无法利用索引，比如where last_name='Smith' and first_name like 'J%' and birthday = '1988-12-23'，这个查询只能利用索引的前两列。

由此可以看出，在B-Tree索引中，索引列的顺序是非常重要的。并不是只要建立的相应列的索引，查询就一定能用上。

数据库