MySQL：索引

本文将初步介绍MySQL数据库索引的数据结构与用处。

索引是一种用来快速查询和检索数据的数据结构。许多查询往往只涉及到数据库的一部分，比如查询出某个ID为xxx的学生，系统如果需要读取每个学生来遍历获得该条记录，那么这种操作方式无疑是低效的。在理想情况下，系统应该能直接定位这些记录。

索引底层数据结构存在很多种类型，常见的索引结构有: B 树， B+树 和 Hash、红黑树。

在 MySQL 中，无论是 Innodb 还是 MyIsam，都使用了 B+树作为索引结构。

索引底层数据结构

二叉查找树（BST）

当二叉查找树是平衡的时候，也就是树的每个节点的左右子树深度相差不超过 1 的时候，查询的时间复杂度为 O(log2(N))，具有比较高的效率。然而，当二叉查找树不平衡时，例如在最坏情况下（有序插入节点），树会退化成线性链表（也被称为斜树），导致查询效率急剧下降，时间复杂退化为 O（N）。

由于二叉查找树的性能非常依赖于它的平衡程度，这就导致其不适合作为 MySQL 底层索引的数据结构。为了解决这个问题，并提高查询效率，人们发明了多种在二叉查找树基础上的改进型数据结构，如平衡二叉树、B-Tree、B+Tree 等。

自平衡二叉查找树（AVL）

AVL 树的特点是保证任何节点的左右子树高度之差不超过 1，因此也被称为高度平衡二叉树，它的查找、插入和删除在平均和最坏情况下的时间复杂度都是 O(logn)。

由于 AVL 树需要频繁地进行旋转操作来保持平衡，因此会有较大的计算开销进而降低了查询性能。并且， 在使用 AVL 树时，每个树节点仅存储一个数据，而每次进行磁盘 IO 时只能读取一个节点的数据，如果需要查询的数据分布在多个节点上，那么就需要进行多次磁盘 IO。所以在实际应用中，AVL 树使用的并不多。

红黑树

红黑树是一种自平衡二叉查找树，通过在插入和删除节点时进行颜色变换和旋转操作，使得树始终保持平衡状态。

虽然红黑树在插入和删除节点时只需进行 O(1) 次数的旋转和变色操作，即可保持基本平衡状态，但是红黑树并不追求严格的平衡，而是大致的平衡。正因如此，红黑树的查询效率稍有下降，因为红黑树的平衡性相对较弱，可能会导致树的高度较高，这可能会导致一些数据需要进行多次磁盘 IO 操作才能查询到，这也是 MySQL 没有选择红黑树的主要原因。

B树&B+树

B 树也称 B-树,全称为多路平衡查找树。

目前大部分数据库系统及文件系统都采用 B-Tree 或其变种 B+Tree 作为索引结构。

B+树叶节点

典型的B+树叶节点会包含n-1个搜索码值（即字段值）和n个指针（指向记录或下一节点）。
示意图：（n=4）

一个叶节点必须容纳$\lceil (n-1)/2 \rceil 到 n-1$个值。

B+树非叶节点

B+树的非叶节点是叶节点之上的一个多级（稀疏）索引，其结构和叶节点相同，但是其指针均指向非叶节点。
一个非叶节点必须容纳$\lceil n/2 \rceil 到 n$个指针。一个节点中的指针数被称为扇出（fanout）。非叶节点也被称为内部节点（internal node）。（根节点的指针数可少于$\lceil n/2 \rceil$）

对于一个内部节点来说，其指针$P_i$指向的子树中，子树的最大值必须小于等于该指针后的搜索码值，子树的最小值必须大于等于该指针前的搜索码值。
示意图：（n=4）

B+树是一定平衡的，即根到叶节点的每个条路径长度都一致。

注意：上述是最好要求搜索码值是唯一的。如果不唯一，数据库会将搜索码从一个值变成一个二元组，比如nameA=nameB，那么当name字段变成搜索码时，nameA在节点中的搜索码值可能变成(nameA,0)，nameB变成(nameA,1)，以保证搜索码值唯一。如果不使用二元组替换，这将导致B+树的节点会变成一个链表，或者需要更改整个B+树的存储逻辑，过于繁琐。

B+树查询

目前不考虑搜索码值可重复的情况。

