【肝帝一周总结：全网最全最细】☀️Mysql 索引数据结构详解与索引优化☀️《❤️记得收藏❤️》

🏳️‍🌈1、索引

在关系数据库中，索引是一种单独的、物理的对数据库表中一列或多列的值进行排序的一种存储数据结构，它是某个表中一列或若干列值的集合和相应的指向表中物理标识这些值的数据页的逻辑指针清单。

索引的作用相当于图书的目录，可以根据目录中的页码快速查找到所需的内容。

在 MySQL 中，存储引擎用类似的方法使用索引，先在索引中找到对应值，然后根据匹配的索引记录找到对应的行。

首先说明下 MySQL 的索引主要是基于 Hash 表或者 B + 树。

🚣2、索引数据结构

了解索引就需要从索引常见的数据结构开始了解学习，这里有集中常见的的索引数据结构。

🗾二叉树（Binary Trees）

二叉树是每个节点最多只有两个分支（即不存在分支度大于 2 的节点）的树结构。通常被称之为 “左子树” 和 “右子树”

在这里插入图片描述

左子树 < 父节点 <= 右子树

二叉树的第 i 层至多有有 2^(i-1) 个节点，

深度为 K 的二叉树至多总共有个 2^k-1 节点（定义根节点所在深度 k0=0），而总计拥有节点数符合的，称为 “满二叉树”；

二叉树通常作为数据结构应用，典型用法是对节点定义一个标记函数，将一些值与每个节点相关系。这样标记的二叉树就可以实现二叉搜索树和二叉堆，并应用于高效率的搜索和排序。

同时学习数据结构，这里还推荐 Data Structure Visualizations 进行学习，可以非常直观的看到数据结构允许的过程，一步一步的怎么走的都可以很清晰看得到。

找到其中的 Binary Search Trees 二叉树。

在这里插入图片描述

可以直观的看到二叉树的数据插入过程，如下：

在这里插入图片描述

可以看到二叉树不适合用作当作索引的，数据量庞大的话，二叉树的层数会很大，查找效率固然也很慢了。 推荐阅读：维基百科 - 二叉树

🏔️红黑树（Red-Black Trees）

是一种自平衡二叉查找树，典型用途是实现关联数组。

红黑树的结构复杂，但它的操作有着良好的最坏情况运行时间，并且在实践中高效：它可以在 O (log n) 时间内完成查找，插入和删除，这里的 n 是树中元素的数目。

红黑树遵行以下原则：

• 节点是红色或黑色。
• 根是黑色。
• 所有叶子都是黑色（叶子是 NIL 节点）。
• 每个红色节点必须有两个黑色的子节点。（从每个叶子到根的所有路径上不能有两个连续的红色节点。）
• 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。

下面是一个具体的红黑树的图例：

在这里插入图片描述

这些约束确保了红黑树的关键特性：从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这个树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例，这个在高度上的理论上限允许红黑树在最坏情况下都是高效的，而不同于普通的二叉查找树。

要知道为什么这些性质确保了这个结果，注意到性质 4 导致了路径不能有两个毗连的红色节点就足够了。最短的可能路径都是黑色节点，最长的可能路径有交替的红色和黑色节点。因为根据性质 5 所有最长的路径都有相同数目的黑色节点，这就表明了没有路径能多于任何其他路径的两倍长。

同样在 Data Structure Visualizations 中选择 Red-Black Trees 红黑树进行插入操作可以直观的看到红黑树的插入过程：

在这里插入图片描述

同样红黑树也不适用于 MySQL 的索引，数据量庞大之后，数层也会变大。

推荐阅读：

维基百科 - 红黑树

⛰️其他结构的问题

由于无法装入内存，则必然依赖磁盘（或 SSD）存储。而内存的读写速度是磁盘的成千上万倍（与具体实现有关），因此，核心问题是 “如何减少磁盘读写次数”。

首先不考虑页表机制，假设每次读、写都直接穿透到磁盘，那么：

• 线性结构：读 / 写平均 O (n) 次
• 二叉搜索树（BST）：读 / 写平均 O (log2 (n)) 次；如果树不平衡，则最差读 / 写 O (n) 次
• 自平衡二叉搜索树（AVL）：在 BST 的基础上加入了自平衡算法，读 / 写最大 O (log2 (n)) 次
• 红黑树（RBT）：另一种自平衡的查找树，读 / 写最大 O (log2 (n)) 次

