认识索引的魅力

只有正确设计索引，业务才能达到上线的初步标准。

索引是什么？

相信你在面试时，通常会被问到“什么是索引？”而你一定要能脱口而出：索引是提升查询速度的一种数据结构。

索引之所以能提升查询速度，在于它在插入时对数据进行了排序（显而易见，它的缺点是影响插入或者更新的性能）。

所以，索引是一门排序的艺术，有效地设计并创建索引，会提升数据库系统的整体性能。在目前的 MySQL 8.0 版本中，InnoDB 存储引擎支持的索引有 B+ 树索引、全文索引、R 树索引。这一讲我们就先关注使用最为广泛的 B+ 树索引。

B+树索引结构

B+ 树索引是数据库系统中最为常见的一种索引数据结构，几乎所有的关系型数据库都支持它。

那为什么关系型数据库都热衷支持 B+树索引呢？因为它是目前为止排序最有效率的数据结构。像二叉树，哈希索引、红黑树、SkipList，在海量数据基于磁盘存储效率方面远不如 B+ 树索引高效。

所以，上述的数据结构一般仅用于内存对象，基于磁盘的数据排序与存储，最有效的依然是 B+ 树索引。

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

又因为现在的固态硬盘每秒能执行至少 10000 次 I/O ，所以查询一条数据，哪怕全部在磁盘上，也只需要 0.003 ~ 0.004 秒。另外，因为 B+ 树矮，在做排序时，也只需要比较 3~4 次就能定位数据需要插入的位置，排序效率非常不错。

B+ 树索引由根节点（root node）、中间节点（non leaf node）、叶子节点（leaf node）组成，其中叶子节点存放所有排序后的数据。当然也存在一种比较特殊的情况，比如高度为 1 的B+ 树索引：

上图中，第一个列就是 B+ 树索引排序的列，你可以理解它是表 User 中的列 id，类型为 8 字节的 BIGINT，所以列 userId 就是索引键（key），类似下表：

CREATE TABLE User (

  id BIGINT AUTO_INCREMENT PRIMARY KEY,
  name VARCHAR(128) NOT NULL,
  sex CHAR(6) NOT NULL,
  registerDate DATETIME NOT NULL,
  ...

)

所有 B+ 树都是从高度为 1 的树开始，然后根据数据的插入，慢慢增加树的高度。你要牢记：索引是对记录进行排序， 高度为 1 的 B+ 树索引中，存放的记录都已经排序好了，若要在一个叶子节点内再进行查询，只进行二叉查找，就能快速定位数据。

节点的存储

在MySQL的InnoDB存储引擎中，B+树索引的每个节点都是存储在一个或多个页（page）中的。页是InnoDB存储数据的基本单位，通常每个页的大小为16KB。

一个节点可能会跨越多个页存储。这种情况主要发生在以下几种情形：

1. 索引键过大导致的分裂

如果索引键或行数据过大，以至于无法完全放入一个页中，InnoDB会将这些数据分裂到多个页中。这种情况通常发生在以下几种情况下：

• 大字段索引：如果索引键包含较大的字段（如较长的字符串或BLOB类型），单个页可能无法容纳所有的键值对。
• 复合索引：如果索引包含多个字段，并且总的键值大小超过了一页的容量，也会导致分裂。

2. 更新导致的分裂

当对表进行更新操作时，如果更新后的数据无法在原来的页中容纳，InnoDB可能会将数据分裂到多个页中。

可随着插入 B+ 树索引的记录变多，1个页（16K）无法存放这么多数据，所以会发生 B+ 树的分裂，B+ 树的高度变为 2，当 B+ 树的高度大于等于 2 时，根节点和中间节点存放的是索引键对，由（索引键、指针）组成。

索引键就是排序的列，而指针是指向下一层的地址，在 MySQL 的 InnoDB 存储引擎中占用 6 个字节。下图显示了 B+ 树高度为 2 时，B+ 树索引的样子：

