B+ 树索引

InnoDB 数据页有 7 个组成部分，各个数据页可以组成一个双向链表，而每个数据页中的记录会按照主键值从小到大的顺序组成一个单向链表，每个数据页都会为存储在它里边儿的记录生成一个页目录，在通过主键查找某条记录的时候可以在页目录中使用二分法快速定位到对应的槽，然后再遍历该槽对应分组中的记录即可快速找到指定的记录。

没有索引的查找

没有索引的时候是怎么查找记录的？比如：

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

在一个页中的查找

如果表中的记录比较少，所有的记录都可以被存放到一个页中，在查找记录的时候可以根据搜索条件的不同分为两种情况：

• 以主键为搜索条件

在页目录中使用二分法快速定位到对应的槽，然后再遍历该槽对应分组中的记录即可快速找到指定的记录。

• 以其他列作为搜索条件

对非主键列，数据页中并没有对非主键列建立所谓的页目录，所以无法通过二分法快速定位相应的槽。这种情况下只能从最小记录开始依次遍历单链表中的每条记录，然后对比每条记录是不是符合搜索条件。很显然，这种查找的效率是非常低的。

在很多页中查找

大部分情况下表中存放的记录都是非常多的，需要好多的数据页来存储这些记录。在很多页中查找记录的话可以分为两个步骤：

1. 定位到记录所在的页。
2. 从所在的页内中查找相应的记录。

由于并不能快速的定位到记录所在的页，所以只能从第一个页沿着双向链表一直往下找，每一个页中再使用上面一个页中的查找方法。非常低效。

索引

B+ 树

B+ 树是目前为止排序最有效率的数据结构。像二叉树，哈希索引、红黑树、SkipList，在海量数据基于磁盘存储效率方面远不如 B+ 树索引高效。

B+ 树索引的特点是： 基于磁盘的平衡树，但树非常矮，通常为 3~4 层，能存放千万到上亿的排序数据。树矮意味着访问效率高，从千万或上亿数据里查询一条数据，只需要 3、4 次 I/O。

B+ 树是 B 树的变种，主要区别：

• 非叶子节点不存储 data，只存储索引(冗余)，可以放更多的索引。B 树的非叶子节点也存储 data，会占用更多的磁盘空间，每个非叶子节点存储的记录远少于 B+ 树，这会导致树的高度变高，磁盘 I/O 次数变多，查询效率变低。
• 叶子节点包含所有索引字段。
• 叶子节点用指针连接，组成一个双向链表，提高区间访问的性能。B 树的叶子节点由于没有这个指针，一次只能访问一个节点，然后再从根节点开始遍历。

B 树的优势

B 树可以在非叶子节点同时存储键和值，因此，把频繁访问的数据放在靠近根节点的地方将会大大提高热点数据的查询效率。

为什么是 B+ 树

哈希表是一种以键-值（key-value）存储数据的结构，插入和查询都很快，但是适用于只有等值查询的场景，由于 key 是无序的，所以范围查询很慢。也不支持模糊查询。

有序数组在等值查询（二分法）和范围查询场景中的性能就都非常优秀。如果仅仅看查询效率，有序数组就是最好的数据结构了。但是，在需要更新数据的时候就麻烦了，你往中间插入一个记录就必须得挪动后面所有的记录，成本太高。

InnoDB 中的 B+ 树

在一个数据页中，Page Directory 通过二分法可以快速定位一条记录在页中的位置。

但是，在一个表中，可能有很多个数据页，如何快速的定位到需要查找的记录在哪些数据页中？

给所有的页建立目录项，目录项记录的 record_type 值是 1，而普通用户记录的 record_type 值是 0。

目录项记录只有主键值和页的编号两个列，而普通的用户记录的列是用户自己定义的，可能包含很多列，另外还有 InnoDB 自己添加的隐藏列。

上图中，如果用户记录的主键值在 [1, 320) 之间，则到页 30 中查找更详细的目录项记录，如果主键值不小于 320 的话，就到页 32 中查找更详细的目录项记录。

不论是存放用户记录的数据页，还是存放目录项记录的数据页，在 B+ 树这个数据结构中，都叫做节点。从图中可以看出来，实际的用户记录都存放在 B+ 树的最底层的节点上，这些节点也被称为叶子节点或叶节点，其余用来存放目录项的节点称为非叶子节点或者内节点，其中 B+ 树最上边的那个节点也称为根节点。

聚簇索引