BST、AVL、RBT 很好的将读写次数从 O (n) 优化到 O (log2 (n))；其中，AVL 和 RBT 都比 BST 多了自平衡的功能，将读写次数降到最大 O (log2 (n))。

假设使用自增主键，则主键本身是有序的，树结构的读写次数能够优化到树高，树高越低读写次数越少；自平衡保证了树结构的稳定。如果想进一步优化，可以引入 B树和 B+树。

🌋B 树（B-Trees）

又称：多路平衡查找树。大多数存储引擎都支持 B 树索引。b 树通常意味着所有的值都是按顺序存储的，并且每一个叶子节点到根的距离相同。B 树索引能够加快访问数据的速度，因为存储引擎不再需要进行全表扫描来获取数据。下图就是一颗简单的 B 树。

在 B 树中，内部（非叶子）节点可以拥有可变数量的子节点（数量范围预先定义好）。当数据被插入或从一个节点中移除，它的子节点数量发生变化。为了维持在预先设定的数量范围内，内部节点可能会被合并或者分离。

如下图所示：

在这里插入图片描述

• 叶节点具有相同的深度，叶节点的指针为空
• 所有索引元素不重复
• 节点中的数据索引从左到右递增排列
• 无论中间节点还是叶子节点都带有卫星数据 data（索引元素所指向的数据记录）

只演示了插入的过程，其中可以通过 delete、find 执行删除和查找操作。直观的感受到 B 树的执行过程。

每个节点存储了多个 Key 和子树，子树与 Key 按顺序排列。

同二叉搜索树类似，每个节点存储了多个 key 和子树，子树与 key 按顺序排列。

页表的目录是扩展外存 + 加速磁盘读写，一个页（Page）通常 4K（等于磁盘数据块 block 的大小，见 inode 与 block 的分析），操作系统每次以页为单位将内容从磁盘加载到内存（以摊分寻道成本），修改页后，再择期将该页写回磁盘。考虑到页表的良好性质，可以使每个节点的大小约等于一个页（使 m 非常大），这每次加载的一个页就能完整覆盖一个节点，以便选择下一层子树；对子树同理。对于页表来说，AVL（或 RBT）相当于 1 个 key+2 个子树的 B 树，由于逻辑上相邻的节点，物理上通常不相邻，因此，读入一个 4k 页，页面内绝大部分空间都将是无效数据。

假设 key、子树节点指针均占用 4B，则 B 树节点最大 m * (4 + 4) = 8m B；页面大小 4KB。则 m = 4 * 1024 / 8m = 512，一个 512 叉的 B 树，1000w 的数据，深度最大 log(512/2)(10^7) = 3.02 ~= 4。对比二叉树如 AVL 的深度为 log(2)(10^7) = 23.25 ~= 24，相差了 5 倍以上。震惊！B 树索引深度竟然如此！

那为什么 B 数这么厉害了，还有 B + 树的出现呢，必然是解决 B 树存在的问题

1、为定位行数

2、无法处理范围查询

🗻问题 1：为定位行数

数据表的记录有多个字段，仅仅定位到主键是不够的，还需要定位到数据行。有 3 个方案解决：

• 直接将 key 对应的数据行（可能对应多行）存储子节点中。
• 数据行单独存储；节点中增加一个字段，定位 key 对应数据行的位置。
• 修改 key 与子树的判断逻辑，使子树大于等于上一 key 小于下一 key，最终所有访问都将落于叶子节点；叶子节点中直接存储数据行或数据行的位置。

方案 1 直接 pass，存储数据行将减少页面中的子树个数，m 减小树高增大。

方案 2 的节点中增加了一个字段，假设是 4B 的指针，则新的 m = 4 * 1024 / 12m = 341.33 ~= 341，深度最大 log(341/2)(10^7) = 3.14 ~= 4。

方案 3 的节点 m 与深度不变，但时间复杂度变为稳定的 O (logm (n))。

个人认为优先选择的方案 3 。

🏕️问题 2：无法处理范围查询

实际业务中，范围查询的频率非常高，B 树只能定位到一个索引位置（可能对应多行），很难处理范围查询。改动较小的是 2 个方案：

• 不改动；查询的时候先查到左界，再查到右界，然后 DFS（或 BFS）遍历左界、右界之间的节点。
• 在 “问题 1 - 方案 3” 的基础上，由于所有数据行都存储在叶子节点，B 树的叶子节点本身也是有序的，可以增加一个指针，指向当前叶子节点按主键顺序的下一叶子节点；查询时先查到左界，再查到右界，然后从左界到有界线性遍历。

