封面来源：由博主个人绘制，如需使用请联系博主。

1. 为什么使用索引

索引是存储引擎用于快速找到数据记录的一种数据结构，就好比一本书的目录，能够通过目录快速找到对应文章的页码。MySQL 中的索引也是一样的道理，进行数据查找时，先确认给定的查询条件是否命中某条索引，符合则通过索引查找相关数据，反之进行全表扫描，直到找到与条件符合的记录。

顺序查找某条记录

数据库在没有索引的情况下，数据分布在磁盘的不同位置上，读取数据时，摆臂需要前后摆动查找数据，非常耗时。

如果数据顺序摆放，也需要一行一行地读取，如果数据量很大，依旧非常耗时。

以二叉搜索树存储数据

如果以二叉搜索树来存储数据，并对 Col2 添加了索引。假设需要查找 Col2 = 89 这条数据，由于二叉搜索树独特的结构，只需要两次即可查找到目标数据。

建立索引能够减少磁盘 IO 的次数，加快查询效率。

2. 索引及其优缺点

2.1 索引的概述

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

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

索引是在存储引擎中实现的，因此每种存储引擎的索引不一定完全相同，并且每种存储引擎不一定支持所有的索引类型。

存储引擎可以定义每个表的最大索引数和最长索引长度。

所有存储引擎支持每个表最多 16 个索引，总索引长度最多为 256 字节，某些存储引擎还能支持更多的索引和更大的索引长度。

2.2 索引的优点

提高数据检索的效率，降低数据库的 IO 成本
通过创建唯一索引，保证每行数据的唯一性
加速表与表之间的连接，对有依赖关系的主子表进行查询时，能够提高查询效率
使用分组和排序子句查询数据时，可以显著减少查询中分组和排序的时间

2.3 索引的缺点

创建索引和维护索引需要消耗时间，随着数据量的增加，消耗的时间也会增加
索引需要占据一定的磁盘空间，如果存在大量的索引，索引文件可能比数据文件更快达到最大文件尺寸
索引会降低更新表的速度，当表中的数据发生变化时，索引可能也需要动态地维护，这会降低修改数据的速度

当有大量数据需要更新时，可以先删除表中的索引，然后再更新数据，更新完成后再创建索引。

3. InnoDB 中索引的推演

3.1 索引之前的查找

精准匹配：

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

在一个页中的查找

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

以主键为搜索条件

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

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

在很多页中查找

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

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

在没有索引的情况下，不论是根据主键列或者其他列的值进行查找，由于不能快速地定位到记录所在的页，所以只能从第一个页沿着双向链表一直往下找。

为了提高查找效率，索引应运而生。

3.2 初识行结构

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 表的行格式示意图：

index_demo表的行格式

record_type：记录头信息的一项属性，表示记录的类型。0 表示普通记录，2 表示最小记录，3 表示最大记录，1 表示目录项的记录。
next_record：记录头信息的一项属性，表示下一条地址相对于本条记录的地址偏移量，下文会使用箭头来表明下一条记录是谁。
各个列的值：以 index_demo 表为例，记录了 c1 、c2 和 c3 三个列。
其他信息：除上述信息之外，还记录了包括其他隐藏列的值以及记录的额外信息。

将其他信息项暂时去掉并把它竖起来的效果就是这样：

把行格式竖过来

再放一些记录到页中：

添加记录到页中后的示意图

3.3 简单的设计方案

在根据某个搜索条件查找一些记录时为什么要遍历所有的数据页呢？

因为各个页中的记录并没有规律，不知道搜索条件匹配哪些页中的记录，所以不得不依次遍历所有的数据页。

如何快速地定位到需要查找的记录在哪些数据页中呢？

可以为目标记录所在的数据页建立一个目录，该目录完成：

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

假设数据页中只能放 3 条数据，此时在页 10 中已经放置了主键值为 1、3、5 的三条数据，接下来需要插入一条主键为 4 的数据。这不仅需要再分配一个新页，为了满足主键值依次增长，还伴随着依次记录移动，把主键值为 5 的数据移动到新页中，然后把主键值为 4 的记录插入到当前页中。记录移动的过程称之为 页分裂。
给所有的页建立一个目录项。

