B+树索引和其使用

一、B 树索引

各个数据页组成双向链表，每个数据页中的记录会按照主键值从小到大的顺序组成一个单向链表。

1.1 没有索引时进行查找

假设搜索条件为某个列等于某个常数的情况：

SELECT [查询列表] FROM 表名 WHERE 列名 = xxx;

（1）若此时只有一个页，根据搜索条件不同分为两种情况：

• 以主键为搜索条件：在页目录中使用二分法定位到对应的槽，然后再遍历该槽对应分组中的记录，即可定位指定记录
• 以其他列为搜索条件：数据页中并没有为非主键列建立页目录，所以只能从Infinum记录开始依次遍历

（2）若有很多数据页，此时需要首先沿着双向链表一页一页地根据情况（1）确定此页有没有目标记录，时间复杂度极高。

于是需要一种高效完成搜索的方法——索引。

1.2 索引

先建个表：

其对应的行格式示意图：

关于行格式及相关字段含义参照文章：
https://blog.csdn.net/sunximei/article/details/121249738

1.3 一个简单的索引方案

我们的第一个需求就是快速定位一个记录所在的数据页。想到在一个页中根据主键值定位记录采用的页目录方法，我们也可以为数据页建立一个别的目录。
在建立此目录的过程中需完成两件事：

1. 下一个数据页中的记录主键值需大于上一页中的。
假设每页最多只能存放3条记录。首先向index_demo表插入3条记录：

INSERT INTO index_demo VALUES (1, 4, 'u'), (3, 9, 'd'), (5, 3, 'y');

此时再插入一条记录：

INSERT INTO index_demo VALUES (4, 4, 'a');

由于记录数超过页最大容量，于是分配新页。但为了使得新页中的主键值大于旧页，所以需要将主键值为5的记录移动至新页，然后再将主键值为4的记录插入旧页。这个过程也可称为页分裂。

注：新分配的页编号可能不是连续的，即在磁盘上并不相邻（不过InnoDB设计尽量让其相邻）

2. 给所有的页建立一个目录项
模拟向表中插入多条记录的效果：

由于这些大小为16KB的页在磁盘上并不相邻，所以需要为所有的页编制一个目录，每个页对应一个目录项，每个目录项包括两个部分：

• 页中用户记录的最小主键值key
• 页号page_no

效果如图：

然后将这些目录项在存储器上连续存储（如数组），就可以实现根据主键值快速查找记录（两次二分法）。这个目录就被称为索引。

1.4 InnoDB的索引方案

刚才的简易方案是基于所有目录项都可以在存储器上连续存储的前提下，实际上存在一些问题：

• InnoDB使用页作为管理存储单位的基本单位，即最多保证16KB连续存储空间。所以无法应对过多的目录项
• 执行删除操作时，会导致被删除项后的所有记录都前移，时间复杂度高；若作为冗余留在页中，又会浪费空间

所以，需要一种可以灵活管理所有目录项的方式。可以发现这些目录项与用户记录相似，只不过目录项中的两列是主键和页号而已，于是复用数据页来存储目录项，把这些目录项称为目录项记录。效果如图：

建立存储目录项记录的页后，查找就可以通过两次二分法实现了，并且能灵活管理目录项。

假设一个页最多存储四条目录项记录，若此时表中再插入一条用户记录，不仅会分配新的数据页存储用户目录，还会额外分配页来存储目录项记录：

那此时的查找如何进行呢？在一个存储目录项记录的页中，可以通过两次二分法查找记录，但现在有多个目录页，我们不知道记录对应在哪个目录页中，若要查找记录，需要变通过双向链表遍历所有目录页。

为了根据主键值快速定位一个相应的存储目录项的页，需要再建立一个上级目录。形成类似多级目录的形式：

这种数据结构就是B 树。可以看到，真正的用户记录存放在叶节点中，其他节点（非叶子节点）存放目录项记录。一般来说，我们使用的B 树不会超过四层。

1.5 InnoDB索引分类