乍一看感觉方案 1 比方案 2 好 —— 时间复杂度和常数项都一样，方案 1 还不需要改动。但是别忘了局部性原理，不管节点中存储的是数据行还是数据行位置，方案 2 的好处在于，依然可以利用页表和缓存预读下一节点的信息。而方案 1 则面临节点逻辑相邻、物理分离的缺点。

推荐阅读：

维基百科 - B 树

🏖️B + 树（B+Trees）

主要变动如上所述：

• 修改 key 与子树的组织逻辑，将索引访问都落到叶子节点。
• 按顺序将叶子节点串起来（方便范围查询）。

回顾上一个 B 树，一个 m 阶的 B 树具有如下几个特征：

1、根结点至少有两个子女。

2、每个中间节点都包含 k-1 个元素和 k 个孩子，其中 m/2 <= k <= m。

3、每一个叶子节点都包含 k-1 个元素，其中 m/2 <= k <= m。

4、所有的叶子结点都位于同一层。

5、每个节点中的元素从小到大排列，节点当中 k-1 个元素正好是 k 个孩子包含的元素的值域分划。

一个 m 阶的 B + 树具有如下几个特征：

1、有 k 个子树的中间节点包含有 k 个元素（B 树中是 k-1 个元素），每个元素不保存数据，只用来索引，所有数据都保存在叶子节点。

2、所有的叶子结点包含了全部元素的信息，及指向含这些元素记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。

3、所有的中间节点元素都同时存在于子节点，在子节点元素中是最大（或最小）元素。

🏜️B + 树特性总结

B + 树是 B 树的升级版，其有如下特性：

• 非叶子节点不存储 data，只存储索引 (冗余)，可以放更多的索引。
• 叶子节点包含所有索引字段。
• 叶子节点用指针连接，提高区间访问的性能。
• 只有叶子节点带有卫星数据 data（索引元素所指向的数据记录）。

在这里插入图片描述

同样在 Data Structure Visualizations 中选择 B+ TreesB + 树进行插入操作可以直观的看到插入过程

在这里插入图片描述

在动图中可以看出，B + 树的每一个叶子节点都有一个指针指向下一个节点，把所有的叶子节点串在一起。索引数据都存储在叶子节点中。

B + 树相比于 B 树，有什么优势呢：

1、单一节点存储更多的元素，使得查询的 IO 次数更少。

2、所有查询都要查找到叶子节点，查询性能稳定。

3、所有叶子节点形成有序链表，便于范围查询。

总结，B + 树相比 B 树的优势有三：1.IO 次数更少；2. 查询性能稳定；3. 范围查询简便。

推荐阅读：

维基百科 - B + 树

🏝️Hash 索引

hash 索引基于 hash 表实现，Hash 索引是将索引键通过 Hash 运算之后，将 Hash 运算结果的 Hash 值和所对应的行指针信息存放于一个 Hash 表中。只有精准匹配索引所有列的查询才有效。索引的检索可以一次定位，不像 B-Tree 索引需要从根节点出发到目标节点。虽然 Hash 索引很快，远高于 B-tree 索引，但是也有其弊端。

• Hash 索引仅仅能满足’=’,’IN’,’<=>’查询，也就是等值查询，不能使用范围查询。很受限。
• 由于 Hash 索引比较的是进行 Hash 运算之后的 Hash 值，所以它只能用于等值的过滤，不能用于基于范围的过滤，因为经过相应的 Hash 算法处理之后的 Hash 值的大小关系，并不能保证和 Hash 运算前完全一样。
• 由于 Hash 索引是通过 hash 表实现，其本身是没有排序的。
• 由于 Hash 索引中存放的是经过 Hash 计算之后的 Hash 值，而且 Hash 值的大小关系并不一定和 Hash 运算前的键值完全一样，所以数据库无法利用索引的数据来避免任何排序运算。
• Hash 索引不能利用部分索引键查询。
• 对于组合索引，Hash 索引在计算 hash 值的时候是组合索引键合并后再一起计算 hash 值，而不是单独计算 hash 值，所以通过组合索引的前面一个或几个索引键进行查询的时候，Hash 索引也无法被利用。
• Hash 索引在任何时候都不能避免表扫描。
• 前面已经知道，Hash 索引是将索引键通过 Hash 运算之后，将 Hash 运算结果的 Hash 值和所对应的行指针信息存放于一个 Hash 表中，由于不同索引键存在相同 Hash 值，所以即使取满足某个 Hash 键值的数据的记录条数，也无法从 Hash 索引中直接完成查询，还是要通过访问表中的实际数据进行相应的比较，并得到相应的结果。
• Hash 索引遇到大量 Hash 值相等的情况后性能并不一定就会比 B-Tree 索引高。
• 对于选择性比较低的索引键，如果创建 Hash 索引，那么将会存在大量记录指针信息存于同一个 Hash 值相关联。这样要定位某一条记录时就会非常麻烦，会浪费多次表数据的访问，而造成整体性能低下。