简单的页目录示意图

以页 28 为例，它对应目录项 2，这个目录项中包含着该页的页号 28 以及该页中用户记录的最小主键值 5 。

只需要把几个目录项在物理存储器上连续存储（比如：数组），就可以实现根据主键值快速查找到某条记录。

比如查找主键值为 20 的记录：

先从目录项中根据二分法快速确定出主键值为 20 的记录在目录项 3 中（因为 12 < 20 < 209），对应页 9；
在页 9 中查找具体的记录

对于这个目录的名字，更喜欢称为“索引”。

3.4 InnoDB 的索引方案

第一次迭代：目录项记录的页

InnoDB 是使用页作为管理存储空间的基本单位，最多能保证 16KB 的连续存储空间。随着表中记录数量的增多，需要非常大的连续存储空间才能把所有的目录项都放下，这对记录数量非常多的表是不现实的。

假设对某页中的所有数据都进行了删除，那么其对应的目录项也没有存在的必要了，需要把其后所有的目录项都向前移动。

目录项和用户记录其实差不多，只不过目录项中的两列是主键和页号。为了和用户记录进行对比，不妨将用来表示目录项的记录称为 目录项记录。

InnoDB 使用记录头信息中的 record_type 属性来区分用户记录和目录项记录：

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

如果将目录项也放到数据页中：

目录项在数据页中的表示

目录项记录与用户记录的不同点：

前者的 record_type 是 1，后者的 record_type 是 0；
前者只有主键值和页的编号两列，后者由用户自定义和 InnoDB 添加的隐藏列；
记录头信息里还有一个叫 min_rec_mask 的属性，只有在存储 目录项记录 的页中的 最小主键值 的目录项记录的 min_rec_mask 值为1 ，其他别的记录的 min_rec_mask 值都是0 。

目录项记录与用户记录的相同点：

用的是一样的数据页，都会为主键值生成 Page Directory，即页目录，以便在按照主键值进行查找时使用二分法来加快查询速度。

第二次迭代：多个目录项记录的页

虽然目录项记录中只存储了主键值和对应的页号，但是一个页只能有 16KB，能存放的目录项记录依旧是有限的。

假设一个存储目录项记录的页最多只能存放 4 条目录项记录，如果此时再插入一条主键值为 328 的用户记录，那就需要分配一个新的存储目录项记录的页：

多个目录项记录的页

插入了主键值为 320 的用户记录后需要两个新的数据页：

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

第三次迭代：目录项记录页的目录项

随着目录项记录的增多，目录项记录的页也会不断增多。由于这些页也是不连续的，为了快速地定位到某个具体的存放目录项记录的页，需要为这些页生成更高级的目录，最终形成类似多级目录的结构。

针对上述结构，可以使用下图来描述：

推导出索引的B+树结构

这个数据结构又被称为 B+ 树。

B+ 树

用于数据页都存放在 B+ 树中了，所以这些数据页也被称为节点。根据前面的迭代过程可知，用户记录都存放在 B+ 树的最底层节点（叶子结点）上，其余用来存放目录项的节点被称为内节点（非叶子结点），最上面的节点被称为根节点。

实际上，一个页存放的记录数量是非常大的，远不止前文假设的 3、4 条。不妨稍微大胆点，假设所有存放用户记录的叶子节点代表的数据页可以存放 100 条用户记录，所有存放目录项记录的内节点代表的数据页可以存放 1000 条目录项记录：

如果 B+ 树只有一层，最多存放 100 条记录；
如果 B+ 树有两层，最多存放 $100 \times 1000 = 10, 0000$ 条记录；
如果 B+ 树有三层，最多存放 $100 \times 1000 \times 1000 = 1, 0000, 0000$ 条记录；
如果 B+ 树有四层，最多存放 $100 \times 1000 \times 1000 \times 1000 = 1000, 0000, 0000$ 条记录；