可以看到，在上面的B+树索引中，若要查询索引键值为 5 的记录，则首先查找根节点，查到键值对（20，地址），这表示小于 20 的记录在地址指向的下一层叶子节点中。接着根据下一层地址就可以找到最左边的叶子节点，在叶子节点中根据二叉查找就能找到索引键值为 5 的记录。

理论上的存储计算

那一个高度为 2 的 B+ 树索引，理论上最多能存放多少行记录呢?

在 MySQL InnoDB 存储引擎中，一个页的大小为 16K，在上面的表 User 中，键值 userId 是BIGINT 类型，则：

根节点能最多存放以下多个键值对 = 16K / 键值对大小(8+6) ≈ 1100

再假设表 User 中，每条记录的大小为 500 字节，则：

叶子节点能存放的最多记录为 = 16K / 每条记录大小 ≈ 32

综上所述，树高度为 2 的 B+ 树索引，最多能存放的记录数为：

总记录数 = 1100 * 32 =  35,200

也就是说，35200 条记录排序后，生成的 B+ 树索引高度为 2。在 35200 条记录中根据索引键查询一条记录只需要查询 2 个页，一个根叶，一个叶子节点，就能定位到记录所在的页。

高度为 3 的 B+ 树索引本质上与高度 2 的索引一致，如下图所示，不再赘述：

同理，树高度为 3 的 B+ 树索引，最多能存放的记录数为：

总记录数 = 1100（根节点） * 1100（中间节点） * 32 =  38,720,000

讲到这儿，你会发现，高度为 3 的 B+ 树索引竟然能存放 3800W 条记录。在 3800W 条记录中定位一条记录，只需要查询 3 个页。那么 B+ 树索引的优势是否逐步体现出来了呢？

不过，在真实环境中，每个页其实利用率并没有这么高，还会存在一些碎片的情况，实际的使用率不可能为100%。

B+ 树的查询高效是要付出代价的，就是我们前面说的插入性能问题，接下去咱们就来讨论一下。

优化 B+ 树索引的插入性能

B+ 树在插入时就对要对数据进行排序，但排序的开销其实并没有你想象得那么大，因为排序是 CPU 操作（当前一个时钟周期 CPU 能处理上亿指令）。

真正的开销在于 B+ 树索引的维护，保证数据排序，这里存在两种不同数据类型的插入情况。

• 数据顺序（或逆序）插入： B+ 树索引的维护代价非常小，叶子节点都是从左往右进行插入，比较典型的是自增 ID 的插入、时间的插入（若在自增 ID 上创建索引，时间列上创建索引，则 B+ 树插入通常是比较快的）。
• 数据无序插入： B+ 树为了维护排序，需要对页进行分裂、旋转等开销较大的操作，另外，即便对于固态硬盘，随机写的性能也不如顺序写，所以磁盘性能也会收到较大影响。比较典型的是用户昵称，每个用户注册时，昵称是随意取的，若在昵称上创建索引，插入是无序的，索引维护需要的开销会比较大。

你不可能要求所有插入的数据都是有序的，因为索引的本身就是用于数据的排序，插入数据都已经是排序的，那么你就不需要 B+ 树索引进行数据查询了。

所以对于 B+ 树索引，在 MySQL 数据库设计中，仅要求主键的索引设计为顺序，比如使用自增，或使用函数 UUID_TO_BIN 排序的 UUID，而不用无序值做主键。

我们再回顾之前说的自增、UUID、UUID 排序的插入性能对比：

可以看到，UUID 由于是无序值，所以在插入时性能比起顺序值自增 ID 和排序 UUID，性能上差距比较明显。

所以，再次强调： 在表结构设计时，主键的设计一定要尽可能地使用顺序值，这样才能保证在海量并发业务场景下的性能。

以上就是索引查询和插入的知识，接下来我们就分析怎么在 MySQL 数据库中查看 B+ 树索引。

MySQL 中 B+ 树索引的设计与管理

在 MySQL 数据库中，可以通过查询表 mysql.innodb_index_stats 查看每个索引的大致情况：

SELECT 
table_name,index_name,stat_name,
stat_value,stat_description 
FROM innodb_index_stats 
WHERE table_name = 'orders' and index_name = 'PRIMARY';

