数据库索引 | Decade

索引是加速数据库查询操作的数据结构，类似于书本的目录。合理使用索引能显著提升查询效率，但也可能带来写入性能下降和存储空间增加的问题。MySQL 默认使用 B+ 树作为主要索引结构，因其高效的范围查询和有序性而广泛应用，此外还有哈希索引、全文索引等多种结构，分别适用于不同的使用场景。

1. 为什么使用索引

索引是存储引擎用于快速找到数据记录的一种数据结构，就好比一本教科书的目录部分，通过目录中找到对应文章的页码，便可快速定位到需要的文章。MySQL 中也是一样的道理，进行数据查找时，首先查看查询条件是否命中某条索引，符合则通过索引查找相关数据，如果不符合则需要全表扫描，即需要一条一条地查找记录，直到找到与条件符合的记录。

如上图所示，数据库没有索引的情况下，数据分布在硬盘不同的位置上面，读取数据时，摆臂需要前后摆动查询数据，这样操作非常消耗时间。如果数据顺序摆放，那么也需要从 1 到 6 行按顺序读取，这样就相当于进行了 6 次 IO 操作，依旧非常耗时。如果我们不借助任何索引结构帮助我们快速定位数据的话，我们查找 Col 2 = 89 这条记录，就要逐行去查找、去比较。从 Col 2 = 34 开始，进行比较，发现不是，继续下一行。我们当前的表只有不到 10 行数据，但如果表很大的话，有上千万条数据，就意味着要做很多很多次硬盘I/0才能找到。现在要查找 Col 2 = 89 这条记录。CPU 必须先去磁盘查找这条记录，找到之后加载到内存，再对数据进行处理。这个过程最耗时间就是磁盘 I/O（涉及到磁盘的旋转时间（速度较快），磁头的寻道时间(速度慢、费时)）

假如给数据使用 二叉树 这样的数据结构进行存储，如下图所示

对字段 Col 2 添加了索引，就相当于在硬盘上为 Col 2 维护了一个索引的数据结构，即这个 二叉搜索树。二叉搜索树的每个结点存储的是 (K, V) 结构，key 是 Col 2，value 是该 key 所在行的文件指针（地址）。比如：该二叉搜索树的根节点就是：(34, 0x07)。现在对 Col 2 添加了索引，这时再去查找 Col 2 = 89 这条记录的时候会先去查找该二叉搜索树（二叉树的遍历查找）。读 34 到内存，89 > 34; 继续右侧数据，读 89 到内存，89==89；找到数据返回。找到之后就根据当前结点的 value 快速定位到要查找的记录对应的地址。我们可以发现，只需要 查找两次 就可以定位到记录的地址，查询速度就提高了。

这就是我们为什么要建索引，目的就是为了 减少磁盘I/O的次数，加快查询速率。

2. 索引及其优缺点

2.1 索引概述

MySQL 官方对索引的定义为：索引（Index）是帮助 MySQL 高效获取数据的数据结构。

索引的本质：索引是数据结构。你可以简单理解为“排好序的快速查找数据结构”，满足特定查找算法。这些数据结构以某种方式指向数据，这样就可以在这些数据结构的基础上实现 高级查找算法 。

索引是在存储引擎中实现的，因此每种存储引擎的索引不一定完全相同，并且每种存储引擎不一定支持所有索引类型。同时，存储引擎可以定义每个表的 最大索引数和 最大索引长度。所有存储引擎支持每个表至多 16 个索引，总索引长度至多为 256 字节。有些存储引擎支持更多的索引数和更大的索引长度。

2.2 优点

（1）类似大学图书馆建书目索引，提高数据检索的效率，降低 数据库的 IO 成本 ，这也是创建索引最主要的原因。

（2）通过创建唯一索引，可以保证数据库表中每一行 数据的唯一性 。

（3）在实现数据的参考完整性方面，可以 加速表和表之间的连接 。换句话说，对于有依赖关系的子表和父表联合查询时，可以提高查询速度。

（4）在使用分组和排序子句进行数据查询时，可以显著 减少查询中分组和排序的时间 ，降低了 CPU 的消耗。

2.3 缺点

增加索引也有许多不利的方面，主要表现在如下几个方面：

（1）创建索引和维护索引要 耗费时间 ，并且随着数据量的增加，所耗费的时间也会增加。

（2）索引需要占 磁盘空间 ，除了数据表占数据空间之外，每一个索引还要占一定的物理空间，存储在磁盘上，如果有大量的索引，索引文件就可能比数据文件更快达到最大文件尺寸。

（3）虽然索引大大提高了查询速度，同时却会 降低更新表的速度 。当对表中的数据进行增加、删除和修改的时候，索引也要动态地维护，这样就降低了数据的维护速度。因此，选择使用索引时，需要综合考虑索引的优点和缺点。

因此，选择使用索引时，需要综合考虑索引的优点和缺点。

提示：

索引可以提高查询的速度，但是会影响插入记录的速度。这种情况下，最好的办法是先删除表中的索引，然后插入数据，插入完成后再创建索引。

3. InnoDB 中索引的推演

3.1 索引之前的查找

先来看一个精确匹配的例子：

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

1. 在一个页中的查找

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

以主键为搜索条件