查询过程：

  1. 查询起始：
    • 查询从根节点开始，根节点始终位于内存中。
    • 根据要查找的键值，在根节点中执行二分查找或按照索引顺序查找合适的指针。
  2. 节点间导航：
    • 找到与目标键值最接近的键，对应的指针会指向下一个层级的节点。
    • 依据指针继续访问下一层级的节点，这个过程同样进行二分查找或顺序查找，不断缩小查找范围。
  3. 递归查找：
    • 重复上述步骤，沿着B+树的层级结构自顶向下移动，每次都会根据中间节点中的键值指引到更低层级的节点。
  4. 抵达叶子节点：
    • 当查询到达叶子节点时，该节点包含了实际的数据记录或者如果是辅助索引，则存储了主键值。
    • 对于精确匹配的查询，直接在叶子节点中找到键值相等的记录即可。
    • 对于范围查询，可以通过叶子节点之间的链表进行高效的顺序扫描。

在应用场景下，一个B+树节点通常可以容纳几百至上千个键值对（计算方式为：$(磁盘页大小-元数据)/(键值大小 + 指针大小)$，磁盘IO一次读出一页，即一个节点），所需磁盘IO次数为$log_{100}(X)$相比平衡二叉树中一个节点仅两个子节点的搜索效率$log_2(X)$要高非常多。

B+树更新

插入

插入：先使用查询，找到将搜索码值将出现的叶节点。然后在该叶节点的对应位置进行插入操作。
当叶子节点的值的数量在插入后大于n-1时，需要进行拆分操作，将该叶子节点拆成两个叶子节点，前一个有$\lceil n/2 \rceil$个节点，后一个有剩余的节点，然后将拆分的叶子节点添加到父节点中。如果父节点在添加了一个节点后也放不下了需要进行拆分，则继续进行拆分，在父父节点添加父节点拆成两个节点的节点，以此不断循环，如果根节点也放不下了，那么将根节点也拆分，并重新添加一个新的根节点。

示意图：

如果此时再插入一个id=7.5的记录，就会将5-7的叶子节点拆分，然后第一个内部节点需要多一个指针，就会导致第一个内部节点再次拆分，进而多出一个内部节点。（画图略）

删除

删除即是插入的逆操作，边界条件下需要将叶子节点进行合并，进而导致内部节点的合并，以致最后的减深度。（自己类推即可，不做描述）

待完善……

B树与B+树的异同

  • B 树的所有节点既存放键(key) 也存放数据(data)，而B+树只有叶子节点存放 key 和 data，其他内节点只存放 key。
  • B 树的叶子节点都是独立的；B+树的叶子节点有一条引用链指向与它相邻的叶子节点。
  • 在 B 树中进行范围查询时，首先找到要查找的下限，然后对 B 树进行中序遍历，直到找到查找的上限；而 B+树的范围查询，只需要对链表进行遍历即可。

综上，B+树与 B 树相比，具备更少的 IO 次数、更稳定的查询效率和更适于范围查询这些优势。

Hash表

哈希表可以做到快速检索数据（接近O(1)）。
MySQL 的 InnoDB 存储引擎不直接支持常规的哈希索引，但是，InnoDB 存储引擎中存在一种特殊的哈希表：自适应哈希索引（Adaptive Hash Index）。自适应哈希索引并不是传统意义上的纯哈希索引，而是结合了 B+Tree 和哈希索引的特点，以便更好地适应实际应用中的数据访问模式和性能需求。自适应哈希索引的每个哈希桶实际上是一个小型的 B+Tree 结构。这个 B+Tree 结构可以存储多个键值对，而不仅仅是一个键。这有助于减少哈希冲突链的长度，提高了索引的效率。

在MySQL运行的过程中，如果InnoDB发现，有很多寻路很长（比如B+树层数太多、回表次数多等情况）的SQL，并且有很多SQL会命中相同的页面（Page）的话，InnoDB会在自己的内存缓冲区（Buffer Pool）里，开辟一块区域，建立自适应哈希索引（Adaptive Hash Index，AHI）：一个动态创建和维护的哈希索引机制，主要目的是为了提高某些工作负载下的数据检索速度。

聚簇索引访问记录过程：

普通索引访问记录过程：

通过普通索引查询记录时，分为两步：

  1. 查询会先访问普通索引，定位到主键值9；
  2. 再通过步骤1得到的主键值，回表到聚集索引上经过二次遍历定位到具体的完整记录。

从上面的流程图可以看出，不管是聚集索引还是普通索引，记录定位的寻路路径（Search Path）都很长。回到Adaptive Hash Index的概念上：在MySQL运行的过程中，如果InnoDB发现：有很多寻路很长（比如B+树层数太多、回表次数多等情况）的SQL；有很多SQL会命中相同的页面（Page），就会建立自适应哈希索引（Adaptive Hash Index，AHI），以加速查询。