1. 使用记录主键值的大小进行记录和页的排序
2. B+ 树的叶子节点存储完整的用户记录（记录中存储了所有列的值，包括隐藏列）。

具有这两种特性的 B+ 树称为聚簇索引，所有完整的用户记录都存放在这个聚簇索引的叶子节点处。这就是所谓的索引即数据，数据即索引。

二级索引

非主键列建立的 B+ 树需要一次回表操作才可以定位到完整的用户记录，所以这种 B+ 树也被称为二级索引（secondary index），或者辅助索引。

二级索引的叶子节点包含的用户记录由 索引列 + 主键 组成。

为什么二级索引的叶子节点只存储主键？

• 节省空间，如果所有的列都存储在二级索引的叶子节点中，那么二级索引的叶子节点就会非常大，占用的空间也会非常大。
• 一致性问题，如果二级索引的叶子节点中存储的是完整的用户记录，那么当用户记录发生变化时，所有二级索引的叶子节点也需要发生变化。

联合索引

联合索引，本质上也是一个二级索引。例如一个联合索引包含列 a 和 b：

B+ 树按照 a 和 b 列的大小进行排序：

• 先把各个记录和页按照 a 列进行排序。
• 在记录的 a 列相同的情况下，采用 b 列进行排序。

B+ 树索引的注意事项

一个 B+ 树索引的根节点自诞生之日起，便不会再移动。根节点一旦建立，它的页号便会被记录到某个地方，然后 InnoDB 存储引擎需要用到这个索引的时候，都会从那个固定的地方取出根节点的页号，从而来访问这个索引。

B+ 树的形成过程：

• 当为某个表创建一个 B+ 树索引时，都会为这个索引创建一个根节点页。最开始表中没有数据的时候，每个 B+ 树索引对应的根节点中既没有用户记录，也没有目录项记录。
• 随后向表中插入用户记录时，先把用户记录存储到这个根节点中。
• 当根节点中的可用空间用完时继续插入记录，此时会将根节点中的所有记录复制到一个新分配的页，比如 页 a 中，然后对这个新页进行页分裂的操作，得到另一个新页，比如 页 b。这时新插入的记录根据键值（也就是聚簇索引中的主键值，二级索引中对应的索引列的值）的大小就会被分配到 页 a 或者 页 b 中，而根节点升级为存储目录项记录的页。

B+ 树的同一层内节点的目录项记录除页号这个字段以外是唯一的。所以对于二级索引的内节点的目录项记录的内容实际上是由三个部分构成的：

• 索引列的值
• 主键值
• 页号

一个页面最少存储 2 条记录。

索引的代价

• 空间上的代价

每建立一个索引都要为它建立一棵 B+ 树，每一棵 B+ 树的每一个节点都是一个数据页，一个页默认会占用 16KB 的存储空间，一棵很大的 B+ 树会消耗很大的一片存储空间。

• 时间上的代价

每次对表中的数据进行增、删、改操作时，都需要去修改各个 B+ 树索引。B+ 树每层节点都是按照索引列的值从小到大的顺序排序而组成了双向链表。不论是叶子节点中的记录，还是非叶节点中的记录都是按照索引列的值从小到大的顺序而形成了一个单向链表。而增、删、改操作可能会对节点和记录的排序造成破坏，所以存储引擎需要额外的时间进行一些记录移位，页面分裂、页面回收等操作来维护好节点和记录的排序。

一个表上索引建的越多，就会占用越多的存储空间，在增删改记录的时候性能就越差。

索引的使用

B+ 树索引适用的条件

联合索引的各个排序列的排序顺序必须是一致的

CREATE TABLE person_info(
    id INT NOT NULL auto_increment,
    name VARCHAR(100) NOT NULL,
    birthday DATE NOT NULL,
    phone_number CHAR(11) NOT NULL,
    country varchar(100) NOT NULL,
    PRIMARY KEY (id),
    KEY idx_name_birthday_phone_number (name, birthday, phone_number)
);

二级索引 idx_name_birthday_phone_number，它是由 3 个列组成的联合索引。所以在这个索引对应的 B+ 树的叶子节点处存储的用户记录只保留 name、birthday、phone_number 这三个列的值以及主键 id 的值。

这个 idx_name_birthday_phone_number 索引对应的 B+ 树中页面和记录的排序方式就是这样的：

• 先按照 name 列的值进行排序。
• 如果 name 列的值相同，则按照 birthday 列的值进行排序。
• 如果 birthday 列的值也相同，则按照 phone_number 的值进行排序。

