索引

1. 索引数据结构

什么是索引？为什么索引能加快查询？

索引是数据库中一种特殊的数据结构，它像书籍的目录一样，能帮助数据库系统快速定位和访问数据。索引能加快查询的原因在于：

减少数据访问量：通过索引，数据库只需要访问包含目标数据的部分，而不是扫描整个表。
有序存储：索引中的数据是按照特定顺序存储的，使得搜索、排序和分组操作更高效。
快速定位：使用树形结构等高效的数据结构，可以在大量数据中快速定位目标记录。

没有索引时，数据库需要进行全表扫描，时间复杂度为O(n)；而使用索引后，查询时间复杂度可降至O(log n)。

B+ 树和（B 树和红黑树）有什么区别？为什么选择用 B+ 树作为索引数据结构？

图片来自：https://xiaolincoding.com/mysql/index/why_index_chose_bpuls_tree.html#%E6%80%8E%E6%A0%B7%E7%9A%84%E7%B4%A2%E5%BC%95%E7%9A%84%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E6%98%AF%E5%A5%BD%E7%9A%84

由于树是存储在磁盘中的，访问每个节点，都对应一次磁盘 I/O 操作(假设一个节点的大小「小于」操作系统的最小读写单位块的大小)，也就是说树的高度就等于每次查询数据时磁盘 IO 操作的次数，所以树的高度越高，就会影响查询性能。

要设计一个适合 MySQL 索引的数据结构，至少满足以下要求：

能在尽可能少的磁盘的 I/0 操作中完成查询工作;
要能高效地查询某一个记录，也要能高效地执行范围查找，

如果主键按照顺序排列的话，可以通过二分查找高效定位数据，使得时间复杂度变为O(log n)。

用数组来实现线性排序的数据虽然简单好用，但是插入新元素的时候性能太低。因为插入一个元素，需要将这个元素之后的所有元素后移一位，如果这个操作发生在磁盘中呢?这必然是灾难性的。因为磁盘的速度比内存慢几十万倍，所以我们不能用一种线性结构将磁盘排序。因此作为修改，二叉查找树诞生了。

它同时解决了查找和插入的问题，但是也有新的毛病，那就是在极端情况下（插入的永远是最大/小项时），二叉搜索树会退化为单链表。

于是又引入平衡二叉查找树解决这个问题，它能够实现自平衡，自动调整树结构，使每个节点的左子树和右子树的高度差不能超过 1：

红黑树的原理和其类似，这里不赘述。但问题是，这里一个节点还是只有两个子节点，当树的高度变大时，还是太吃磁盘的IO操作次数了。那么还有没有更加简单的打法呢？

有的兄弟有的，B树来咯！

为了解决降低树的高度的问题，后面就出来了B树，它不再限制一个节点就只能有2个子节点，而是允许M 个子节点 (M>2)，从而降低树的高度。

B树的每一个节点最多可以包括 M 个子节点，M 称为 B树的阶，所以 B树就是一个多又树。假设 M =3，那么就是一棵3阶的B树，特点就是每个节点最多有2个(M-1个)数据和最多有3个(M个)子节点，超过这些要求的话，就会分裂节点，比如下面的的动图:

问题又来了， B树的每个节点都包含数据(索引+记录)，而用户的记录数据的大小很有可能远远超过了索引数据，这就需要花费更多的磁盘 IO操作次数来读到「有用的索引数据」。

而且，在我们查询位于底层的某个节点(比如 A 记录)过程中，「非A记录节点」里的记录数据会从磁盘加载到内存，但是这些记录数据是没用的，我们只是想读取这些节点的索引数据来做比较查询，而「非A记录节点」里的记录数据对我们是没用的，这样不仅增多磁盘 IO 操作次数，也占用内存资源。

另外，如果使用B树来做范围查询的话，需要使用中序遍历，这会涉及多个节点的磁盘 IO 问题，从而导致整体速度下降。

因此，B+树诞生了。

B+ 树与 B 树差异的点，主要是以下这几点:

叶子节点(最底部的节点)才会存放实际数据(索引+记录)，非叶子节点只会存放索引；
所有索引都会在叶子节点出现，叶子节点之间构成一个有序链表；
非叶子节点的索引也会同时存在在子节点中，并且是在子节点中所有索引的最大(或最小)；
非叶子节点中有多少个子节点，就有多少个索引。

但是 Innodb 使用的 B+ 树有一些特别的点，比如:

B+ 树的叶子节点之间是用「双向链表」进行连接，这样的好处是既能向右遍历，也能向左遍历。
B+树节点内容是数据页，数据页里存放了用户的记录以及各种信息，每个数据页默认大小是 16 KB.

Innodb 根据索引类型不同，分为聚簇和二级索引。他们区别在于:

·聚簇索引的叶子节点存放的是实际数据，所有完整的用户记录都存放在聚簇索引的叶子节点，而二级索引的叶子节点存放的是主键值，而不是实际数据。
因为表的数据都是存放在聚簇索引的叶子节点里，所以 InnoDB 存储引擎一定会为表创建一个聚簇索引且由于数据在物理上只会保存一份，所以聚簇索引只能有一个，而二级索引可以创建多个。

总结：

2. 索引存储

堆表和索引组织表有什么区别？分别应用场景是什么？

图片来自：https://learn.lianglianglee.com/%E4%B8%93%E6%A0%8F/MySQL%E5%AE%9E%E6%88%98%E5%AE%9D%E5%85%B8/09%20%20%E7%B4%A2%E5%BC%95%E7%BB%84%E7%BB%87%E8%A1%A8%EF%BC%9A%E4%B8%87%E7%89%A9%E7%9A%86%E7%B4%A2%E5%BC%95.md
堆表和索引组织表的区别其实也是MyISAM和InnoDB的区别的一部分，因为它们与这两个存储引擎的实现方式分别对应。

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

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

而索引组织表，数据根据主键排序存放在索引中，主键索引也叫聚集索引（Clustered Index）。在索引组织表中，数据即索引，索引即数据。并且二级索引只需要通过回表的方式进行数据查询，而不用修改其他的索引，这非常的方便。

值得提的是，每种不同数据对二级索引的性能开销影响是不一样的。要比较顺序，对聚集索引性能友好；尽可能紧凑，对二级索引的性能和存储友好；

堆表与索引组织表的区别：

堆表（Heap Table）：
- 数据行没有特定顺序，按照插入顺序存储
- 通过行ID（ROWID）或物理位置进行访问
- 插入操作简单快速，无需维护顺序
索引组织表（Index-Organized Table，IOT）：
- 数据按主键顺序存储
- 表数据本身就是按B+树组织的
- 表和主键索引在物理上是同一个结构

应用场景：

堆表:

当表主要进行大量的插入操作/全表扫描，并且对检索性能的要求相对较低时，堆表是一个合适的选择。

索引组织表:

当表主要进行范围查询、按索引检索以及有序的数据检索时，索引组织表通常更适用。在这种情况下通过索引直接访问有序的数据行可以提高查询效率。

3. 联合索引与索引覆盖

联合索引的结构是怎样的？

联合索引（Compound Index）是指由多个列所组合而成的 B+树索引，这和我们之前介绍的B+ 树索引的原理完全一样，只是之前是对一个列排序，现在是对多个列排序。

联合索引既可以是主键索引，也可以是二级索引，下图显示的是一个二级联合索引：

联合索引的 B+ 树结构

从上图可以看到，联合索引只是排序的键值从 1 个变成了多个，本质还是一颗 B+ 树索引。但是你一定要意识到（a，b）和（b，a）这样的联合索引，其排序结果是完全不一样的。而索引的字段变多了，设计上更容易出问题，如：

对联合索引（a，b）来说，因为其对列 a、b 做了排序，所以它可以对下面两个查询进行优化：

1
2
3

SELECT * FROM table WHERE a = ?

SELECT * FROM table WHERE a = ？ AND b = ？

上述 SQL 查询中，WHERE 后查询列 a 和 b 的顺序无关，即使先写 b = ? AND a = ？依然可以使用联合索引（a，b）。

但是下面的 SQL 无法使用联合索引（a，b），因为（a，b）排序并不能推出（b，a）排序：

1	SELECT * FROM table WHERE b = ?

此外，同样由于索引（a，b）已排序，因此下面这条 SQL 依然可以使用联合索引（a，b），以此提升查询的效率：

1	SELECT * FROM table WHERE a = ？ ORDER BY b DESC

同样的原因，索引（a，b）排序不能得出（b，a）排序，因此下面的 SQL 无法使用联合索引（a，b）：

1	SELECT * FROM table WHERE b = ？ ORDER BY a DESC

索引覆盖

由于二级组合索引的叶子节点，包含索引键值和主键值，若查询的字段在二级索引的叶子节点中，则可直接返回结果，无需回表。这种通过组合索引避免回表的优化技术也称为索引覆盖（Covering Index）。