• 聚簇索引。在叶子节点存放所有完整的用户记录。无需显示创建，InnoDB引擎会自动创建聚簇索引。所以在InnoDB中，聚簇索引就是数据的存储方式——“索引即数据，数据即索引”
• 二级索引。叶子节点中不是用户记录，而是对应的列 主键，目录页中目录项也变成列 页号。这种B 树需要执行回表操作才可以定位到完整的用户记录。
• 联合索引。同时为多个列建立索引。假设让B 树按照c2和c3列的大小进行排序（c2和c3建立联合索引），就是先把各个记录和页按照c2列进行排序，在c2列相同的情况下，再采用c3列进行排序。其实其本质上也是一个二级索引

1.6 MyISAM中索引方案简介

最大区别是，MyISAM将索引和数据分开，即“索引是索引，数据是数据”。

1.7 MySQL中创建和删除索引的语句

可以在建表时检录索引，或者在修改表结构时建立索引：

CREATE TABLE 表名{
	各个列...,
	KEY|INDEX 索引名 （对应列）
}

ALTER TABLE 表名 ADD KEY|INDEX 索引名 （对应列）;

KEY和INDEX任意选一个均可

建立联合索引例：

删除索引(DROP关键字)：

ALTER TABLE index_demo DROP INDEX idx_c2_c3;

二、B 树索引的使用

2.1 B 树索引示意图的简化

先建一个表：

一个聚簇索引和4个二级索引：

• id列为聚簇索引
• key1列建立二级索引idx_key1
• key2列建立唯一二级索引uk_key2
• key3列建立二级索引idx_key3
• key_part1、key_part2、key_part3列建立二级索引idx_key_part，且是联合索引

对于聚簇索引，也就是数据对应的B 树，简化一下画法：

对于二级索引，以idx_key1为例：

例如想通过idx_key1查找key1等于’abc’的记录，可以轻易定位到第一条key1列等于’abc’的二级索引记录，然后沿着单项链表向后扫描即可。

2.2 索引的代价

• 空间代价：显然要建立B 树
• 时间代价：增删该都需要修改B 树索引。导致存储引擎可能需要额外的时间来进行页分裂和页面回收等操作。

所以为了减少成本，避免建立不必要的索引，需要了解索引在执行期间是如何发挥作用的。

2.3 应用B 树索引

2.3.1 扫描区间和边界条件

对于查询语句：

SELECT * FROM single_table WHERE id >= 2 AND id <= 100;

这个语句是想查询id值在[2, 100]区间中的所有聚簇索引记录。我们可以通过索引的B 树快速定位到id值为2的那条记录，然后沿着单向链表向后扫描，直到id值不符合id<=100的条件。

为简便起见，将这个例子中待扫描的id值所在的区间（[2, 100]）称为扫描区间，对应的搜索条件（id >= 2 AND id <= 100）称为边界条件。

对于全表扫描来说，扫描区间为（-∞， ∞）。

对于下面的查询语句：

SELECT * FROM single_table WHERE key2 IN (1438, 6328) OR (key2 >= 38 AND key2 <= 79);

对应的扫描区间在数轴上表示：

从上述扫描区间中每获取一条二级索引记录，就需要根据该二级索引记录的id列的值执行回表操作。

然而并不是所有的搜索条件都可以称为边界条件，如：

SELECT * FROM single_table WHERE key1 < 'a' AND key3 > 'z' AND common_field = 'abc';

• 若使用idx_key1执行查询，则相应的扫描区间就是（-∞， ‘a’）;而key3 > ‘z’ AND common_field = 'abc’就是普通搜索条件而非边界条件，这些普通搜索条件需要在获取idx_key1的二级索引记录并执行回表操作，获取完整的记录后再判断是否成立。
• 同样的，如果使用idx_key3执行查询，（‘z’， ∞）,其他两个条件就成为普通搜索条件

对于B 树索引来说，只要索引列的常数使用=、<=>、IN、NOT IN、IS NULL、IS NOT NULL、>、<、>=、<=、!=、BETWEEN等连接起来，就能产生扫描区间。不过需要注意几点：