这个排序方式非常重要，因为只要页面和记录是排好序的，就可以通过二分法来快速定位查找。

全值匹配

当查询条件中的列与索引中的列完全匹配，并且全部使用等值比较（=）时，称为全值匹配。这种情况下，MySQL 可以最有效地利用索引。

SELECT * FROM person_info WHERE name = 'Ashburn' AND birthday = '1990-09-27' AND phone_number = '15123983239';

idx_name_birthday_phone_number 索引包含的 3 个列，查询过程：

1. B+ 树的数据页和记录是先按照 name 列的值进行排序的，可以先按照 name 列来查找。
2. name 列相同的记录又是按照 birthday 进行排序的，可以继续按照 birthday 来查找。
3. 如果 name 和 birthday 都是相同的，会按照 phone_number 列的值排序。

name、birthday、phone_number 这几个搜索列的顺序对查询结果没有影响，因为优化器可以优化语句。

匹配左边的列

SELECT * FROM person_info WHERE name = 'Ashburn';

SELECT * FROM person_info WHERE name = 'Ashburn' AND birthday = '1990-09-27';

没有包含全部联合索引的列，只要包含左边的一列或者多列，也可以使用索引。

因为 B+ 树的联合索引按照索引从左到右的顺序排序的。

如果想使用联合索引中尽可能多的列，搜索条件中的各个列必须是联合索引中从最左边连续的列。

匹配列前缀

字符串排序的本质就是比较哪个字符串大一点儿，哪个字符串小一点，比较字符串大小就用到了该列的字符集和比较规则。

比较两个字符串的大小的过程其实是这样的：

• 先比较字符串的第一个字符，第一个字符小的那个字符串就比较小。
• 如果两个字符串的第一个字符相同，那就再比较第二个字符，第二个字符比较小的那个字符串就比较小。
• 如果两个字符串的第二个字符也相同，那就接着比较第三个字符，依此类推。

所以一个排好序的字符串列其实有这样的特点：

• 先按照字符串的第一个字符进行排序。
• 如果第一个字符相同再按照第二个字符进行排序。
• 如果第二个字符相同再按照第三个字符进行排序，依此类推。

也就是说这些字符串的前 n 个字符，也就是前缀都是排好序的，所以对于字符串类型的索引列来说，我们只匹配它的前缀也是可以快速定位记录的，比方说我们想查询名字以’As’开头的记录，那就可以这么写查询语句：

SELECT * FROM person_info WHERE name LIKE 'As%';

但是如果只给出后缀或者中间某个字符串，如 %As%，就没办法利用索引了。

匹配范围值

所有记录都是按照索引列的值从小到大的顺序排好序的，所以查找某个范围的值的记录是很简单的。

SELECT * FROM person_info WHERE name > 'Asa' AND name < 'Barlow';

记录是先按 name 列排序的，所以我们上边的查询过程其实是这样的：

• 找到 name 值为 Asa 的记录。
• 找到 name 值为 Barlow 的记录。
• 由于所有记录都是由链表连起来的（记录之间用单链表，数据页之间用双链表），所以他们之间的记录都可以很容易的取出来。
• 找到这些记录的主键值，再到聚簇索引中回表查找完整的记录。

如果对多个列同时进行范围查找的话，只有对索引最左边的那个列进行范围查找的时候才能用到 B+ 树索引。

SELECT * FROM person_info WHERE name > 'Asa' AND name < 'Barlow' AND birthday > '1980-01-01';

查询可以分成两个部分：

1. 通过条件 name > 'Asa' AND name < 'Barlow' 来对 name 进行范围查找，查找的结果可能有多条 name 值不同的记录，
2. 对这些 name 值不同的记录继续通过 birthday > '1980-01-01' 条件继续过滤。

精确匹配某一列并范围匹配另外一列

对于同一个联合索引来说，虽然对多个列都进行范围查找时只能用到最左边那个索引列，但是如果左边的列是精确查找，则右边的列可以进行范围查找，比方说这样：

SELECT * FROM person_info WHERE name = 'Ashburn' AND birthday > '1980-01-01' AND birthday < '2000-12-31' AND phone_number > '15100000000';

name = 'Ashburn'，对 name 列进行精确查找，使用 B+ 树索引。

birthday > '1980-01-01' AND birthday < '2000-12-31'，由于 name 列是精确查找，所以通过 name = 'Ashburn'条件查找后得到的结果的 name 值都是相同的，它们会再按照 birthday 的值进行排序。所以此时对 birthday 列进行范围查找是可以用到 B+ 树索引的。

