Mysql 探索 (一):B-Tree 索引
备注:公众号原名张狗蛋的技术之路，现已改名为程序员历小冰
MySQL 是目前业界最为流行的关系型数据库之一，而索引的优化也是数据库性能优化的关键之一。所以，充分地了解 MySQL 索引有助于提升开发人员对 MySQL 数据库的使用优化能力。
MySQL 的索引有很多种类型，可以为不同的场景提供更好的性能。而 B-Tree 索引是最为常见的 MySQL 索引类型，一般谈论 MySQL 索引时，如果没有特别说明，就是指 B-Tree 索引。本文就详细讲解一下 B-Tree 索引的的底层结构，使用原则和特性。
为了节约你的时间，本文的主要内容如下：
B-Tree 索引的底层结构
B-Tree 索引的使用规则
聚簇索引
InnoDB 和 MyISAM 引擎索引的差异
松散索引
覆盖索引
B-Tree 索引
B-Tree 索引使用 B-Tree 来存储数据，当然不同存储引擎的实现方式不同。B-Tree 通常意味着所有的值都是按顺序存储的，并且每一个叶子页到根的距离相同，图 1 展示了 B-Tree 索引的抽象表示，由此可以看出 MySQL 的 B-Tree 索引的大致工作机制。
B-Tree 索引的底层数据结构一般是 B+树，其具体数据结构和优势这里就不作详细描述，图 1 展示了 B-树索引的抽象表示，大致反应了 MyISAM 索引是如何工作的，而 InnoDB 使用的结构有所不同。
图 1 B-Tree 索引的底层结构示意图
MySQL 可以在单独一列上添加 B-Tree 索引，也可以在多列数据上添加 B-Tree 索引，多列的数据按照添加索引声明的顺序组合起来，存储在 B-Tree 的页中。假设有如下数据表：
对于表中的每一行数据，索引中包含了 last_name，first_name 和 birthday 列的值，图 2 展示了该索引是如何组织数据的存储的。
图 2 多列索引
B-Tree 索引使用 B-Tree 作为其存储数据的数据结构，其使用的查询规则也由此决定。一般来说，B-Tree 索引适用于全键值、键值范围和键前缀查找，其中键前缀查找只适用于根据最左前缀查找。B-Tree 索引支持的查询原则如下所示：
全值匹配：全值匹配指的是和索引中的所有列进行匹配，
匹配最左前缀：前边提到的索引可以用于查找所有姓 Allen 的人，即只使用索引中的第一列。
匹配列前缀：也可以只匹配某一列的值的开头部分。例如前面提到的索引可用于查找所有以 J 开头的姓的人。这里也只用到了索引的第一列。
匹配范围值：例如前边提到的索引可用于查找姓在 Allen 和 Barrymore 之间的人。这里也只使用了索引的第一列。
精确匹配某一列并范围匹配另外一列：前边提到的索引也可用于查找所有姓为 Allen，并且名字是字母 K 开头(比如 Kim,Karl 等)的人。即第一列 last_name 全匹配，第二列 first_name 范围匹配。
因为索引树的节点是有序的，所以除了按值查找之外，索引还可以用于查询中的 ORDER BY 操作(按顺序查找)，如果 ORDER BY 子句满足前面列出的几种查询类型，则这个索引也可以满足对应的排序需求。
下面是一些关于 B-Tree 索引的限制：
如果不是按照索引的最左列开始查找，则无法使用索引。例如上面例子中的索引无法查找名字为 Bill 的人，也无法查找某个特定生日的日，因为这两列都不是最左数据列。
如果查询中有某个列的范围查询，则其右侧所有列都无法使用索引优化查找。
聚簇索引
聚簇索引并不是一种单独的索引类型，而是一种数据存储方式。具体的细节依赖于其实现方式，但是 InnoDB 的聚簇索引实际上在同一个结构中保存了 B-Tree 索引和数据行。
当表有聚簇索引时，它的数据行实际上存放在索引的叶子页中，这也就是说数据行和相邻的键值紧凑地存储在一起。
图 3 展示了聚簇索引中的记录是如何存放的。注意到，叶子页包含了行的全部数据行，但是节点页只包含了索引列。
图 3 聚簇索引
聚簇索引可能对性能有帮助，但也可能导致严重的性能问题。聚簇的数据是有一些重要的优点：
数据访问更快，聚簇索引将索引和数据保存在同一个 B-Tree 中，因此从聚簇索引中获取数据通常比在非聚簇索引中查找要快。
使用覆盖索引扫描的查询可以直接使用页节点中的主键值。
如果在设计表和查询时能充分利用上面的优点，那么就能极大地提升性能。同时，聚簇索引也有一些缺点：
插入顺序严重依赖插入顺序。按照主键的顺序插入是向 InnoDB 表中插入数据速度最快的方式，需要避免主键键值随机的(不连续且值得分布范围非常大)聚簇索引，比如使用 UUID 作为主键，而应该使用类似 AUTO_INCREMENT 的自增列。
更新聚簇索引列的代价很高，因为会强制 InnoDB 将每个被更新的行移动位置到新的位置。
基于聚簇索引的表在插入新行，或者主键被更新导致需要移动行时，可能面临“页分裂”的问题。当行的主键值要求必须将这行插入到某个已满的页中时，存储引擎会将该页分裂成两个页面来容纳该行，这就是一次页分裂操作。页分裂会导致表占用更多的磁盘空间
二级索引可能比想象的更大，因为在二级索引中的叶节点包含了引用行的主键列
二级索引访问需要两次索引查找，而不是一次。
InnoDB 和 MyISAM 的索引区别
聚簇索引和非聚簇索引的数据分布有区别，以及对应的主键索引和二级索引的数据分布也有区别，通常会让人感到困惑和意外。图 4 展示了 MyISAM 和 InnoDB 的不同索引和数据存储方式。 MyISAM 的数据分布非常简单，按照数据插入的顺序存储在磁盘上，主键索引和二级索引的叶节点存储着指针，指向对应的数据行。 InnoDB 中，聚簇索引“就是”表，所以不会像 MyISAM 那样需要独立的行存储。聚簇索引的每个叶节点都包含了主键值和所有的剩余列(在此例中是 col2)。 InnoDB 的二级索引和聚簇索引很不同。InnoDB 二级索引的叶节点中存储的不是“行指针”，而是主键值，并以此作为指向行的“指针”。
图 4 InnoDB 和 MyISAM 的区别
松散索引扫描
MySQL 并不支持松散索引扫描，也就是无法按照不连续的方式扫描一个索引。通常，MySQL 的索引扫描需要先定义一个起点和终点，即使需要的数据只是这段索引中很少数的几个，MySQL 仍然需要扫描这段索引中的每个条目。 下面，我们通过一个示例说明这点，假设我们有如下索引(a,b)，有下面的查询：
因为索引的前导字段是列 a，但是在查询中只指定了字段 b，MySQL 无法使用这个索引，从而只能通过全表扫描找到匹配的行，如图 5 所示。
图 5 全表扫描
了解索引的物理结构的话，不难发现还可以有一个更快的办法执行上面的查询。索引的物理结构(不是存储引擎的 API)是的可以先扫描 a 列第一个值对应的 b 列的范围，然后再跳到 a 列第二个不不同值扫描对应的 b 列的范围。图 6 展示了如果由 MySQL 来实现这个过程会怎样。
图 6 松散索引
注意到，这时就无须再使用 WHERE 子句过滤，因为松散索引扫描已经跳过了所有不需要的记录。 MySQL 5.0 之后的版本，在某些特殊的场景下是可以使用松散索引扫描的，例如，在一个分组查询中需要找到分组的最大值和最小值：
在 EXPLAIN 中的 Extra 字段显示"Using index for group-by"，表示这里将使用松散索引扫描。
覆盖索引
索引除了是一种查找数据的高效方式之外，也是一种列数据的直接获取方式。MySQL 可以使用索引来直接获取列的数据，这样就不需要读取数据行。如果一个索引包含所有需要查询的字段的值，我们就称之为“覆盖索引”。 覆盖索引是非常有用的工具，能够极大地提高性能。SQL 查询只需要扫描索引而无需回表，会带来很多好处：
索引条目数量和大小通常远小于数据行的条目和大小，所以如果只需要读取索引，那么 MySQL 就会极大地减少数据访问量。
因为索引是按照列顺序存储的，所以对于 I/O 密集型的范围查找会比随机从磁盘读取每一行数据的 I/O 要少的多。
由于 InnoDB 的聚簇索引，覆盖索引对 InnoDB 表特别有用。InnoDB 的二级索引在叶子节点中保存了行的主键，索引如果二级主键能够覆盖查询，则避免对主键索引的第二次查询。
当发起一个被覆盖索引的查询(也叫索引覆盖查询)时，在 EXPLAIN 的 Extra 列可以看到"Using Index"的信息。例如，表 sakila.inventory 有一个多列索引(store_id, film_id)。MySQL 如果只需要访问这两列，就可以使用这个索引做覆盖索引，如下所示：
备注:公众号原名张狗蛋的技术之路，现已改名为程序员历小冰
版权声明: 本文为 InfoQ 作者【程序员历小冰】的原创文章。
原文链接:【http://xie.infoq.cn/article/a0595ff42a4a42c627c66f176】。文章转载请联系作者。
程序员历小冰 2018.04.28 加入
历小冰的技术博客，专注于探讨后端生态的点点滴滴，内容包括微服务、分布式、数据库、性能调优和各类源码分析。
评论