• IN与若干个=之间用OR连接起来的语义是一样的。
• key1 != a产生的扫描区间是(-∞, ‘a’)和(‘a’, ∞)
• LIKE操作符只有在匹配到完整字符串或字符串前缀时才产生合适的扫描区间。字符串的比较规则就是依次比较字符大小

例如对于搜索条件 key1 LIKE ‘a%’ 形成的扫描区间为[‘a’, ‘b’)。

关于复杂搜索条件确定扫描区间和联合索引确定扫描区间，详见《MySQL是怎样运行的》第七章。

2.3.2 索引用于排序

对于下面的查询语句：

SELECT * FROM single_table ORDER BY key_part1, key_part2, key_part3 LIMIT 10;

这个查询语句的结果需要先按照key_part1值排序；若key_part1值相同，再按照key_part2排序；若key_part1和key_part2都相同，再按照key_part3排序。可以发现，这种排序方法正是三者联合索引的排序方法，所以我们可以从第一条idx_key_part二级索引记录开始，沿着记录所在的单向链表向后扫描，取十条二级索引记录，针对每一条二级索引记录，都执行一次回表操作。获取完整的用户记录后发送给客户端即可。

1. 使用联合索引进行排序时的注意事项
使用联合索引时，ORDER BY子句后的列的顺序也必须按照索引列的顺序给出。ORDER BY key_part1 和 ORDER BY key_part1，key_part2这些仅对联合索引的索引列中左边连续的列进行排序的形式，也是可以利用B 树索引的。另外，当联合索引的索引列中左边连续的列为常量时，也可以使用联合索引对右边的列进行排序，比如下面的查询：

SELECT * FROM single_table WHERE key_part1 = 'a' AND key_part2 = 'b' ORDER BY key_part3 LIMIT 10;

2. 不可以使用索引进行排序的几种情况
（1）ASC、DESC混用
对于使用联合索引进行排序的场景，我们要求各个排序列的排序规则是一致的，即要么是升序（ASC），要么是降序（DESC）。
（记录在页中是通过单向链表递增排序的，降序情况下如何进行索引查询，即查询上一条记录？ 降序相对于升序来说较复杂一些，对于一条记录，首先向后遍历找到“带头大哥”，再从页目录中找到上一个槽，再由上一个槽的值找到本槽的第一个记录，从第一个记录向下遍历直到找到目标记录）

不过MySQL8.0引入了一种称为Descending Index的特性，可以支持ORDER BY子句中升降序混用。

（2）排序列中包含非同一索引的列
如：

SELECT * FROM single_table ORDER BY key1, key2 LIMIT 10;

（3）排序列是某个联合索引的索引列，但是这些排序列在联合索引中并不连续
如：

SELECT * FROM single_table ORDER BY key_part1, key_part3 LIMIT 10;

（4）排序不是以单独列名的形式出现在ORDER BY子句中，而是修饰过的形式，如 ORDER BY UPPER(key1)

2.3.3 索引用于分组

对于以下语句：

SELECT key_part1, key_part2, key_part3, COUNT(*) FROM single_table ORDER BY key_part1, key_part2, key_part3;

这个查询语句相当于执行了3次分组操作：
先按照key_part1值将记录进行分组，然后将key_part1值相同的组再按照key_part2分组，即大分组中细分小分组，然后对每个小分组再按照key_part3分组，即再细分更小的分组。

然后针对小小分组进行统计条数。若没有idx_key_part联合索引，就得建立一个用于统计的临时表，在扫描聚簇索引的时候将统计的中间结果填入此表，扫描完成后，再将此表作为结果集发送给客户端。 若有了idx_key_part，就不用建立临时表了。

注：分组列的排序也需要与索引列的顺序一致，也可以只使用索引列中左边连续的列进行分组。

2.4 回表的代价

对于下面的查询：

SELECT * FROM single_table WHERE key1 > 'a' AND key1 < 'c';

