MySQL的索引相关
InnoDB如何存储数据的
MySQL 把数据存储和查询操作抽象成了存储引擎，不同的存储引擎，对数据的存储和读取方式各不相同。MySQL 支持多种存储引擎，并且可以以表为粒度设置存储引擎。因为支持事务，我们最常使用的是 InnoDB。
那么InnoDB 是如何存储数据的？虽然数据保存在磁盘中，但其处理是在内存中进行的。为了减少磁盘随机读取次数，InnoDB 采用页而不是行的粒度来保存数据，即数据被分成若干页，以页为单位保存在磁盘中。InnoDB 的页大小，一般是 16KB。
数据页是InnoDB中的基本存储单元，用于存储表的数据行和索引节点。每个数据页由文件头、页头、Infimum和Supremum记录、用户记录、空闲空间和页目录组成。
数据页的基本结构可以分为以下几个部分：
- 文件头（File Header）： 文件头保存了数据页的一些基本信息，比如页号、页类型等。
- 页头（Page Header）： 页头包含了数据页的管理信息，比如页面大小、空闲空间大小等。
- Infimum + Supremum Records： 这是InnoDB中特殊的记录。Infimum表示虚拟的最小记录，Supremum表示虚拟的最大记录。它们分别位于数据页的最底部和最顶部，用于指向数据页中数据行的起始和结束位置。
- 用户记录（User Records）： 用户记录是实际存储在数据页中的数据行。每个数据页可以存储多个数据行。
- 空闲空间（Free Space）： 空闲空间用于存储新增数据行或已删除数据行的内容。
- 页目录（Page Directory）： 页目录记录了数据页中数据行的位置和大小。通过页目录可以快速定位数据行。
数据页组成一个双向链表，每个数据页中的记录按照主键顺序组成单向链表；每一个数据页中有一个页目录，方便按照主键查询记录。数据页的结构如下：
页目录通过槽把记录分成不同的小组，每个小组有若干条记录。如图所示，记录中最前面的小方块中的数字，代表的是当前分组的记录条数，最小和最大的槽指向 2 个特殊的伪记录。有了槽之后，我们按照主键搜索页中记录时，就可以采用二分法快速搜索，无需从最小记录开始遍历整个页中的记录链表。
这个结构有没有很熟悉的感觉，是不是很像跳表的数据结构来查找元素的情景。
以上就是InnoDB的底层存储数据的原理
聚簇索引
说到索引，页目录就是最简单的索引，是通过对记录进行一级分组来降低搜索的时间复杂度。
但，这样能够降低的时间复杂度数量级，非常有限。当有无数个数据页来存储表数据的时候，我们就需要考虑如何建立合适的索引，才能方便定位记录所在的页。
为了解决这个问题，InnoDB 引入了 B+ 树。如下图所示，B+ 树是一棵倒过来的树：
B+ 树的特点包括：
- 最底层的节点叫作叶子节点，用来存放数据；
- 其他上层节点叫作非叶子节点，仅用来存放目录项，作为索引；
- 非叶子节点分为不同层次，通过分层来降低每一层的搜索量；
- 所有节点按照索引键大小排序，构成一个双向链表，加速范围查找。
因此，InnoDB 使用 B+ 树，既可以保存实际数据，也可以加速数据搜索，这就是聚簇索引。
如果把上图叶子节点下面方块中的省略号看作实际数据的话，那么它就是聚簇索引的示意图。
由于数据在物理上只会保存一份，所以包含实际数据的聚簇索引只能有一个。
InnoDB 会自动使用主键（唯一定义一条记录的单个或多个字段）作为聚簇索引的索引键（如果没有主键，就选择第一个不包含 NULL 值的唯一列）。上图方框中的数字代表了索引键的值，对聚簇索引而言一般就是主键。
以下是聚簇索引的一些重要特点：
- 物理存储顺序： 聚簇索引中的数据行按照索引键值的顺序在存储介质上进行物理存储，具有相近键值的数据行在物理存储上也是相邻的。
- 覆盖索引： 聚簇索引包含了所有的表数据，因此，如果查询只需要聚簇索引中包含的列，而不需要访问表的其他列，那么查询就可以通过聚簇索引进行覆盖索引扫描，避免了额外的表访问，提高了查询性能。
- 聚簇和非聚簇索引的选择： 聚簇索引对于范围查询非常高效，但是对于频繁的插入和更新操作，由于需要调整数据行的物理存储位置，可能会导致性能下降。在这种情况下，选择合适的非聚簇索引可能更有利于性能优化。
- 数据页分裂： 当一个数据页已满，再插入新的数据行时，InnoDB需要将数据页进行分裂，以便为新的数据行腾出空间。数据页分裂可能会导致数据行的物理存储位置发生变化，影响插入操作的性能。
- 聚簇索引的选择： 在设计数据库时，需要根据查询的特点、数据访问模式和性能需求来选择是否使用聚簇索引以及选择哪些列作为聚簇索引。
二级索引
为了实现非主键字段的快速搜索，就引出了二级索引，也叫作非聚簇索引、辅助索引。二级索引，也是利用的 B+ 树的数据结构，如下图所示：
这次二级索引的叶子节点中保存的不是实际数据，而是主键，获得主键值后去聚簇索引中获得数据行。这个过程就叫作回表。
举个例子，有个索引是针对用户名字段创建的，索引记录上面方块中的字母是用户名，按照顺序形成链表。如果我们要搜索用户名为 b 的数据，经过两次定位可以得出在 #5 数据页中，查出所有的主键为 7 和 6，再拿着这两个主键继续使用聚簇索引进行两次回表得到完整数据。
以下是非聚簇索引的一些重要特点：
- 数据和索引分离： 非聚簇索引将索引和数据行分开存储。索引本身保存在B+树结构中，每个节点包含键值和指向对应数据行的指针或引用。
- 物理存储顺序与索引无关： 与聚簇索引不同，非聚簇索引中的键值不决定数据行的物理存储顺序。数据行在存储介质上可能是随机分布的，这意味着通过非聚簇索引查找数据行时，可能需要进行额外的随机I/O操作。
- 覆盖索引： 非聚簇索引中除了包含索引列的键值外，还包含了指向对应数据行的引用。因此，如果查询只需要索引列的数据，而不需要访问表的其他列，那么查询可以通过非聚簇索引进行覆盖索引扫描，避免了额外的表访问，提高了查询性能。
- 辅助查询： 非聚簇索引能够加速多种类型的查询操作，比如等值查询、范围查询、排序和分组等。通过合理的非聚簇索引设计，可以优化数据库的查询性能。
- 数据页不分裂： 由于非聚簇索引不影响数据行的物理存储顺序，插入和更新数据不会导致数据页的分裂，因此，相较于聚簇索引，非聚簇索引对于插入和更新操作更友好。
索引的代价
创建二级索引的代价，主要表现在维护代价、空间代价和回表代价三个方面。
- 首先是维护代价。创建 N 个二级索引，就需要再创建 N 棵 B+ 树，新增数据时不仅要修改聚簇索引，还需要修改这 N 个二级索引。
- 其次是空间代价。虽然二级索引不保存原始数据，但要保存索引列的数据，所以会占用更多的空间。
- 最后是回表的代价。二级索引不保存原始数据，通过索引找到主键后需要再查询聚簇索引，才能得到我们要的数据。
索引覆盖
如果我们需要查询的是索引列索引或联合索引能覆盖的数据，那么查询索引本身已经“覆盖”了需要的数据，不再需要回表查询。
最后，我和你总结下关于索引开销的最佳实践吧。
- 第一，无需一开始就建立索引，可以等到业务场景明确后，或者是数据量超过 1 万、查询变慢后，再针对需要查询、排序或分组的字段创建索引。创建索引后可以使用 EXPLAIN 命令，确认查询是否可以使用索引。我会在下一小节展开说明。
- 第二，尽量索引轻量级的字段，比如能索引 int 字段就不要索引 varchar 字段。索引字段也可以是部分前缀，在创建的时候指定字段索引长度。针对长文本的搜索，可以考虑使用 Elasticsearch 等专门用于文本搜索的索引数据库。
- 第三，尽量不要在 SQL 语句中 SELECT *，而是 SELECT 必要的字段，甚至可以考虑使用联合索引来包含我们要搜索的字段，既能实现索引加速，又可以避免回表的开销。
索引失效
- 索引只能匹配列前缀。原因很简单，索引 B+ 树中行数据按照索引值排序，只能根据前缀进行比较。如果要按照后缀搜索也希望走索引的话，并且永远只是按照后缀搜索的话，可以把数据反过来存，用的时候再倒过来。
- 条件涉及函数操作无法走索引。同样的原因，索引保存的是索引列的原始值，而不是经过函数计算后的值。如果需要针对函数调用走数据库索引的话，只能保存一份函数变换后的值，然后重新针对这个计算列做索引。
- 联合索引只能匹配左边的列。原因也很简单，在联合索引的情况下，数据是按照索引第一列排序，第一列数据相同时才会按照第二列排序。也就是说，如果我们想使用联合索引中尽可能多的列，查询条件中的各个列必须是联合索引中从最左边开始连续的列。如果我们仅仅按照第二列搜索，肯定无法走索引。
基于成本是否决定走索引
查询数据可以直接在聚簇索引上进行全表扫描，也可以走二级索引扫描后到聚簇索引回表。看到这里，你不禁要问了，MySQL 到底是怎么确定走哪种方案的呢。其实，MySQL 在查询数据之前，会先对可能的方案做执行计划，然后依据成本决定走哪个执行计划。
这里的成本，包括 IO 成本和 CPU 成本：
- IO 成本，是从磁盘把数据加载到内存的成本。默认情况下，读取数据页的 IO 成本常数是 1（也就是读取 1 个页成本是 1）。
- CPU 成本，是检测数据是否满足条件和排序等 CPU 操作的成本。默认情况下，检测记录的成本是 0.2。