MySQL建立Adaptive Hash Index的过程：

  1. 监控与识别热点：
    • InnoDB存储引擎会持续监控缓冲池（Buffer Pool）中的页面访问模式。
    • 当发现某个索引频繁被访问时，特别是对于点查询（即通过主键或唯一二级索引查找行记录的操作），InnoDB会判断是否适合构建哈希索引以加速这类查询。
  2. 自动创建哈希索引：
    • 如果InnoDB确定建立哈希索引可以带来性能提升，它将在内存中为那些经常访问的索引页上的键值构建一个哈希索引结构。
    • 这个哈希索引是在缓冲池内部创建的，并且仅针对已经加载到内存中的索引部分。
  3. 插入与更新操作：
    • 随着DML操作（INSERT、UPDATE、DELETE）的发生，InnoDB会对相应的哈希索引进行同步更新，以确保哈希索引的正确性。
  4. 自适应调整：
    • AHI具有自适应性，意味着它可以动态地创建、删除或者调整哈希索引，完全无需数据库管理员手动干预。
    • 如果原先认为热点的索引不再频繁访问，或者由于内存压力导致缓冲池中的其他数据更需要空间，InnoDB会自动移除不再高效的哈希索引。

在Adaptive Hash Index中，Key就是经常访问到的索引键值，Value就是该索引键值匹配的完整记录所在页面（Page）的位置。因为是MySQL InnoDB自己维护创建的，所以称之为“自适应”哈希索引。

在一般的哈希索引中，如果出现哈希冲突（即两个不同的键经过哈希函数计算后映射到同一个槽位），通常采用链表或其他方法链接冲突的键值对。但在InnoDB的AHI中，为了避免长链表带来的性能下降，特别是在内存有限且热点数据冲突较多的情况下，选择将哈希冲突的键值对组织成B+树结构。这样做的好处是：

  • 尽管AHI仍然是哈希索引的形式，但是B+树的特性使得即使在哈希冲突的情况下也能保持相对稳定的时间复杂度（O(log n)）来查找数据，相比于单纯的链表查询效率更高。
  • B+树天然支持范围查找，尽管AHI主要用于点查优化，但如果因为哈希冲突导致的键值分布在一个桶内，那么在这个小规模的B+树上进行局部范围查找也是可行的，这比纯哈希索引更有优势。

索引类型

评价一个索引的因素：

  • 访问类型：能有效支持的访问类型，如找到某个值、找到某个范围内的值。
  • 访问时间：使用该索引找到一个值或一个值的集合所需要的时间。
  • 插入时间：通过该索引，插入一个数据项的时间+插入后更新索引的时间。
  • 删除时间：通过该索引，找到该数据项并删除的时间+删除后更新索引的时间。
  • 空间花销：索引结构所需空间。

搜索码：用于在文件中查找记录的属性或属性集被称为搜索码（search key）。如果一个文件有多个索引，则它就有多个搜索码。
索引项（index entry）：又称索引记录（index record），由一个搜索码值和指针构成。指针会指向该搜索码值对应的一条或多条记录。

顺序索引

顺序索引（ordered index）：基于值的顺序排序。

散列索引（hash index）：基于将值平均分布到若干桶中。值对应的桶由散列函数决定。

顺序索引有两类：

  • 稠密索引（dense index）：每个搜索码值（即字段值）都被一个索引项所指向。具有相同搜索码值的其余记录会顺序地排序在第一条记录后。
  • 稀疏索引（sparse index）：只为某些搜索码值建立索引。只有聚集索引才能使用稀疏索引。当定位记录时，从最大搜索码值小于或等于所搜索的记录的搜索码值的索引项开始遍历，直到找到为止。

稠密索引示意图：

稀疏索引示意图：

聚集索引

聚集索引（clustering index）：又称主索引（primary index），搜索码定义了文件的次序。
非聚集索引（nonclustering index）：又称辅助索引（secondary index），搜索码的次序与文件的排序次序不同。

多级索引

注意：多级索引同时适用于索引顺序文件和B+树，只不过索引顺序文件中是外层索引块，B+树中是非叶节点。

如果索引很小，就可以放在主存中，这样查找一个索引项的速度就会很快。但是如果索引很大，就会导致需要将其放在磁盘中，进而导致当使用索引进行搜索时，需要进行多次磁盘IO（尤其是使用二分法搜索索引时，可能导致$log_2(n)$次的磁盘IO）。多级索引就是为了解决这个问题。
假设有1000000条记录，一个索引块可保存100条索引项，那么就会存在10000个索引块。（一个块可能是4KB）
当进行查找时，二分法需要14次磁盘的随机读才能找到对应的索引块，这可能需要0.1s的时间。

为此，我们需要加快找到索引块的方式，多级索引就是一种方案。
索引项总是顺序排序的，我们将索引文件也看做是顺序文件，并对索引块再次建立一层稀疏索引：
示意图：