可以选择全表扫描，即直接扫描全部的聚簇索引记录；也可以使用索引idx_key1，根据搜索条件得到扫描区间，然后扫描二级索引记录，再执行回表操作。

对于使用InnoDB存储引擎的表来说，索引中的数据页会被存放到磁盘的一个或多个文件中，页面的页号对应着该页在磁盘文件中的偏移量（number * 16KB）。之前讲过，每一层的节点，双向链表连接起来的上一个节点和下一个节点可以不必相邻（InnoDB的设计使其尽量相邻）。
不过，即使相邻，在读取二级索引时，可能付出的代价较小，但相邻的二级索引对应的主键（id）并不连续，且这些聚簇索引记录可能分布在不同的数据页，页号也毫无规律。所以，在回表时，会造成大量的随机I/O。需要回表的次数越多，使用二级索引进行查询的性能也就越低。

一般情况下，可以给查询语句指定LIMIT子句来限制查询返回的记录数，这可能让查询优化器倾向于选择使用二级索引 回表的方式查询。

2.5 更好地创建和使用索引

1. 只为用于搜索、排序或分组的列创建索引
我们只为出现在WHERE子句中的列、连接子句中的连接列，或出现在ORDER BY、GROUP BY子句中的列创建索引。仅出现在查询列表中的列就没必要建立索引了。如：

SELECT common_field, key_part3 FROM single_table WHERE key1 = 'a';

查询列表中的common_field, key_part3这两个列就没必要创建索引。

2. 考虑索引列中不重复值的个数
我们在为某个列创建索引时，需要考虑该列中不重复值的个数占全部记录条数的比例。若比例太低，则说明该列包含过多重复值，那么在通过二级索引 回表方式执行查询时，就可能执行太多次回表操作。

3. 索引列的类型尽量小
因为数据类型越小，索引占用的存储空间就越少，在一个数据页中就可以存放更多的记录，读写效率也就越高。

4. 为列前缀创建索引
MySQL中使用utf-8字符集存储字符串的话，需要1-3个字节来编码一个字符。若字符串很长，在索引中占用的存储空间就会很大。

为列前缀创建索引——即只将字符串的前几个字符存放到索引中，比如修改idx_key1索引，使其只保留字符串的前10个字符：

ALTER TABLE single_table DROP INDEX idx_key1;
ALTER TABLE single_table ADD INDEX idx_key1(key1(10));

然后执行查询语句：

SELECT * FROM single_table WHERE key1 = 'ajfhkhkahfkahf';

我们只能定位到前缀为’ajfhkhkahf’的二级索引记录，在扫描这些二级索引记录的时候再判断它们是否满足key1 = 'ajfhkhkahfkahf’的条件。当列中存储的字符串包含的字符较多时，这种为列前缀建立索引的方式可以明显减少索引大小。

不过此时不能通过此索引对key1进行排序了，因为此索引不包含完整的key1列信息。

5. 覆盖索引
建议最好在查询列表中只包含索引列。查询和排序操作优先使用覆盖索引。
如：

SELECT * FROM single_table ORDER BY key1;

虽然这个查询语句中没有LIMIT子句，但是由于可以采用覆盖索引，所以查询优化器会直接使用idx_key1索引进行排序，而不需要执行回表操作

6. 让索引列以列名的形式在搜索条件中单独出现

SELECT * FROM s1 single_table WHERE key2 * 2 < 4;
SELECT * FROM s1 single_table WHERE key2 < 4/2;

第一个key2列不是以单独列名形式出现，第二个是。MySQL不会优化第一个语句，只能通过全表扫描的方式来执行。

7. 尽量使用自增类型主键

若插入记录的主键值是递增的话，则每插满一个数据页，就换到下一页继续插入。假设插入的主键值忽大忽小，在已经插满的数据页中再插入，则需要进行页分裂，造成性能损耗。像single_table表主键id列具有AUTO_INCREMENT属性。

8. 避免冗余和重复索引
联合索引的第一个索引列，本来就是按照此列排序，没必要再为此列单独建立索引；无需再为主键建立二级索引。

这篇好文章是转载于：学新通技术网