如下面的SQL语句：

EXPLAIN FORMAT=tree 

SELECT o_custkey,o_orderdate,o_totalprice 

FROM orders WHERE o_custkey = 147601\G

*************************** 1. row ***************************

EXPLAIN: -> Index lookup on orders using idx_custkey_orderdate (O_CUSTKEY=147601)  (cost=6.65 rows=19)

cost=6.65 表示的就是这条 SQL 当前的执行成本。不用关心 cost 的具体单位，你只需明白cost 越小，开销越小，执行速度越快。

如果想要避免回表，可以通过索引覆盖技术，创建(o_custkey，o_orderdate，o_totalprice）的组合索引，如：

1
2
3

ALTER TABLE `orders` ADD INDEX

idx_custkey_orderdate_totalprice(o_custkey,o_orderdate,o_totalprice);

再次观察 SQL 的执行成本，可以看到 cost 有明显的下降，从 6.65 下降为了 2.94：

EXPLAIN FORMAT=tree 

SELECT o_custkey,o_orderdate,o_totalprice 

FROM orders WHERE o_custkey = 147601\G

*************************** 1. row ***************************

EXPLAIN: -> Index lookup on orders using idx_custkey_orderdate_totalprice (O_CUSTKEY=147601)  (cost=2.94 rows=19)

效果显著！

如何利用联合索引提升查询性能？

利用联合索引提升性能的策略：

遵循最左前缀原则：
- 查询条件必须包含索引的第一列
- 如有索引(A,B,C)，可以使用A、AB、ABC组合查询
合理设计索引顺序：
- 把选择性高的列放在前面
- 把常用于等值查询的列放在前面
- 把范围查询的列放在最后
避免索引失效情况：
- 不在索引列上使用函数或表达式
- 避免使用NOT、!=、<>等操作符
- 避免隐式类型转换
- 注意通配符使用位置（前缀通配符会导致索引失效）
覆盖索引技巧：
- 将经常查询的列都包含在索引中
- 可以实现”索引覆盖”，避免回表操作
适当冗余索引：
- 为不同查询场景创建专用索引
- 平衡索引数量与性能需求

通过合理设计和使用联合索引，可以显著提升查询性能，减少磁盘IO和CPU开销，尤其在大型数据库系统中效果更为明显。

通过这道题，我来详细解释一下索引下推（Index Condition Pushdown, ICP）：

什么是索引下推？

索引下推是MySQL 5.6引入的查询优化技术，它允许存储引擎层在遍历索引时，就对索引中包含的字段进行条件判断，从而减少不必要的回表操作。

用题目中的例子说明

**例2：`select \* from T where a=1 and b>2 and c=3`**

对于联合索引(a,b,c)：

a和b 可以用于索引定位（最左匹配原则）
c 无法用于索引定位（因为b是范围查询，打断了连续性）
但c可以进行索引下推

没有索引下推时的执行过程：

1. 在索引树中找到所有 a=1 and b>2 的记录
2. 对每条记录都回表，读取完整行数据
3. 在Server层判断 c=3 是否满足
4. 返回符合条件的结果

有索引下推时的执行过程：

1. 在索引树中找到所有 a=1 and b>2 的记录
2. 在索引树中就判断 c=3 是否满足（索引下推）
3. 只有满足 c=3 的记录才回表
4. 返回符合条件的结果

**例4：`select \* from T where a=2 and c=3`**

a 可以走索引
c 无法走索引（跳过了b，不符合最左匹配）
但c可以被索引下推

优化效果： 假设有100条 a=2 的记录，但只有10条同时满足 c=3

没有ICP：需要回表100次
有ICP：只需要回表10次

索引下推的关键点

只适用于二级索引（辅助索引）
只能下推索引中包含的字段：对于联合索引(a,b,c)，只有a、b、c这三个字段可以下推
减少回表次数：在索引层就过滤掉不符合条件的记录
提高查询性能：特别是当回表操作代价较大时

验证方式

在MySQL中可以通过EXPLAIN查看是否使用了索引下推：

1	EXPLAIN SELECT * FROM T WHERE a=1 AND b>2 AND c=3;

如果Extra列显示 **”Using index condition”**，说明使用了索引下推。

索引下推是MySQL优化器的一个智能特性，能自动判断何时使用，无需手动干预，但了解它的原理有助于我们更好地设计索引和优化查询。