可以在页目录中使用 二分法 快速定位到对应的槽，然后再遍历该槽对用分组中的记录即可快速找到指定记录。
以其他列作为搜索条件

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

2. 在很多页中查找

在很多页中查找记录的活动可以分为两个步骤：

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

在没有索引的情况下，不论是根据主键列或者其他列的值进行查找，由于我们并不能快速的定位到记录所在的页，所以只能从第一个页沿着双向链表一直往下找，在每一个页中根据我们上面的查找方式去查找指定的记录。因为要遍历所有的数据页，所以这种方式显然是超级耗时的。如果一个表有一亿条记录呢？此时索引应运而生。

3.2 设计索引

建一个表：

mysql> CREATE TABLE index_demo(
-> c1 INT,
-> c2 INT,
-> c3 CHAR(1),
-> PRIMARY KEY(c1)
-> ) ROW_FORMAT = Compact;

这个新建的 index_demo 表中有 2 个 INT 类型的列，1 个 CHAR(1)类型的列，而且我们规定了 c1 列为主键，这个表使用 Compact 行格式来实际存储记录的。这里我们简化了 index_demo 表的行格式示意图：

我们只在示意图里展示记录的这几个部分：

record_type ：记录头信息的一项属性，表示记录的类型， 0 表示普通记录、 2 表示最小记录、 3 表示最大记录、 1 暂时还用不着，下面讲。
next_record ：记录头信息的一项属性，表示下一条地址相对于本条记录的地址偏移量，我们用箭头来表明下一条记录是谁。
各个列的值：这里只记录在 index_demo 表中的三个列，分别是 c1 、 c2 和 c3 。
其他信息：除了上述 3 种信息以外的所有信息，包括其他隐藏列的值以及记录的额外信息。

将记录格式示意图的其他信息项暂时去掉并把它竖起来的效果就是这样：

把一些记录放到页里的示意图就是：

1. 一个简单的索引设计方案

我们在根据某个搜索条件查找一些记录时为什么要遍历所有的数据页呢？因为各个页中的记录并没有规律，我们并不知道我们的搜索条件匹配哪些页中的记录，所以不得不依次遍历所有的数据页。所以如果我们 想快速的定位到需要查找的记录在哪些数据页 中该咋办？我们可以为快速定位记录所在的数据页而建立一个目录，建这个目录必须完成下边这些事：

下一个数据页中用户记录的主键值必须大于上一个页中用户记录的主键值。

假设：每个数据结构最多能存放 3 条记录（实际上一个数据页非常大，可以存放下好多记录）。
1
INSERT INTO index_demo VALUES(1, 4, 'u'), (3, 9, 'd'), (5, 3, 'y');
那么这些记录以及按照主键值的大小串联成一个单向链表了，如图所示：

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

因为 页 10 最多只能放 3 条记录，所以我们不得不再分配一个新页：

注意：新分配的 数据页编号可能并不是连续的。它们只是通过维护者上一个页和下一个页的编号而建立了链表关系。另外，页 10中用户记录最大的主键值是 5，而页 28中有一条记录的主键值是 4，因为 5>4，所以这就不符合下一个数据页中用户记录的主键值必须大于上一个页中用户记录的主键值的要求，所以在插入主键值为 4 的记录的时候需要伴随着一次 记录移动，也就是把主键值为 5 的记录移动到页 28 中，然后再把主键值为 4 的记录插入到页 10 中。

这个过程表明了在对页中的记录进行增删改查操作的过程中，我们必须通过一些诸如 记录移动 的操作来始终保证这个状态一直成立：下一个数据页中用户记录的主键值必须大于上一个页中用户记录的主键值。这个过程称为 页分裂。

由于数据页的 编号可能是不连续 的，所以在向 index_demo 表中插入许多条记录后，可能是这样的效果：

我们需要给它们做个目录，每个页对应一个目录项，每个目录项包括下边两个部分：

1）页的用户记录中最小的主键值，我们用 key 来表示。

2）页号，我们用 page_on 表示。

以页 28 为例，它对应目录项 2 ，这个目录项中包含着该页的页号 28 以及该页中用户记录的最小主键值 5 。我们只需要把几个目录项在物理存储器上连续存储（比如：数组），就可以实现根据主键值快速查找某条记录的功能了。比如：查找主键值为 20 的记录，具体查找过程分两步：

先从目录项中根据二分法快速确定出主键值为 20 的记录在目录项 3 中（因为 12 < 20 < 209 ），它对应的页是页 9 。
再根据前边说的在页中查找记录的方式去页 9 中定位具体的记录。

至此，针对数据页做的简易目录就搞定了。这个目录有一个别名，称为索引。

2. InnoDB 中的索引方案

① 迭代 1 次：目录项纪录的页

InnoDB 怎么区分一条记录是普通的 用户记录 还是 目录项记录 呢？使用记录头信息里的 record_type 属性，它的各自取值代表的意思如下：

0：普通的用户记录
1：目录项记录
2：最小记录
3：最大记录

我们把前边使用到的目录项放到数据页中的样子就是这样：

从图中可以看出来，我们新分配了一个编号为 30 的页来专门存储目录项记录。这里再次强调 目录项记录 和普通的 用户记录 的不同点：