当 B+ 树有四层时，就能存放相当多的记录，所以一般情况下，使用的 B+ 树都不会超过四层。在这种情况下，通过主键值去查找某条记录最多只需要做 4 个页面内的查找（查找 3 个目录项页和 1 个用户记录页），又因为在每个页面内都有 Page Directory（页目录），所以在页面内还可以通过二分法实现快速定位记录。

选择 B+ 树作为底层存储结构也是有道理的，4 层的 B+ 树就能存放很多数据了，而树的层次越低，IO 次数也就越少。

4. 常见索引概念

索引按照物理实现方式，可以分为 2 种：

聚簇（聚集）索引
非聚簇（非聚集）索引，也称为二级索引或辅助索引

4.1 聚簇索引

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

“聚簇”表示数据行和相邻的键值聚簇地储存在一起。

特点

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

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

优点

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

缺点

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

限制

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

4.2 非聚簇索引

聚族索引只能在搜索条件是主键值时才能发挥作用，因为 B+ 树中的数据都是按照主键进行排序的。那如果想以别的列作为搜索条件该怎么办呢？

肯定不能从头到尾沿着链表依次遍历记录一遍吧。

可以多建几棵 B+ 树，不同 B+ 树中的数据采用不同的排序规则。

比方说用 c2 列的大小作为数据页和页中记录的排序规则，再建一棵 B+ 树：

以c2列作为排序规则建立B+树

这个 B+ 树与前文介绍的聚族索引有几处不同：

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

以上图为例，如果要查找 c2 列值为 4 的记录：

确定目录项记录页。根据根页面（即页 44）快速定位到目录项记录所在的页为页 42
根据目录项记录页确定用户记录真实所在的页。在页 42 中快速定位到实际存储用户记录的页，但由于 c2 列并没有唯一性约束，所以值为 4 的 c2 列记录可能分布在多个数据页中，确定实际存储用户记录的页在页 34 和页 35 中
最终定位到具体的记录

回表

以 c2 列大小排序的 B+ 树只能确定要查找记录的主键值，如果想根据 c2 列的值查找完整的用户记录，仍需要到聚簇索引中再查一遍，这个过程称为回表。

也就是根据 c2 列的值查询一条完整的用户记录需要使用到 2 棵 B+ 树。

那为什么需要一次回表操作呢？直接把完整的用户记录放在叶子节点上不行吗？

虽然不用回表，但太浪费存储空间。

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

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

使用聚簇索引时，查询数据的效率更高，但对数据的插入、删除和更新操作相比于非聚簇索引会更低。

InnoDB中的索引分布

4.3 联合索引

也可以同时以多个列的大小作为排序规则，也就是同时为多个列建立索引，比如让 B+ 树按照 c2 和 c3 列的大小进行排序，这包括：

先把各个记录和页按照 c2 列进行排序
当记录的 c2 列相同时，采用 c3 列进行排序
每条目录项记录由 c2、c3 和页号三部分组成，B+ 树的叶子节点处的用户记录由 c2、c3 和主键三部分组成

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

建立联合索引只会建立 1 棵 B+ 树
分别为 c2 或 c3列建立索引则会分别以 c2 或 c3 列的大小为排序规建立 2 棵 B+ 树

5. 索引的注意事项

此处特指 InnoDB 中的 B+ 树索引的注意事项。

5.1 根页面位置万年不动

前文介绍 B+ 树索引时，为了理解上的方便，先把存储用户记录的叶子节点都画出来，接着画出存储目录项记录的内节点，但实际上 B+ 树的形成过程并不是这样的：

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

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

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

B+ 树索引的内节点中目录项记录的内容是 索引列 + 页号 的搭配，但这个搭配对二级索引来说有点不严谨。以 index_demo 表为例，假设此时表中的数据如下：

c1	c2	c3
1	1	‘u’
3	1	‘d’
5	1	‘y’
7	1	‘s’