🏞️3、MySQL 数据库引擎

通过 navicat 工具查看表设计选项中，从引擎中可以看到 MySQL 又这么多引擎。具体细分到每个表，不同的表引擎可以不一样。

在这里插入图片描述

🏟️MyISAM

新建一张表 t_test_myisam，引擎使用 MyISAM，查看原文件可以看到有 3 个文件

在这里插入图片描述

可以看到索引和数据是分开的，其中索引文件仅仅保存数据记录的地址，故属于非聚簇索引。

主键索引（Primary Index）

MyISAM 引擎使用 B+Tree 作为索引结构，叶节点的 data 存放的是数据记录的地址。如下图是 MyISAM 主键索引的原理图。

在这里插入图片描述

其中 Col1 为主键，可以看出看出 MyISAM 的索引文件仅保存数据记录的地址。

辅助索引（Secondary Index）

在 Col2 上建立一个辅助索引，如下图辅助索引原理图。

在这里插入图片描述

可以看到与主键索引没有任何区别，只不过主键索引的 key 是唯一的，而辅助索引的 key 可以重复。

MyISAM 中索引检索的算法为首先按照 B+Tree 搜索算法搜索索引，如果指定的 Key 存在，则取出其 data 域的值，然后以 data 域的值为地址，读取相应数据记录。

其中三个字段就是联合索引。

由于联合索引的出现，key 由多个列组成，列的排序决定了可命中索引的列数。也叫最左前缀匹配。

索引只能用于查找 key 是否存在（相等），遇到范围查找（>,<,=,between,like 左匹配）等就不能进一步匹配。

🏛️InnoDB

新建一张表 t_test_innodb，引擎使用 InnoDB，查看原文件可以看到有 2 个文件

在这里插入图片描述

主键索引（Primary Index）

InnoDB 的索引和数据在一个文件当中。

按照 B+Tree 组织的一个索引结构。

叶节点保存了完整的数据记录和索引。这种索引就叫做聚簇索引。

索引的 Key 是数据的主键，因此 InnoDB 表数据文件本身就是主索引。

如下图：

在这里插入图片描述

可以看到叶节点包含了完整的数据记录。

因为 InnoDB 的数据文件本身要按照主键聚集，所以 InnoDB 要求必须有主键。如果没有显式指定，则 MySQL 系统会自动选择一个可以唯一标识数据记录的列作为主键，如果不存在这种列，则 MySQL 自动为 InnoDB 表生成一个隐含字段 rowid 作为主键，这个字段长度为 6 个字节，类型为长整形。

辅助索引（Secondary Index）

辅助索引，将途中的第二行 name，作为索引如图：

在这里插入图片描述

InnoDB 表是基于聚簇索引建立的。聚簇索引这种实现方式使得按照主键的搜索十分高效，但是需要首先检索辅助索引获得主键，然后用主键到主索引中检索获得记录。

在这里插入图片描述

由于 InnoDB 索引的实现特性，推荐使用整形的自增主键。

有三点好处：

• 自增 key 一般为 int 等整数型，key 比较紧凑，这样 m 可以非常大，而且索引占用空间小。最极端的例子，如果使用 50B 的 varchar（包括长度），那么 m = 4 * 1024 / 54m = 75.85 ~= 76，深度最大 log(76/2)(10^7) = 4.43 ~= 5，再加上 cache 缺失、字符串比较的成本，时间成本增加较大。同时，key 由 4B 增长到 50B，整棵索引树的空间占用增长也是极为恐怖的（如果二级索引使用主键定位数据行，则空间增长更加严重）。
• MySQL 索引底层的数据比较都是整数型比较，如果主键时字符串类型的，里面还有英文，还得转换 ASCII 码进行比较。所以不建议使用 uuid 作为主键。
• 自增的主键使得数据行的插入比如落到索引数的最右侧，发生节点分裂的频率较低。B+Tree 实际操作插入过程。如果不是非单调主键，插入过程很大程度会发生节点重排，不利于索引优化的初衷。