目录项记录 的 record_type 值是 1，而 普通用户记录 的 record_type 值是 0。
目录项记录只有 主键值和页的编号 两个列，而普通的用户记录的列是用户自己定义的，可能包含 很多列 ，另外还有 InnoDB 自己添加的隐藏列。
了解：记录头信息里还有一个叫 min_rec_mask 的属性，只有在存储 目录项记录 的页中的主键值最小的 目录项记录 的 min_rec_mask 值为 1 ，其他别的记录的 min_rec_mask 值都是 0 。

相同点：两者用的是一样的数据页，都会为主键值生成 Page Directory （页目录），从而在按照主键值进行查找时可以使用 二分法 来加快查询速度。

原始页中数据是链表存储，不好随机访问。

页目录相当于一个数组，支持随机访问，方便二分。

现在以查找主键为 20 的记录为例，根据某个主键值去查找记录的步骤就可以大致拆分成下边两步：

先到存储目录项记录的页，也就是页 30 中通过二分法快速定位到对应目录项，因为 12 < 20 < 209 ，所以定位到对应的记录所在的页就是页 9。
再到存储用户记录的页 9 中根据二分法快速定位到主键值为 20 的用户记录。

② 迭代 2 次：多个目录项纪录的页

从图中可以看出，我们插入了一条主键值为 320 的用户记录之后需要两个新的数据页：

为存储该用户记录而新生成了页 31 。
因为原先存储目录项记录的页 30 的容量已满（我们前边假设只能存储 4 条目录项记录），所以不得不需要一个新的页 32 来存放页 31 对应的目录项。

现在因为存储目录项记录的页不止一个，所以如果我们想根据主键值查找一条用户记录大致需要 3 个步骤，以查找主键值为 20 的记录为例：

确定目录项记录页我们现在的存储目录项记录的页有两个，即页 30 和页 32 ，又因为页 30 表示的目录项的主键值的范围是 [1, 320) ，页 32 表示的目录项的主键值不小于 320 ，所以主键值为 20 的记录对应的目录项记录在页 30 中。
通过目录项记录页确定用户记录真实所在的页。在一个存储目录项记录的页中通过主键值定位一条目录项记录的方式说过了。
在真实存储用户记录的页中定位到具体的记录。

如果我们表中的数据非常多则会产生很多存储目录项记录的页，那我们怎么根据主键值快速定位一个存储目录项记录的页呢？那就为这些存储目录项记录的页再生成一个更高级的目录，就像是一个多级目录一样，大目录里嵌套小目录，小目录里才是实际的数据，所以现在各个页的示意图就是这样子：

如图，我们生成了一个存储更高级目录项的页 33 ，这个页中的两条记录分别代表页 30 和页 32，如果用户记录的主键值在 [1, 320) 之间，则到页 30 中查找更详细的目录项记录，如果主键值不小于 320 的话，就到页 32 中查找更详细的目录项记录。

我们可以用下边这个图来描述它：

这个数据结构，它的名称是 B+树。

④ B+Tree

一个 B+树的节点其实可以分成好多层，规定最下边的那层，也就是存放我们用户记录的那层为第 0 层，之后依次往上加。之前我们做了一个非常极端的假设：存放用户记录的页最多存放 3 条记录，存放目录项记录的页最多存放 4 条记录。其实真实环境中一个页存放的记录数量是非常大的，假设所有存放用户记录的叶子节点代表的数据页可以存放 100 条用户记录，所有存放目录项记录的内节点代表的数据页可以存放 1000 条目录项记录，那么：

如果 B+树只有 1 层，也就是只有 1 个用于存放用户记录的节点，最多能存放 100 条记录。
如果 B+树有 2 层，最多能存放 1000×100=10,0000 条记录。
如果 B+树有 3 层，最多能存放 1000×1000×100=1,0000,0000 条记录。
如果 B+树有 4 层，最多能存放 1000×1000×1000×100=1000,0000,0000 条记录。相当多的记录！

你的表里能存放 100000000000 条记录吗？所以一般情况下，我们用到的 B+树都不会超过 4 层 ，那我们通过主键值去查找某条记录最多只需要做 4 个页面内的查找（查找 3 个目录项页和一个用户记录页），又因为在每个页面内有所谓的 Page Directory （页目录），所以在页面内也可以通过 二分法 实现快速定位记录。

3.3 常见索引概念

索引按照物理实现方式，索引可以分为 2 种：聚簇（聚集）和非聚簇（非聚集）索引。我们也把非聚集索引称为二级索引或者辅助索引。

1. 聚簇索引

聚簇索引并不是一种单独的索引类型，而是一种数据存储方式（所有的用户记录都存储在了叶子结点），也就是所谓的 索引即数据，数据即索引。

术语”聚簇”表示当前数据行和相邻的键值聚簇的存储在一起

特点：

使用记录主键值的大小进行记录和页的排序，这包括三个方面的含义：
- 页内 的记录是按照主键的大小顺序排成一个 单向链表 。
- 各个存放用户记录的页也是根据页中用户记录的主键大小顺序排成一个双向链表 。
- 存放 目录项记录的页 分为不同的层次，在同一层次中的页也是根据页中目录项记录的主键大小顺序排成一个 双向链表 。
B+树的叶子节点存储的是完整的用户记录。

所谓完整的用户记录，就是指这个记录中存储了所有列的值（包括隐藏列）。