该表以 c2 列建立了二级索引，假设目录项记录所在的页中的记录将以 c2 列与页号构成，并且每个页中只能存放 3 条数据。

如果插入记录 (9, 1, 'c')，会发现目录项记录所在的页中的两条目录项记录对应的 c2 列的值都是 1，那新增的这条数据应该放到哪个页号对应的页中呢？

为了让新插入记录能够准确地被定位，需要 保证 B+ 树同一层内节点的目录项记录除页号外是唯一的。

所以二级索引的内节点的目录项记录的实际内容由三部分组成：

索引列的值
主键值
页号

把主键值添加到二级索引后，就能够 保证 B+ 树同一层内节点的目录项记录除页号外是唯一的。

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

一个 B+ 树只需要很少的层级就可以轻松存储数亿条记录，这是因为 B+ 树的本质是一个多层级目录，每经过一个目录时都会过滤掉许多无效子目录，直到最后访问到存储真实数据的目录。

如果一个大的目录中只存放一个子目录，就会导致目录层级异常的多，而且最后存放真实数据的目录中只能存放一条记录。哪有什么意义呢？

因此 InnoDB 的一个数据页中至少要存放两条记录。

6. MyISAM 中的索引方案

B 树（B-Tree）索引适用存储引擎如表所示：

MyISAM	InnoDB	Memory
✅	✅	✅

即使多个存储引擎支持同一种类型的索引，它们的实现原理也可能不同。InnoDB 和 MyISAM 默认的索引是 B-Tree 索引，而 Memory 默认的索引是 Hash 索引。

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

6.1 MyISAM 索引的原理

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

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

MyISAM索引原理图

上述是 MyISAM 表的主索引（Primary key）示意图，表中共有三列，并选用 Col1 作为主键。可以看出，MyISAM 的索引文件仅仅保存数据记录的地址。

在 MyISAM 中，主键索引和二级索引（Secondary key）在结构上没有区别，只是主键索引要求 key 唯一，二级索引的 key 可以重复。

如果在 Col2 上建立一个二级索引，索引结构如下图所示：

在Col2列上建立MyISAM表的二级索引

6.2 与 InnoDB 对比

MyISAM 的索引方式都是“非聚簇”的，与 InnoDB 始终包含 1 个聚簇索引是不同的：

在 InnoDB 存储引擎中，只需要根据主键值对聚簇索引进行一次查找就能找到对应的记录，而在 MyISAM 中却需要进行一次回表操作，这相当于 MyISAM 中建立的索引全都是二级索引；
InnoDB 的数据文件本身就是索引文件，而 MyISAM 的索引文件和数据文件是分离的，索引文件仅保存数据记录的地址；
InnoDB 的非聚簇索引 data 域存储相应记录主键的值，而 MyISAM 索引存储的是记录的地址。换句话说，InnoDB 的所有非聚簇索引都引用主键作为 data 域；
MyISAM 的回表操作是十分快速的，因为能够使用地址偏移量直接从文件中获取数据，反观 InnoDB 则要在获取主键后再去聚簇索引里找对应的记录，相比 MyISAM 会慢一点；
InnoDB 要求表必须有主键（MyISAM 没有这个要求）。如果没有显式指定，MySQL 会自动选择一个非空且唯一的列作为主键。如果不存在这样的列，MySQL 将为 InnoDB 表生成一个隐藏字段作为主键，这个字段占 6 个字节，类型是长整型。

通过了解不同存储引擎的索引实现方式，对于正确使用和优化索引都有帮助：

使用 InnoDB 时，不建议使用过长的字段作为主键，因为所有二级索引都引用了主键索引，过长的主键会导致二级索引变得过大；
使用非单调的字段作为主键在 InnoDB 中不是一个好主意，因为 InnoDB 数据文件本身是一棵 B+Tree，非单调的主键会造成在插入新记录时，数据文件为了维持 B+Tree 的特性而频繁地分裂调整，影响插入效率，使用自增字段作为主键是一个较好的选择。

InnoDB表与MyISAM表的索引结构对比

7. 索引的代价