+----------+------------+-----------+------------+------------------+
|table_name| index_name | stat_name | stat_value |stat_description  |
+----------+-------------------+------------+------------+----------+
| orders | PRIMARY|n_diff_pfx01|5778522     | O_ORDERKEY            |
| orders | PRIMARY|n_leaf_pages|48867 | Number of leaf pages        |
| orders | PRIMARY|size        |49024 | Number of pages in the index|
+--------+--------+------------+------+-----------------------------+
3 rows in set (0.00 sec)

从上面的结果中可以看到，表 orders 中的主键索引，大约有 5778522 条记录，其中叶子节点一共有 48867 个页，索引所有页的数量为 49024。根据上面的介绍，你可以推理出非叶节点的数量为 49024 ~ 48867，等于 157 个页。

另外，我看见网上一些所谓的 MySQL“军规”中写道“一张表的索引不能超过 5 个”。根本没有这样的说法，完全是无稽之谈。

在我看来，如果业务的确需要很多不同维度进行查询，那么就该创建对应多索引，这是没有任何值得商讨的地方。

真正在业务上遇到的问题是： 由于业务开发同学对数据库不熟悉，创建 N 多索引，但实际这些索引从创建之初到现在根本就没有使用过！因为优化器并不会选择这些低效的索引，这些无效索引占用了空间，又影响了插入的性能。

那你怎么知道哪些 B+树索引未被使用过呢？在 MySQL 数据库中，可以通过查询表sys.schema_unused_indexes，查看有哪些索引一直未被使用过，可以被废弃：

SELECT * FROM schema_unused_indexes

WHERE object_schema != 'performance_schema';
+---------------+-------------+--------------+
| object_schema | object_name | index_name   |
+---------------+-------------+--------------+
| sbtest        | sbtest1     | k_1          |
| sbtest        | sbtest2     | k_2          |
| sbtest        | sbtest3     | k_3          |
| sbtest        | sbtest4     | k_4          |
| tpch          | customer    | CUSTOMER_FK1 |
| tpch          | lineitem    | LINEITEM_FK2 |
| tpch          | nation      | NATION_FK1   |
| tpch          | orders      | ORDERS_FK1   |
| tpch          | partsupp    | PARTSUPP_FK1 |
| tpch          | supplier    | SUPPLIER_FK1 |
+---------------+-------------+--------------+

如果数据库运行时间比较长，而且索引的创建时间也比较久，索引还出现在上述结果中，DBA 就可以考虑删除这些没有用的索引。

而 MySQL 8.0 版本推出了索引不可见（Invisible）功能。在删除废弃索引前，用户可以将索引设置为对优化器不可见，然后观察业务是否有影响。若无，DBA 可以更安心地删除这些索引：

ALTER TABLE t1 

ALTER INDEX idx_name INVISIBLE/VISIBLE;

索引组织表

数据存储有堆表和索引组织表两种方式。

堆表中的数据无序存放， 数据的排序完全依赖于索引（Oracle、Microsoft SQL Server、PostgreSQL 早期默认支持的数据存储都是堆表结构）。

从图中你能看到，堆表的组织结构中，数据和索引分开存储。索引是排序后的数据，而堆表中的数据是无序的，索引的叶子节点存放了数据在堆表中的地址，当堆表的数据发生改变，且位置发生了变更，所有索引中的地址都要更新，这非常影响性能，特别是对于 OLTP 业务。

而索引组织表，数据根据主键排序存放在索引中，主键索引也叫聚集索引（Clustered Index）。在索引组织表中，数据即索引，索引即数据。

MySQL InnoDB 存储引擎就是这样的数据组织方式；Oracle、Microsoft SQL Server 后期也推出了支持索引组织表的存储方式。

但是，PostgreSQL 数据库因为只支持堆表存储，不适合 OLTP 的访问特性，虽然它后期对堆表有一定的优化，但本质是通过空间换时间，对海量并发的 OLTP 业务支持依然存在局限性。

以下就是索引组织表的方式：