🏗️InnoDB 索引和 MyISAM 索引的区别

一是主索引的区别：InnoDB 的数据文件本身就是索引文件。而 MyISAM 的索引和数据是分开的。

二是辅助索引的区别：InnoDB 的辅助索引 data 域存储相应记录主键的值而不是地址。而 MyISAM 的辅助索引和主索引没有多大区别。

🏘️4、覆盖索引（Covering index）

InnoDB 存储引擎支持覆盖索引，即从辅助索引中就可以得到查询的记录，而不需要查询聚集索引中的记录，就是平时所说的不需要回表。

可以减少大量的 IO 操作。如果要查询辅助索引中不包含的字段，得先遍历辅助索引，再遍历聚集索引，而如果要查询的字段值在辅助索引上就有，就不用再查聚集索引了，这显然会减少 IO 操作。

🏚️5、联合索引

联合索引是指对表上的多个列进行索引。如下图联合索引原理图

InnoDB 存储引擎支持覆盖索引，即从辅助索引中就可以得到查询的记录，不需要查询聚簇索引中的记录了。可以减少大量的 IO 操作。

如果要查询辅助索引中不含有的字段，得先遍历辅助索引，再遍历聚集索引，而如果要查询的字段值在辅助索引上就有，就不用再查聚集索引了，这显然会减少 IO 操作。

例如，联合索引（a,b,c,d）, 查询条件 a=1 and b=3 and c>3 and d=4; 会依次命中 a,b,c，无法命中 d，这就是最左前缀匹配。

两个或以上的列上的索引。如下图联合索引的原理图：

在这里插入图片描述

上图中的联合索引有三个，从上到下，严格按照排序。

🏠6、优化建议

1、最左前缀匹配

索引可以简单如一个列 (a)，也可以复杂如多个列 (a, b, c, d)，即联合索引。如果是联合索引，那么 key 也由多个列组成，同时，索引只能用于查找 key 是否存在（相等），遇到范围查询 (>、<、between、like 左匹配) 等就不能进一步匹配了，后续退化为线性查找。因此，列的排列顺序决定了可命中索引的列数。

如有索引 (a, b, c, d)，查询条件 a = 1 and b = 2 and c > 3 and d = 4，则会在每个节点依次命中 a、b、c，无法命中 d。也就是最左前缀匹配原则。

2、in 自动优化顺序

不需要考虑 =、in 等的顺序，mysql 会自动优化这些条件的顺序，以匹配尽可能多的索引列。

如有索引 (a, b, c, d)，查询条件 c > 3 and b = 2 and a = 1 and d < 4 与 a = 1 and c > 3 and b = 2 and d < 4 等顺序都是可以的，MySQL 会自动优化为 a = 1 and b = 2 and c > 3 and d < 4，依次命中 a、b、c。

索引列不能参与计算

有索引列参与计算的查询条件对索引不友好（甚至无法使用索引），如 from_unixtime(create_time) = '2021-08-27'。

原因很简单，如何在节点中查找到对应 key？如果线性扫描，则每次都需要重新计算，成本太高；如果二分查找，则需要针对 from_unixtime 方法确定大小关系。

因此，索引列不能参与计算。上述 from_unixtime(create_time) = '2021-08-27' 语句应该写成 create_time = unix_timestamp('2021-08-27')。

能扩展就不要新建索引

如果已有索引 (a)，想建立索引 (a, b)，尽量选择修改索引 (a) 为索引 (a, b)。

新建索引的成本很容易理解。而基于索引 (a) 修改为索引 (a, b) 的话，MySQL 可以直接在索引 a 的 B + 树上，经过分裂、合并等修改为索引 (a, b)。

不需要建立前缀有包含关系的索引

如果已有索引 (a, b)，则不需要再建立索引 (a)，但是如果有必要，则仍然需考虑建立索引 (b)。

选择区分度高的列作索引

很容易理解。如，用性别作索引，那么索引仅能将 1000w 行数据划分为两部分（如 500w 男，500w 女），索引几乎无效。

区分度的公式是 count(distinct <col>) / count(*)，表示字段不重复的比例，比例越大区分度越好。唯一键的区分度是 1，而一些状态、性别字段可能在大数据面前的区分度趋近于 0。