索引虽然能提升查询效率，但它不是银弹，它在时间、空间上都有代价：

时间上的代价：每次对表中的数据进行增、删、改时，都需要去修改各个 B+Tree 索引。B+Tree 每层节点都是按照索引列的值从小到大的顺序排序后组成的双向链表。不论是叶子节点中的记录，还是内节点中的记录（即不论是用户记录还是目录项记录）都是按照索引列的值从小到大的顺序形成一个单向链表。增、删、改可能会对节点和记录的排序造成破坏，后续存储引擎需要额外的时间进行记录移位、页面分裂、页面回收等操作来维护节点和记录的排序。如果建了许多索引，每个索引对应的 B+Tree 都要进行相关的维护，这会导致增、删、改的性能下降。
空间上的代价：每建立一个索引都要为它建立一棵 B+Tree，每一棵 B+Tree 的每一个节点都是一个数据页，一个页默认会占用 16KB 的存储空间，一棵很大的 B+Tree 由多个数据页组成，这会是很大一片存储空间。

8. 索引结构的选择合理性

从 MySQL 的角度来讲，不得不考虑的一个现实问题是磁盘 IO。如果能让索引的数据结构尽量减少硬盘的 IO 操作，所消耗的时间也就越小。

查找都是索引操作，当数据量较大时，索引的大小有可能几个 G 甚至更多，为了减少索引在内存上的占用，索引是存储在外部磁盘上的。当利用索引进行查询时，不能把整个索引全部加载到内存，只能逐一加载，那么 MySQL 衡量查询效率的标准就是磁盘 IO 次数。

8.1 Hash 结构

Hash 本身是一个函数，又被称为散列函数，它可以大幅提升检索数据的效率。

Hash 算法是通过某种确定性的算法（比如 MD5、SHA1、SHA2、SHA3）将输入转变为输出。相同的输入永远可以得到相同的输出，如果输入内容有微小偏差，在输出中 通常（不是一定） 会有不同的结果。

比如要判断两个文件是否相同，无需把两份文件直接对比，只需要求出彼此的 Hash 值并进行相等性比较即可。这在大多数情况下都是符合要求的，但在某些情况下也可能出现两个完全不同的文件求出了相同的 Hash 值（曾经在万能的贴吧有幸见到过两张相同 Hash 值，但内容完全不同的图片）。

以 Java 中的 HashMap 为例，它的数据存储示意图是：

HashMap的数据存储示意图

采用 Hash 进行数据检索的效率非常高，往往一次检索就能找到目标数据。与 B+Tree 进行对比，B+Tree 需要自顶向下依次查找，多次进行节点的访问才能找到目标数据，中间需要多次 IO 操作。

在 Hash 的方式下，一个元素 $k$ 处于 $h(k)$ 中，即利用哈希函数 $h$ ，根据关键字 $k$ 计算出槽的位置。函数 $h$ 将关键字域映射到哈希表 $T[0, m - 1]$ 的槽位上。

哈希碰撞的产生

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

使用链接法解决哈希碰撞

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

Hash 索引仅能满足等值查询和 IN 查询，如果想要进行范围查询，哈希型索引的时间复杂度会退化为 $O(n)$ ，进行全表扫描，而树的“有序”性却依然能够保持 $O(log2n)$ 的高效率；
Hash 索引下的数据存储是没有顺序的，在进行 ORDER BY 时，需要对数据重新排序；
创建联合索引时，Hash 索引是将联合索引键合并后一起来计算的，无法单独地对一个键或几个索引键进行查询，此时无法仅仅通过 Hash 索引来定位目标记录（不同列的索引键合并计算 Hash 后可能得到相同的值）；
对于等值查询来说，Hash 索引的效率往往更高，但如果索引列的重复值很多，效率也会降低。这是因为发生 Hash 冲突时，需要遍历桶中的行指针来进行比较，这会非常耗时，因此通常不会在重复值多的列上建立 Hash 索引，比如性别列、年龄列。

支持 Hash 索引的存储引擎