好了，假设一样是10000个索引块，现在通过外层索引（将原先的索引称为内层索引），我们只需要100个外层索引块即可建立指向10000索引项的的外层索引项，并且在读取某一个记录时，只需要查找外层索引→内层索引→数据块即可，仅一次内存访问和两次磁盘IO操作。
如果有更多的记录，我们同样可以继续建立更外层的索引。

覆盖索引

如果一个索引包含（或者说覆盖）所有需要查询的字段的值，我们就称之为覆盖索引（Covering Index）。
我们知道在 InnoDB 存储引擎中，如果不是主键索引，叶子节点存储的是主键+列值。最终是要执行“回表”操作的，也就是要通过主键再查找一次。
而覆盖索引即需要查询的字段正好是索引的字段，那么直接根据该索引，就可以查到数据了，而无需回表查询。

联合索引

使用表中的多个字段创建索引，就是联合索引，也叫组合索引或复合索引。

如果有这样一个索引定义在table (col1, col2, col3)上，那么索引记录将是按照col1升序排列，对于col1相等的记录，则按照col2升序排列，以此类推。

最左前缀匹配原则

  • 最左前缀匹配原则意味着只要查询条件中包含了索引的最左侧列（这里是A），就可以利用索引来优化查询。也就是说，不只是查询条件只包括A列时能使用索引，当查询条件包含A和B（即A=? AND B=?），或者A、B和C（即A=? AND B=? AND C=?）时，都可以利用这个联合索引来加快查询速度。
  • 但是如果查询条件只包含B或C（即B=? 或B=? AND C=?），因为(a, b, c) 是联合索引，是先按 a 排序，在 a 相同的情况再按 b 排序，在 b 相同的情况再按 c 排序。所以，b 和 c 是全局无序，局部相对有序的，这样在没有遵循最左匹配原则的情况下，是无法利用到索引的。

最左匹配原则会一直向右匹配直到遇到范围查询(>、<、between、like) 就会停止匹配。

  • 向右匹配的概念是，一旦满足最左列的条件后，数据库会继续检查下一个索引列（即从左到右），只要查询条件允许。
  • 停止匹配原则在于，如果查询条件中出现了一个范围查询（如A > ?、A < ?、B BETWEEN ? AND ?等），那么在遇到这个范围查询的列之后的索引列将不再用于索引查找。例如，对于上述索引，若查询条件为A = ? AND B > ? AND C = ?，虽然A列和B列都能利用索引，但由于B列进行了范围查询，因此C列将不会使用索引来优化查询，数据库系统可能需要进行额外的全表扫描或其他操作来获取满足C列条件的记录。

注意，如果范围查询中，存在确定情况下的记录（即>=、<=、Between…and…、like导致的$[a,b)$区间），则在刚好=的情况下，范围查询索引右侧的索引仍旧可以起效，但是如果是不确定的情况（即>、<、like中去除了a后的$(a,b)$），则会停止匹配。
比如条件为a>=1 and b=1，针对a=1的记录，判定b时仍然可使用联合索引；但是对于a>1的记录，则只能使用联合索引中a的部分。
相关来源：小林coding

索引失效场景

  1. 联合索引失效
    • 未符合联合索引要求的最左前缀匹配原则（即不包含联合索引最左侧的字段）。
      • 注意：MySQL8新增索引跳跃扫描的功能，即第一列索引的唯一值较少时，即使 where 条件没有第一列索引，查询的时候也可以用到联合索引。
    • 向右匹配时遇到范围查询。
  2. where范围过大
    • where查询范围过大，可能导致MySQL最优选择全表扫描，进而导致索引失效。
  3. where条件中包含函数或计算
    • 由于索引保存的是索引字段的原始值，而不是经过函数/计算后的值，自然就没办法走索引了。
      • 注意：MySQL 8.0 开始，索引特性增加了函数索引，可以针对函数计算后的值建立一个索引。
  4. like %…
    • 范围过大造成索引没有意义从而失效的情况。
  5. 条件包含or导致失效
    • 如果在OR前的条件列是索引列，而在OR后的条件列不是索引列，那么索引会失效，因为验证后一个条件是需要遍历全表的。
      • 在Or的条件中两边都加上索引，即可避免全表扫描。
  6. (not) in …
    • 当IN的取值范围较大时会导致索引失效，走全表扫描，与like %…类似。
  7. order By
    • 在需要排序的场景下，存在两种策略：
      • 索引+回表：走索引，索引是排好序的，但是需要回表。
      • 全表扫描：直接全表扫描排序，不用回表。
    • MySQL认为后一种效率更高，因此orderBy情况下索引会失效。