我们把具有这两种特性的 B+树称为聚簇索引，所有完整的用户记录都存放在这个聚簇索引的叶子节点处。这种聚簇索引并不需要我们在 MySQL 语句中显式的使用 INDEX 语句去创建，InnDB 存储引擎会 自动 的为我们创建聚簇索引。

优点：

数据访问更快，因为聚簇索引将索引和数据保存在同一个 B+树中，因此从聚簇索引中获取数据比非聚簇索引更快
聚簇索引对于主键的 排序查找 和 范围查找 速度非常快
按照聚簇索引排列顺序，查询显示一定范围数据的时候，由于数据都是紧密相连，数据库不用从多个数据块中提取数据，所以 节省了大量的io操作 。

缺点：

插入速度严重依赖于插入顺序 ，按照主键的顺序插入是最快的方式，否则将会出现页分裂，严重影响性能。因此，对于 InnoDB 表，我们一般都会定义一个自增的ID列为主键
更新主键的代价很高 ，因为将会导致被更新的行移动。因此，对于 InnoDB 表，我们一般定义主键为不可更新
二级索引访问需要两次索引查找 ，第一次找到主键值，第二次根据主键值找到行数据

限制:

对于 MySQL 数据库目前只有 InnoDB 数据引擎支持聚簇索引, 而 MyISAM 并不支持聚簇索引。
由于数据物理存储排序方式只能有一种，所以每个 MySQL 的表只能有一个聚簇索引。一般情况下就是该表的主键。
如果没有定义主键，Innodb 会选择非空的唯一索引代替。如果没有这样的索引，Innodb 会隐式的定义一个主键来作为聚簇索引。
为了充分利用聚簇索引的聚簇的特性，所以 innodb 表的主键列尽量选用有序的顺序 id，而不建议用无序的 id，比如 UUID、MD5、HASH、字符串列作为主键无法保证数据的顺序增长。

2. 二级索引（辅助索引、非聚簇索引）

如果我们想以别的列作为搜索条件该怎么办？肯定不能是从头到尾沿着链表依次遍历记录一遍。

答案：我们可以多建几颗B+树，不同的 B+树中的数据采用不同的排列规则。比方说我们用c2列的大小作为数据页、页中记录的排序规则，再建一课 B+树。

这个 B+树与上边介绍的聚簇索引有几处不同：

使用记录 c2 列的大小进行记录和页的排序，这包括三个方面的含义：
- 页内的记录是按照 c2 列的大小顺序排成一个单向链表。
- 各个存放用户记录的页也是根据页中记录的 c2 列大小顺序排成一个双向链表。
- 存放目录项记录的页分为不同的层次，在同一层次中的页也是根据页中目录项记录的 c2 列大小顺序排成一个双向链表。
B+树的叶子节点存储的并不是完整的用户记录，而只是 c2 列+主键(c1 列)这两个列的值。
目录项记录中不再是主键+页号的搭配，而变成了 c2 列+页号的搭配。

我们根据这个以 c2 列大小排序的 B+树只能确定我们要查找记录的主键值，所以如果我们想根据 c2 列的值查找到完整的用户记录的话，仍然需要到主键构成的聚簇索引中再查一遍，这个过程称为回表。也就是根据 c2 列的值查询一条完整的用户记录需要使用到 2 棵 B+树！

问题：为什么我们还需要一次回表操作呢？直接把完整的用户记录放到叶子节点不 OK 吗？

回答：如果把完整的用户记录放到叶子结点是可以不用回表。但是太占地方了，相当于每建立一课 B+树都需要把所有的用户记录再都拷贝一遍，这就有点太浪费存储空间了。

因为这种按照非主键列建立的 B+树需要一次回表操作才可以定位到完整的用户记录，所以这种 B+树也被称为二级索引，或者辅助索引。由于使用的是 c2 列的大小作为 B+树的排序规则，所以我们也称这个 B+树为 c2 列的索引。

非聚簇索引的存在不影响数据在聚簇索引中的组织，所以一张表可以有多个非聚簇索引。

小结：聚簇索引与非聚簇索引的原理不同，在使用上也有一些区别：

聚簇索引的叶子节点存储的就是我们的数据记录, 非聚簇索引的叶子节点存储的是数据位置。非聚簇索引不会影响数据表的物理存储顺序。
一个表只能有一个聚簇索引，因为只能有一种排序存储的方式，但可以有多个非聚簇索引，也就是多个索引目录提供数据检索。
使用聚簇索引的时候，数据的查询效率高，但如果对数据进行插入，删除，更新等操作，效率会比非聚簇索引低。

3.联合索引

我们也可以同时以多个列的大小作为排序规则，也就是同时为多个列建立索引，比方说我们想让 B+树按照 c2 和 c3 列的大小进行排序，这个包含两层含义：

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

如图所示，我们需要注意以下几点：

每条目录项都有 c2、c3、页号这三个部分组成，各条记录先按照 c2 列的值进行排序，如果记录的 c2 列相同，则按照 c3 列的值进行排序
B+树叶子节点处的用户记录由 c2、c3 和主键 c1 列组成

注意一点，以 c2 和 c3 列的大小为排序规则建立的 B+树称为联合索引，本质上也是一个二级索引。它的意思与分别为 c2 和 c3 列分别建立索引的表述是不同的，不同点如下：