MyISAM	InnoDB	Memory
❌	❌	✅

Hash 索引的适用性

Hash 索引存在着很多限制，B+Tree 索引的适用面更广，不过在某些场景中采用 Hash 索引的效率会更高，比如在键值型（Key-Value）数据库中，例如 Redis 的核心就是 Hash 表。

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

InnoDB 引擎本身不支持 Hash 索引，但提供了自适应 Hash 索引（Adaptive Hash Index)。如果某个数据经常被访问，在满足一定条件时，会将这个数据页的地址存放到 Hash 表中，在下次查询时，可以直接找到页所在的位置。

自适应Hash索引图示

采用自适应 Hash 索引能够根据 SQL 的查询条件快速定位到叶子节点，尤其是当 B+Tree 层次较深时，通过自适应 Hash 索引可以明显提高数据的检索效率。

可以通过 innodb_adaptive_hash_index 变量来查看是否开启了自适应 Hash 索引：

1	SHOW VARIABLES LIKE '%adaptive_hash_index';

8.2 二叉搜索树

二叉搜索树的特点、Java 实现可以参考数据结构之二叉搜索树一文。

对数列（34、22、89、5、23、77、91）构造出的二叉搜索树如下图所示：

常见的二叉搜索树

但在极端情况下，二叉搜索树的深度会非常大，退化成了链表。比如以数列（5、22、23、34、77、89、91）构造出的二叉搜索树如下图所示：

退化为链表的二叉搜索树

树的高度越低，才能减少磁盘 IO 次数，才能提高查询效率，二叉搜索树在极端情况下显然不合适。

8.3 AVL 树

为了防止二叉搜索树退化成链表，提出了 AVL 树的概念。相比于二叉搜索树，AVL 树的左右子树高度差的绝对值不操作 1，并且左右子树都是一棵平衡二叉树。

AVL 树的特点、Java 实现可以参考数据结构之 “艾薇儿” 树一文。

当节点数量较多时，AVL 树的高度也会很高，比如 31 个节点的 AVL 树：

31个节点的AVL树

此时共有 5 层，但如果改成三叉树：

31个节点的三叉树

树的高度减低了。也就是说，当节点数量较大时，树的分叉数越大，树的高度也就越低。

8.4 B-Tree

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

三阶B树

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

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