表 User 的主键是 id，所以表中的数据根据 id 排序存储，叶子节点存放了表中完整的记录，可以看到表中的数据存放在索引中，即表就是索引，索引就是表。

在了解完 MySQL InnoDB 的主键索引存储方式之后，接下来我们继续了解二级索引。

二级索引

InnoDB 存储引擎的数据是根据主键索引排序存储的，除了主键索引外，其他的索引都称之为二级索引（Secondeary Index）， 或非聚集索引（None Clustered Index）。

二级索引也是一颗 B+ 树索引，但它和主键索引不同的是叶子节点存放的是索引键值、主键值。对于 08 讲创建的表 User，假设在列 name 上还创建了索引 idx_name，该索引就是二级索引：

CREATE TABLE User (

    id BIGINT AUTO_INCREMENT,

    name VARCHAR(128) NOT NULL,
    sex CHAR(6) NOT NULL,
    registerDate DATETIME NOT NULL,
    ...

    PRIMARY KEY(id), -- 主键索引

    KEY idx_name(name) -- 二级索引

)

如果用户通过列 name 进行查询，比如下面的 SQL：

SELECT * FROM User WHERE name = 'David'，

通过二级索引 idx_name 只能定位主键值，需要额外再通过主键索引进行查询，才能得到最终的结果。这种“二级索引通过主键索引进行再一次查询”的操作叫作“回表”，你可以通过下图理解二级索引的查询：

索引组织表这样的二级索引设计有一个非常大的好处：若记录发生了修改，则其他索引无须进行维护，除非记录的主键发生了修改。

与堆表的索引实现对比着看，你会发现索引组织表在存在大量变更的场景下，性能优势会非常明显，因为大部分情况下都不需要维护其他二级索引。

前面我强调“索引组织表，数据即索引，索引即数据”。那么为了便于理解二级索引，你可以将二级索引按照一张表来进行理解，比如索引 idx_name 可以理解成一张表，如下所示：

CREATE TABLE idx_name (

    name VARCHAR(128) NOT NULL,
    id BIGINT NOT NULL,
    PRIAMRY KEY(name,id)

)

根据 name 进行查询的 SQL 可以理解为拆分成了两个步骤：

SELECT id FROM idx_name WHERE name = ?
SELECT * FROM User WHERE id = _id; -- 回表

当插入数据时，你可以理解为对主键索引表、二级索引表进行了一个事务操作，要么都成功，要么都不成功：

START TRANSATION;

INSERT INTO User VALUES (...) -- 主键索引
INSERT INTO idx_name VALUES (...) -- 二级索引

COMMIT;

当然，对于索引，还可以加入唯一的约束，具有唯一约束的索引称之为唯一索引，也是二级索引。

对于表 User，列 name 应该具有唯一约束，因为通常用户注册通常要求昵称唯一，所以表User 定义更新为：

CREATE TABLE User (

    id BIGINT AUTO_INCREMENT,
    name VARCHAR(128) NOT NULL,
    sex CHAR(6) NOT NULL,
    registerDate DATETIME NOT NULL,

    ...

    PRIMARY KEY(id), -- 主键索引

    UNIQUE KEY idx_name(name) -- 二级索引

)

那么对于唯一索引又该如何理解为表呢？ 其实我们可以将约束理解成一张表或一个索引，故唯一索引 idx_name 应该理解为：

CREATE TABLE idx_name (

    name VARCHAR(128) NOT NULL,
    id BIGINT NOT NULL,
    PRIAMRY KEY(name,id)

) -- 二级索引

CREATE TABLE check_idx_name (

    name VARCHAR(128),
    PRIMARY KEY(name)，

) -- 唯一约束

讲到这儿，你应该理解了吧？在索引组织表中，万物皆索引，索引就是数据，数据就是索引。

最后，为了加深你对于索引组织表的理解，我们再来回顾一下堆表的实现。

堆表中的索引都是二级索引，哪怕是主键索引也是二级索引，也就是说它没有聚集索引，每次索引查询都要回表。同时，堆表中的记录全部存放在数据文件中，并且无序存放，这对互联网海量并发的 OLTP 业务来说，堆表的实现的确“过时”了。