建立联合索引只会建立如上图一样的 1 棵 B+树。
为 c2 和 c3 列分别建立索引会分别以 c2 和 c3 列的大小为排序规则建立 2 棵 B+树。

3.4 InnoDB 的 B+树索引的注意事项

1. 根页面位置万年不动

实际上 B+树的形成过程是这样的：

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

这个过程特别注意的是：一个 B+树索引的根节点自诞生之日起，便不会再移动。这样只要我们对某个表建议一个索引，那么它的根节点的页号便会被记录到某个地方。然后凡是 InnoDB 存储引擎需要用到这个索引的时候，都会从哪个固定的地方取出根节点的页号，从而来访问这个索引。

2. 内节点中目录项记录的唯一性

我们知道 B+树索引的内节点中目录项记录的内容是 索引列 + 页号 的搭配，但是这个搭配对于二级索引来说有点不严谨。还拿 index_demo 表为例，假设这个表中的数据是这样的：

如果二级索引中目录项记录的内容只是 索引列 + 页号 的搭配的话，那么为 c2 列简历索引后的 B+树应该长这样：

如果我们想新插入一行记录，其中 c1 、c2 、c3 的值分别是: 9、1、c, 那么在修改这个为 c2 列建立的二级索引对应的 B+ 树时便碰到了个大问题：由于 页3 中存储的目录项记录是由 c2列 + 页号 的值构成的，页3 中的两条目录项记录对应的 c2 列的值都是 1，而我们 新插入的这条记录 的 c2 列的值也是 1，那我们这条新插入的记录到底应该放在 页4 中，还是应该放在 页5 中？答案：对不起，懵了

为了让新插入记录找到自己在那个页面，我们需要保证在 B+树的同一层页节点的目录项记录除页号这个字段以外是唯一的。所以对于二级索引的内节点的目录项记录的内容实际上是由三个部分构成的：

索引列的值
主键值
页号

也就是我们把主键值也添加到二级索引内节点中的目录项记录，这样就能保住 B+ 树每一层节点中各条目录项记录除页号这个字段外是唯一的。

这样我们再插入记录(9, 1, 'c') 时，由于 页3 中存储的目录项记录是由 c2列 + 主键 + 页号 的值构成的，可以先把新纪录的 c2 列的值和 页3 中各目录项记录的 c2 列的值作比较，如果 c2 列的值相同的话，可以接着比较主键值，因为 B+树同一层中不同目录项记录的 c2列 + 主键的值肯定是不一样的，所以最后肯定能定位唯一的一条目录项记录，在本例中最后确定新纪录应该被插入到 页5 中。

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

一个 B+树只需要很少的层级就可以轻松存储数亿条记录，查询速度相当不错！这是因为 B+树本质上就是一个大的多层级目录，每经过一个目录时都会过滤掉许多无效的子目录，直到最后访问到存储真实数据的目录。那如果一个大的目录中只存放一个子目录是个啥效果呢？那就是目录层级非常非常多，而且最后的那个存放真实数据的目录中只存放一条数据。所以 InnoDB 的一个数据页至少可以存放两条记录。

4. MyISAM 中的索引方案

B 树索引使用存储引擎如表所示：

索引 / 存储引擎	MyISAM	InnoDB	Memory
B-Tree 索引	支持	支持	支持

即使多个存储引擎支持同一种类型的索引，但是他们的实现原理也是不同的。Innodb 和 MyISAM 默认的索引是 Btree 索引；而 Memory 默认的索引是 Hash 索引。

MyISAM 引擎使用 B+Tree 作为索引结构，叶子节点的 data 域存放的是数据记录的地址。

4.1 MyISAM 索引的原理

我们知道 InnoDB 中索引即数据，也就是聚簇索引的那棵 B+ 树的叶子节点中已经把所有完整的用户记录都包含了，而 MyISAM 的索引方案虽然也使用树形结构，但是却将索引和数据分开存储：

将表中的记录按照记录的插入顺序单独存储在一个文件中，称之为数据文件(.MYD)。这个文件并不划分为若干个数据页，有多少记录就往这个文件中塞多少记录就成了。由于在插入数据的时候并没有刻意按照主键大小排序，所以我们并不能在这些数据上使用二分法进行查找。
使用 MyISAM 存储引擎的表会把索引信息另外存储到一个称为索引文件的另一个文件中(.MYI)。MyISAM 会单独为表的主键创建一个索引，只不过在索引的叶子节点中存储的不是完整的用户记录，而是主键值 + 数据记录地址的组合。

4.2 MyISAM 与 InnoDB 对比

MyISAM 的索引方式都是“非聚簇”的，与 InnoDB 包含 1 个聚簇索引是不同的。小结两种引擎中索引的区别：

① 在 InnoDB 存储引擎中，我们只需要根据主键值对 聚簇索引 进行一次查找就能找到对应的记录，而在 MyISAM 中却需要进行一次回表操作，意味着 MyISAM 中建立的索引相当于全部都是二级索引。

② InnoDB 的数据文件本身就是索引文件，而 MyISAM 索引文件和数据文件是分离的，索引文件仅保存数据记录的地址。

③ InnoDB 的非聚簇索引 data 域存储相应记录主键的值，而 MyISAM 索引记录的是地址。换句话说，InnoDB 的所有非聚簇索引都引用主键作为 data 域。