根节点的儿子数的范围是 $[2, M]$ ；
每个中间节点包含 $k-1$ 个关键字和 $k$ 个孩子，孩子的数量 = 关键字的数量 + 1， $k \in [ceil(M/2), M]$ 。
叶子节点包括 $k-1$ 个关键字， $k \in [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 树为例，磁盘块 2 里的关键字为 $(8,12)$ ，它有 3 个孩子 $(3, 5)$ ， $(9, 10)$ 和 $(13, 15)$ ， $(3, 5)$ 小于 $8$ ， $(9, 10)$ 在 $8$ 和 $12$ 之间， $(13, 15)$ 大于 $12$ 。

假设要查找的关键字是 9，那么查找步骤为：

与根节点的关键字 $(17, 35)$ 进行比较，9 小于 17 那么得到指针 P1；
按照指针 P1 找到磁盘块 2，关键字为 $(8, 12)$ ，因为 9 在 8 和 12 之间，得到指针 P2；
按照指针 P2 找到磁盘块 6，关键字为 $(9, 10)$ ，最终找到关键字 9。

小结

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

另一个B数图示

8.5 B+Tree

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

B+Tree 与 B-Tree 的差异：

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

B+Tree 的中间节点不直接存储数据，这有什么好处呢？

B+Tree 查询效率更稳定。因为 B+Tree 每次只有访问到叶子节点才能找到对应的数据，而在 B-Tree 中，非叶子节点也会存储数据，这会造成查询效率不稳定的情况，有时候访问到非叶子节点就可以找到关键字，而有时需要访问到叶子节点才能找到关键字。
B+Tree 的查询效率更高。因为 B+Tree 通常比 B-Tree 更矮胖（阶数越大，深度越低），查询需要的磁盘 IO 也更少，同样大小的磁盘页，B+Tree 可以存储更多的节点关键字。
在查询范围上，B+Tree 的效率比 B-Tree 高。因为所有关键字都出现在 B+Tree 的叶子节点中，叶子节点之间会有指针，数据递增排列，使得范围查找可以通过指针连接查找，而在 B-Tree 中则需要通过中序遍历才能完成范围的查找，效率要低很多。

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

为了减少 IO，索引树会一次性加载吗？

索引是存储在磁盘上的，如果数据量很大，会导致索引的大小也很大，甚至达到几个 G。利用索引进行查询时，不会将全部索引都加载到内存，只能逐一加载每一个磁盘页，磁盘页对应着索引树的节点。

B+Tree 的存储能力怎么样？为什么说一般查找行记录，最多只需 1~3 次磁盘 IO？

InnoDB 存储引擎中页的大小为 16KB，表的主键类型一般为 INT（占用 4 个字节）或 BIGINT（占用 8 个字节），指针类型一般也是 4 或 8 个字节，也就是说一个页（即 B+Tree 中的一个节点）中大概存储 $16KB / (8B + 8B) = 1K$ 个键值（为了方便计算，K 取值为 $10^3$ ，也就是说一个深度为 3 的 B+Tree 索引可以维护 $10^3 \times 10^3 \times 10^3 = 10,0000,0000$ 条记录（假设一个数据页存储 $10^3$ 条行记录数据）。

实际情况中的节点可能不会填充满，因此数据库中的 B+Tree 的高度一般都是 2~4 层。MySQL 的 InnoDB 存储引擎会将根节点常驻内存，也就是说查找某一键值的行记录时最多只需要 1~3 次磁盘 IO 操作。

B+Tree 为什么比 B-Tree 更适合在实际应用中作为操作系统的文件索引和数据库索引？

B+Tree 的磁盘读写代价更低。B+Tree 的内部结点并没有指向关键字具体信息的指针。因此其内部结点相比于 B-Tree 更小。如果把所有同一内部结点的关键字都存放在同一盘块中，那么盘块所能容纳的关键字数量也越多，一次性读入内存中的关键字也就越多，相对来说降低了 IO 读写次数。
B+Tree 的查询效率更稳定。

Hash 索引与 B+Tree 索引的区别

Hash 索引不支持范围查询，B+Tree 索引可以。
Hash 索引不支持联合索引的最左侧原则（即联合索引的部分索引无法使用），B+Tree 索引可以。
Hash 索引不支持 ORDER BY，也不支持模糊查询。
InnoDB 不支持 Hash 索引。

Hash 索引和 B+Tree 索引是建索引时手动指定的吗？

InnoDB 和 MyISAM 存储引擎会默认使用 B+Tree 索引，无法使用 Hash 索引。

InnoDB 提供的自适应 Hash 索引无需手动指定。

MEMORY/HEAP 存储引擎和 NDB 存储引擎可以选择 Hash 索引。

8.6 R 树

R-Tree 在 MySQL 中很少使用，仅支持 GEOMETRY 数据类型，支持该类型的存储引擎只有 MyISAM、BDB、InnoDB、NDB、ARCHIVE 几种。

如果需要查找 20 英里内所有的餐厅，一般情况下会把餐厅的坐标 (x, y) 分为两个字段存放在数据库中，一个字段记录经度，一个字段记录纬度，后续只需要遍历所有的餐厅获取其位置信息，并计算是否满足要求即可。如果一个地区有 100 家餐厅，就需要进行 100 次位置计算操作，如果应用到谷歌地图、百度地图这种超大数据库中，这种方式必定不可行。

R-Tree 很好地解决了这种高维空间搜索问题。它把 B-Tree 的思想扩展到多维空间中，采用了 B-Tree 分割空间的思想，在添加、删除操作时采用合并、分解结点，保证树的平衡性。R-Tree 就是一棵用于存储高维数据的平衡树，相比于 B-Tree，R-Tree 的优势在于范围查找。