索引类型之B-Tree索引

一. 前言

索引是存储引擎中用于快速找到记录的一种数据结构。索引的类型有很多，可以为不同场景提供更好的性能。在Mysql中，索引是在存储引擎层而不是在服务层上实现的。这里介绍一下常用的 B-Tree索引。

二. B-Tree索引

1. 简介

当人们谈论索引的时候，如果没有特别指明类型，那多半就是B-Tree索引。
存储引擎上以不同方式使用B-Tree索引，性能各不相同，各有优劣。例如，MyISAM使用 前缀压缩技术使得索引更小，但 InnoDB 则按照原数据格式进行存储。再如 MyISAM 索引通过数据的物理位置引用索引的行，而 InnoDB 则根据主键引用被索引的行。

2. InnoDB上B-Tree的结构

B-Tree 通常意味着所有的值都是按顺序存储的，并且每一个叶子到根的距离相同。

图一为 B-Tree树的结构，每一层节点都会带上数据

图二为实例化的B+Tree, 只有叶子节点才会带上数据

其中关于B树和 B+树的区别，文章有很多，这里只说几个明显的的区别

1. B+ 树是 B-树的变体，也是一种多路搜索树，并且所有叶子节点位于同一层
2. B+Tree 为所有的叶子节点增加了一个链路指针，即支持范围检索
3. B+Tree 只有叶子节点才存储 data, 内部节点都只存储索引值

B-Tree 索引能够加快访问速度，因为存储引擎不再需要进行全表扫描来获取数据，取而代之的是从索引的根节点开始进行搜索。根节点存放了指向叶子节点的指针，存储引擎根据这些指针想下层查找。通过比较节点页的值和要查找的值可以找到合适的指针进入下层子节点，这些指针实际上定义了子节点页中值的上限和下限。
(在Mysql中，虽然它的索引类型是BTREE，但数据结构上使用的是B+Tree)

3. 案例说明

建表语句:

CREATE TABLE `People` (
  `last_name` varchar(50) NOT NULL,
  `first_name` varchar(50) NOT NULL,
  `dob` date NOT NULL,
  `gender` enum('m','f') NOT NULL,
  KEY `key` (`last_name`,`first_name`,`dob`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4

我们插入了一些数据。对于表中的每一行数据，索引中包含了last_name,first_name,dob列的值，下图表示数据是如何存储的。

B-Tree 索引适用于全键值，键值范围或键前缀查找。其中键前缀查找只适用于根据最左前缀查找。

• 全值匹配
  全值匹配指的是和索引中所有列进行匹配，例如前面提到的缩影可用于查找姓名为Cuba Allen, 出生于 1960-01-01 的人

• 匹配最左前缀
  前面提到索引可用于查找所有姓为 Allen 的人，即只使用索引的第一列。
  也可以只匹配某一列的值的开头部分。例如前面提到索引可用于查找所有 J 开头姓的人，这里也只使用了索引的第一列

• 匹配范围值
  例如前面提到的索引可以用于查找所有姓为 Allen, 并切名字是字母 K 开头(比如 Kim, Karl 等)的人。即第一列 last_name 全匹配，第二列 first_name 范围匹配。

Tips:

1. 如果不按最左前缀查找，则无法使用索引，例如不能查找名字 (first_name) 为 Bill的人，也无法查找特定生日的人。类似地，也无法查找姓氏以某个字母结尾的人
2. 不能跳过索引中的列，比如查找姓为 Smith 并且某个特定日期生的人，这时候不指定名 (first_name), 则Mysql 只能使用索引的第一列
3. 如果查找中有某个列的方位查询，则其右边所有列都无法使用索引优化查找。例如有查询 Where last_name=‘Smith’ And first_name Like ‘J%’ And dob = ‘1976-12-23’, 这个查询只能使用索引的钱两列，因为这里 Like 是一个范围条件。