④ MyISAM 的回表操作是十分快速的，因为是拿着地址偏移量直接到文件中取数据的，反观 InnoDB 是通过获取主键之后再去聚簇索引里找记录，虽然说也不慢，但还是比不上直接用地址去访问。

⑤ InnoDB 要求表必须有主键（ MyISAM 可以没有）。如果没有显式指定，则 MySQL 系统会自动选择一个可以非空且唯一标识数据记录的列作为主键。如果不存在这种列，则 MySQL 自动为 InnoDB 表生成一个隐含字段作为主键，这个字段长度为 6 个字节，类型为长整型（Bigint）。

5. 索引的代价

索引是个好东西，可不能乱建，它在空间和时间上都会有消耗：

空间上的代价

每建立一个索引都要为它建立一棵 B+树，每一棵 B+树的每一个节点都是一个数据页，一个页默认会占用 16KB 的存储空间，一棵很大的 B+树由许多数据页组成，那就是很大的一片存储空间。
时间上的代价

每次对表中的数据进行 增、删、改 操作时，都需要去修改各个 B+树索引。而且我们讲过，B+树每层节点都是按照索引列的值从小到大的顺序排序而组成了双向链表。不论是叶子节点中的记录，还是内节点中的记录（也就是不论是用户记录还是目录项记录）都是按照索引列的值从小到大的顺序而形成了一个单向链表。而增、删、改操作可能会对节点和记录的排序造成破坏，所以存储引擎需要额外的时间进行一些记录移位，页面分裂、页面回收等操作来维护好节点和记录的排序。如果我们建了许多索引，每个索引对应的 B+树都要进行相关的维护操作，会给性能拖后腿。

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

为了能建立又好又少的索引，我们得学学这些索引在哪些条件下起作用的。

6. MySQL 数据结构选择的合理性

从 MySQL 的角度讲，不得不考虑一个现实问题就是磁盘 10 。如果我们能让索引的数据结构尽量减少硬盘的 1/0 操作，所消耗的时间也就越小。可以说，磁盘的 I/O 操作次数对索引的使用效率至关重要。

查找都是索引操作，一般来说索引非常大，尤其是关系型数据库，当数据量比较大的时候，索引的大小有可能几个 G 甚至更多，为了减少索引在内存的占用，数据库索引是存储在外部磁盘上的。当我们利用索引查询的时候，不可能把整个索引全部加载到内存，只能逐一加载，那么 MySQL 衡量查询效率的标准就是磁盘 I/O 次数。

6.1 全表查询

这里都懒得说了。

6.2 Hash 查询

加快查找速度的数据结构，常见的有两类：

树，例如平衡二叉搜索树，查询/插入/修改/删除的平均时间复杂度都是 O(log2N);
哈希，例如 HashMap，查询/插入/修改/删除的平均时间复杂度都是 O(1); (key, value)

哈希函数 h 有可能将两个不同的关键字映射到相同的位置，这叫做碰撞，在数据库中一般采用链接法来解决。在链接法中，将散列到同一槽位的元素放在一个链表中。

实验：体会数组和 hash 表的查找方面的效率区别

// 算法复杂度为 O(n)
@Test
public void test1(){
    int[] arr = new int[100000];
    for(int i = 0;i < arr.length;i++){
        arr[i] = i + 1;
    }
    long start = System.currentTimeMillis();
    for(int j = 1; j<=100000;j++){
        int temp = j;
        for(int i = 0;i < arr.length;i++){
            if(temp == arr[i]){
                break;
            }
        }
    }
    long end = System.currentTimeMillis();
    System.out.println("time： " + (end - start)); //time： 823
}

// 算法复杂度为 O(1)
@Test
public void test2(){
    HashSet<Integer> set = new HashSet<>(100000);
    for(int i = 0;i < 100000;i++){
    	set.add(i + 1);
    }
    long start = System.currentTimeMillis();
    for(int j = 1; j<=100000;j++) {
        int temp = j;
        boolean contains = set.contains(temp);
    }
    long end = System.currentTimeMillis();
    System.out.println("time： " + (end - start)); //time： 5
}

Hash 结构效率高，那为什么索引结构要设计成树型呢？

原因 1：Hash 索引仅能满足 (=) (<>) 和 IN 查询。如果进行 范围查询，时间复杂度会退化为 O(n) ；而树型的“有序”特性，依然能够保持 O(log₂ N) 的高效率。

原因 2：Hash 索引还有一个缺陷，数据的存储是没有顺序的，在 ORDER BY 的情况下，使用 Hash 索引还需要对数据重新排序。

原因 3：对于联合索引的情况，Hash 值是将联合索引键合并后一起来计算的，无法对单独的一个键或者几个索引键进行查询。

原因 4：对于等值查询来说，通常 Hash 索引的效率更高，不过也存在一种情况，就是索引列的重复值如果很多, 效率就会降低。这是因为遇到 Hash 冲突时，需要遍历桶中的行指针来进行比较，找到查询的关键字，非常耗时。所以，Hash 索引通常不会用到重复值多的列上，比如列为性别、年龄的情况等。

Hash 索引适用存储引擎如表所示：