phone_number > '15100000000'，通过 birthday 的范围查找的记录的 birthday 的值可能不同，所以这个条件无法再利用 B+ 树索引了，只能遍历上一步查询得到的记录。

用于排序

一般情况下，我们只能把记录都加载到内存中，再用一些排序算法，比如快速排序、归并排序、吧啦吧啦排序等等在内存中对这些记录进行排序，有的时候可能查询的结果集太大以至于不能在内存中进行排序的话，还可能暂时借助磁盘的空间来存放中间结果，排序操作完成后再把排好序的结果集返回到客户端。在 MySQL 中，把这种在内存中或者磁盘上进行排序的方式统称为文件排序。

如果 ORDER BY 子句里使用到了我们的索引列，就有可能省去在内存或文件中排序的步骤，比如下边这个简单的查询语句：

SELECT * FROM person_info ORDER BY name, birthday, phone_number LIMIT 10;

这个查询的结果集需要先按照 name 值排序，如果记录的 name 值相同，则需要按照 birthday 来排序，如果 birthday 的值相同，则需要按照 phone_number 排序。大家可以回过头去看我们建立的 idx_name_birthday_phone_number 索引的示意图，因为这个 B+ 树索引本身就是按照上述规则排好序的，所以直接从索引中提取数据，然后进行回表操作取出该索引中不包含的列就好了。

注意，ORDER BY 的子句后边的列的顺序也必须按照索引列的顺序给出，如果给出 ORDER BY phone_number, birthday, name 的顺序，那也是用不了 B+ 树索引

同理，ORDER BY name、ORDER BY name, birthday 这种匹配索引左边的列的形式可以使用部分的 B+ 树索引。当联合索引左边列的值为常量，也可以使用后边的列进行排序

SELECT * FROM person_info WHERE name = 'A' ORDER BY birthday, phone_number LIMIT 10;

不可以使用索引进行排序:

• ASC、DESC 混用
• 排序列包含非同一个索引的列
• 排序列使用了复杂的表达式 SELECT * FROM person_info ORDER BY UPPER(name) LIMIT 10;

用于分组

SELECT name, birthday, phone_number, COUNT(*) FROM person_info GROUP BY name, birthday, phone_number

先把记录按照 name 值进行分组，所有 name 值相同的记录划分为一组。

将每个 name 值相同的分组里的记录再按照 birthday 的值进行分组，将 birthday 值相同的记录放到一个小分组里，所以看起来就像在一个大分组里又化分了好多小分组。

再将上一步中产生的小分组按照 phone_number 的值分成更小的分组，所以整体上看起来就像是先把记录分成一个大分组，然后把大分组分成若干个小分组，然后把若干个小分组再细分成更多的小小分组。

如果没有索引的话，这个分组过程全部需要在内存里实现，而如果有了索引的话，恰巧这个分组顺序又和我们的 B+ 树中的索引列的顺序是一致的，而我们的 B+ 树索引又是按照索引列排好序的，这不正好么，所以可以直接使用 B+ 树索引进行分组。

回表的代价

idx_name_birthday_phone_number 索引为例

SELECT * FROM person_info WHERE name > 'Asa' AND name < 'Barlow';

索引 idx_name_birthday_phone_number 对应的 B+ 树用户记录中只包含 name、birthday、phone_number、id 这 4 个字段，而查询列表是 *，意味着要查询表中所有字段。这时需要把从上一步中获取到的每一条记录的 id 字段都到聚簇索引对应的 B+ 树中找到完整的用户记录，也就是我们通常所说的回表，然后把完整的用户记录返回给查询用户。

顺序 I/O

索引 idx_name_birthday_phone_number 对应的 B+ 树中的记录首先会按照 name 列的值进行排序，所以值在 Asa～Barlow 之间的记录在磁盘中的存储是相连的，集中分布在一个或几个数据页中，我们可以很快的把这些连着的记录从磁盘中读出来，这种读取方式我们也可以称为顺序 I/O

随机 I/O

根据第 1 步中获取到的记录的 id 字段的值可能并不相连，而在聚簇索引中记录是根据 id（也就是主键）的顺序排列的，所以根据这些并不连续的 id 值到聚簇索引中访问完整的用户记录可能分布在不同的数据页中，这样读取完整的用户记录可能要访问更多的数据页，这种读取方式我们也可以称为随机 I/O

顺序 I/O 比随机 I/O 的性能高很多。