索引 / 存储引擎	MyISAM	InnoDB	Memory
HASH 索引	不支持	不支持	支持

Hash 索引的适用性：

Hash 索引存在着很多限制，相比之下在数据库中 B+ 树索引的使用面会更广，不过也有一些场景采用 Hash 索引效率更高，比如在键值型 (Key-Value) 数据库中，Redis 存储的核心就是 Hash 表。

MySQL 中的 Memory 存储引擎支持 Hash 存储，如果我们需要用到查询的临时表时，就可以选择 Memory 存储引擎，把某个字段设置为 Hash 索引，比如字符串类型的字段，进行 Hash 计算之后长度可以缩短到几个字节。当字段的重复度低，而且经常需要进行等值查询的时候，采用 Hash 索引是个不错的选择。

另外，InnoDB 本身不支持 Hash 索引，但是提供自适应 Hash 索引 (Adaptive Hash Index)。什么情况下才会使用自适应 Hash 索引呢? 如果某个数据经常被访问，当满足一定条件的时候，就会将这个数据页的地址存放到 Hash 表中。这样下次查询的时候，就可以直接找到这个页面的所在位置。这样让 B+ 树也具备了 Hash 索引的优点。

采用自适应 Hash 索引目的是方便根据 SQL 的查询条件加速定位到叶子节点，特别是当 B+ 树比较深的时候，通过自适应 Hash 索引可以明显提高数据的检索效率。

我们可以通过 innodb_adaptive_hash_index 变量来查看是否开启了自适应 Hash

1	show variables like '%adaptive_hash_index';

6.3 二叉搜索树

如果我们利用二叉树作为索引结构，那么磁盘的 IO 次数和索引树的高度是相关的。

1. 二叉搜索树的特点

一个节点只能有两个子节点，也就是一个节点度不能超过 2
左子节点 < 本节点; 右子节点 >= 本节点，比我大的向右，比我小的向左

2. 查找规则

为了提高查询效率，就需要减少磁盘 IO 数。为了减少磁盘 IO 的次数，就需要尽量降低树的高度，需要把原来“瘦高”的树结构变的“矮胖”，树的每层的分叉越多越好。

6.4 AVL 树

为了解决上面二叉查找树退化成链表的问题，人们提出了平衡二叉搜索树（Balanced Binary Tree），又称为 AVL 树（有别于 AVL 算法），它在二叉搜索树的基础上增加了约束，具有以下性质:

它是一棵空树或它的左右两个子树的高度差的绝对值不超过 1，并且左右两个子树都是一棵平衡二叉树。

这里说一下，常见的平衡二叉树有很多种，包括了平衡二叉搜索树、红黑树、数堆、伸展树。平衡二叉搜索树是最早提出来的自平衡二叉搜索树，当我们提到平衡二叉树时一般指的就是平衡二叉搜索树。

数据查询的时间主要依赖于磁盘 I/O 的次数，如果我们采用二叉树的形式，即使通过平衡二叉搜索树进行了改进，树的深度也是 O(log 2n) ，当 n 比较大时，深度也是比较高的，比如下图的情况：

每访问一次节点就需要进行一次磁盘 I/O 操作，对于上面的树来说，我们需要进行 5 次 I/O 操作。虽然平衡二叉树的效率高，但是树的深度也同样高，这就意味着磁盘 I/O 操作次数多，会影响整体数据查询的效率。

针对同样的数据，如果我们把二叉树改成 M 叉树（M>2）呢？当 M=3 时，同样的 31 个节点可以由下面的三叉树来进行存储：

你能看到此时树的高度降低了，当数据量 N 大的时候，以及树的分叉树 M 大的时候，M 叉树的高度会远小于二叉树的高度 (M > 2)。所以，我们需要把树从“瘦高” 变 “矮胖”。

6.5 B-Tree

B 树的英文是 Balance Tree，也就是 多路平衡查找树。简写为 B-Tree。它的高度远小于平衡二叉树的高度。

B 树作为多路平衡查找树，它的每一个节点最多可以包括 M 个子节点，M 称为 B 树的阶。每个磁盘块中包括了关键字和子节点的指针。如果一个磁盘块中包括了 x 个关键字，那么指针数就是 x + 1 。对于一个 100 阶的 B 树来说，如果有 3 层的话最多可以存储约 100 万的索引数据。对于大量的索引数据来说，采用 B 树的结构是非常适合的，因为树的高度要远小于二叉树的高度。

一个 M 阶的 B 树（M>2）有以下的特性：

根节点的儿子数的范围是 [2,M]。
每个中间节点包含 k-1 个关键字和 k 个孩子，孩子的数量 = 关键字的数量 +1，k 的取值范围为 [ceil(M/2), M]。
叶子节点包括 k-1 个关键字（叶子节点没有孩子），k 的取值范围为 [ceil(M/2), M]。
假设中间节点节点的关键字为：Key[1], Key[2], …, Key[k-1]，且关键字按照升序排序，即 Key[i]<Key[i+1]。此时 k-1 个关键字相当于划分了 k 个范围，也就是对应着 k 个指针，即为：P[1], P[2], …, P[k]，其中 P[1] 指向关键字小于 Key[1] 的子树，P[i] 指向关键字属于 (Key[i-1], Key[i]) 的子树，P[k] 指向关键字大于 Key[k-1] 的子树。
所有叶子节点位于同一层。

在 B 树的搜索过程中，我们比较的次数并不少，但如果把数据读取出来然后在内存中进行比较，这个时间就是可以忽略不计的。而读取磁盘块本身需要进行 I/O 操作，消耗的时间比在内存中进行比较所需要的时间要多，是数据查找用时的重要因素。B 树相比于平衡二叉树来说磁盘 I/O 操作要少，在数据查询中比平衡二叉树效率要高。所以只要树的高度足够低，I/O 次数足够少，就可以提高查询性能。

小结:

B 树在插入和删除节点的时候如果导致树不平衡，就通过自动调整节点的位置来保持树的自平衡。
关键字集合分布在整棵树中, 即叶子节点和非叶子节点都存放数据。搜索有可能在非叶子节点结束。
其搜索性能等价于在关键字全集内做一次二分查找。

6.6 B+Tree

B+ 树也是一种多路搜索树，基于 B 树做出了改进，主流的 DBMS 都支持 B+ 树的索引方式，比如 MySQL。相比于 B-Tree，B+Tree 适合文件索引系统。|

B+ 树和 B 树的差异在于以下几点：

有 k 个孩子的节点就有 k 个关键字。也就是孩子数量 = 关键字数，而 B 树中，孩子数量 = 关键字数 +1。
非叶子节点的关键字也会同时存在在子节点中，并且是在子节点中所有关键字的最大（或最小）。
非叶子节点仅用于索引，不保存数据记录，跟记录有关的信息都放在叶子节点中。而 B 树中，非叶子节点既保存索引，也保存数据记录。
所有关键字都在叶子节点出现，叶子节点构成一个有序链表，而且叶子节点本身按照关键字的大小从小到大顺序链接。

首先，B+ 树查询效率更稳定。因为 B+ 树每次只有访问到叶子节点才能找到对应的数据，而在 B 树中，非叶子节点也会存储数据，这样就会造成查询效率不稳定的情况，有时候访问到了非叶子节点就可以找到关键字，而有时需要访问到叶子节点才能找到关键字。

其次，B+ 树的查询效率更高。一般来说，索引本身也很大，不可能全部存储在内存中，因此索引往往以索引文件的形式存储的磁盘上。这样的话，索引查找过程中就要产生磁盘 I/O 消耗。而因为 B+树的内部节点只是作为索引使用，而不像 B 树那样每个节点都需要存储硬盘指针。也就是说：B+树中每个非叶节点没有指向某个关键字具体信息的指针，所以每一个节点可以存放更多的关键字数量，即一次性读入内存所需要查找的关键字也就越多，减少了 I/O 操作。

不仅是对单个关键字的查询上，在查询范围上， B+ 树的效率也比 B 树高。这是因为所有关键字都出现在 B+ 树的叶子节点中，叶子节点之间会有指针，数据又是递增的，这使得我们范围查找可以通过指针连接查找。而在 B 树中则需要通过中序遍历才能完成查询范围的查找，效率要低很多。

B 树和 B+ 树都可以作为索引的数据结构，在 MySQL 中采用的是 B+ 树。但 B 树和 B+树各有自己的应用场景，不能说 B+树完全比 B 树好，反之亦然。

思考题：B+树的存储能力如何？为何说一般查找行记录，最多只需 1~3 次磁盘 IO

思考题：为什么说 B+树比 B-树更适合实际应用中操作系统的文件索引和数据库索引？

思考题：Hash 索引与 B+ 树索引的区别

6.7 R 树

R-Tree 在 MySQL 很少使用，仅支持 geometry 数据类型，支持该类型的存储引擎只有 myisam、bdb、 innodb、ndb、archive 几种。举个 R 树在现实领域中能够解决的例子：查找 20 英里以内所有的餐厅。如果没有 R 树你会怎么解决？一般情况下我们会把餐厅的坐标(x,y)分为两个字段存放在数据库中，一个字段记录经度，另一个字段记录纬度。这样的话我们就需要遍历所有的餐厅获取其位置信息，然后计算是否满足要求。如果一个地区有 100 家餐厅的话，我们就要进行 100 次位置计算操作了，如果应用到谷歌、百度地图这种超大数据库中，这种方法便必定不可行了。R 树就很好的解决了这种高维空间搜索问题。它把 B 树的思想很好的扩展到了多维空间，采用了 B 树分割空间的思想，并在添加、删除操作时采用合并、分解结点的方法，保证树的平衡性。因此，R 树就是一棵用来存储高维数据的平衡树。相对于 B-Tree，R-Tree 的优势在于范围查找。

索引 / 存储引擎	MyISAM	InnoDB	Memory
R-Tree 索引	支持	支持	不支持

6.8 小结

使用索引可以帮助我们从海量的数据中快速定位想要查找的数据，不过索引也存在一些不足，比如占用存储空间、降低数据库写操作的性能等，如果有多个索引还会增加索引选择的时间。当我们使用索引时，需要平衡索引的利 (提升查询效率) 和弊 (维护索引所需的代价)。|

在实际工作中，我们还需要基于需求和数据本身的分布情况来确定是否使用索引，尽管索引不是万能的，但数据量大的时候不使用索引是不可想象的，毕竟索引的本质是帮助我们提升数据检索的效率。