需要回表的记录越多，使用二级索引的性能就越低。某些查询宁愿使用全表扫描也不使用二级索引。比方说 name 值在 Asa~Barlow 之间的用户记录数量占全部记录数量 90% 以上，那么如果使用 idx_name_birthday_phone_number 索引的话，有 90% 多的 id 值需要回表，这不是吃力不讨好么，还不如直接去扫描聚簇索引（也就是全表扫描）。

查询优化器会事先对表中的记录计算一些统计数据，然后再利用这些统计数据根据查询的条件来计算一下需要回表的记录数，需要回表的记录数越多，就越倾向于使用全表扫描，反之倾向于使用 二级索引 + 回表 的方式。

回表的记录特别少，优化器就会倾向于使用 二级索引 + 回表 的方式执行查询。

覆盖索引

为了彻底告别回表操作带来的性能损耗：最好在查询列表里只包含索引列

SELECT name, birthday, phone_number FROM person_info WHERE name > 'Asa' AND name < 'Barlow'

只查询 name, birthday, phone_number 这三个索引列的值，所以在通过 idx_name_birthday_phone_number 索引得到结果后就不必到聚簇索引中再查找记录的剩余列，这样就省去了回表操作带来的性能损耗。

不鼓励用 * 号作为查询列表，最好把我们需要查询的列依次标明。

索引下推

什么是索引下推（Index Condition Pushdown，ICP）？

索引下推是一种在存储引擎层提前过滤不符合条件的记录的优化手段。没有 ICP 的时候，索引只用来定位数据行的位置，具体 WHERE 条件由 Server 层来判断。即使部分索引已能判断，仍需回表取数据。有 ICP 的时候 InnoDB 在扫描索引时，就会尽量利用 WHERE 子句中的条件直接过滤数据，不必回表就能丢掉无效行，减少回表的次数。

没有使用 ICP 的情况下，MySQL 的查询：

1. 存储引擎读取索引记录；
2. 根据索引中的主键值，定位并读取完整的行记录；
3. 存储引擎把记录交给 Server 层去检测该记录是否满足 WHERE 条件。

使用 ICP 的情况下，查询过程：

1. 存储引擎读取索引记录（不是完整的行记录）；
2. 判断 WHERE 条件部分能否用索引中的列来做检查，条件不满足，则处理下一行索引记录；
3. 条件满足，使用索引中的主键去定位并读取完整的行记录（回表）；
4. 存储引擎把记录交给 Server 层，Server 层检测该记录是否满足 WHERE 条件的其余部分。

-- 联合索引 (name,age,position)
SELECT * FROM employees WHERE name like 'LiLei%' AND age = 22 AND position ='manager';

在 MySQL 5.6 之前的版本没有 ICP，这个查询只能在联合索引里匹配到名字是 'LiLei' 开头的索引，然后拿这些索引对应的主键逐个回表，到主键索引上找出相应的记录，服务器层再根据 age 和 position 的过滤条件进行筛选。这种情况只会走 name 字段索引，无法很好的利用索引。

MySQL 5.6 引入了索引下推优化 ICP，上面那个查询在联合索引里匹配到名字是 'LiLei' 开头的索引之后，同时还会在索引里过滤 age 和 position 这两个字段，拿着过滤完剩下的索引对应的主键 id 再回表查整行数据。

为什么范围查找 MySQL 没有用索引下推优化？

可能是 MySQL 认为索引下推需要额外的判断，范围查找过滤的结果集过大，会导致更多的计算，like KK% 在绝大多数情况来看，过滤后的结果集比较小，所以这里 MySQL 选择给 like KK% 用了索引下推优化，当然这也不是绝对的，有时 like KK% 也不一定就会走索引下推。

索引下推的使用条件

• 索引下推优化只对联合索引生效。索引下推的目的是为了减少回表次数，也就是要减少 IO 操作。对聚簇索引来说，数据和索引是在一起的，不存在回表这一说。
• 索引下推优化只对 InnoDB 存储引擎生效。

百万级别或以上的数据如何删除

删除数据的速度和创建的索引数量是成正比的。百万级别的数据删除速度也会很慢。最快的方案是删除重建索引。

1. 想要删除百万数据的时候可以先删除索引。
2. 然后删除其中无用数据。
3. 删除完成后重新创建索引(此时数据较少了)创建索引也非常快。
4. 与之前的直接删除绝对是要快速很多，更别说万一删除中断,一切删除会回滚。那更是坑了。