跳表和Mysql联合索引的最左原则和索引下推的优化
文章目录
跳表（Skip List）关键特性跳表的结构示意图跳表的查询效率为什么 MySQL 不使用跳表而使用 B+ 树？跳表的实际应用场景
总结
MySQL 联合索引的最左匹配原则最左匹配原则的规则示例：创建联合索引查询示例及索引使用情况设计联合索引
MySQL 的索引下推优化（Index Condition Pushdown, ICP）索引下推的工作原理索引下推示例索引下推的优势索引下推的适用场景联合索引和索引下推优化的实际案例总结
B+树的高度在3层时存储的数据可能已达千万级别，但对于跳表而言同样去维护千万的数据量那么所造成的跳表层数过高而导致的磁盘io次数增多，也就是使用B+树在存储同样的数据下磁盘io次数更少。
跳表（Skip List）
跳表（Skip List）是一种 平衡数据结构，它是对链表的一种优化，通过引入多层级的索引结构，提升了对有序链表的查找效率。跳表是一种 概率型数据结构，经常用在 内存中的有序数据存储和检索 中，比如 Redis 的有序集合（ZSET）就使用了跳表。
跳表的核心是基于 多层级的链表结构。它在一个有序的单链表基础上，额外增加了多层的索引来跳跃查找数据。
关键特性
多层链表：
最底层是完整的链表，所有元素按顺序排列。上层是索引层，每一层都是从下层链表中抽取部分元素作为索引。最顶层的索引层可能只包含很少的元素，通常是头尾两个元素。 查询效率：每一层索引可以帮助快速跳过多个节点，将查找时间从 O(n) 降低到 O(log n)。动态更新：插入、删除数据时会根据一定的概率来决定是否将新元素加入到索引层，从而动态维护平衡。
跳表的结构示意图
Level 4: 1 -----> -------> 17
Level 3: 1 -----> 9 -----> 17
Level 2: 1 -----> 5 -----> 9 -----> 17
Level 1: 1 -----> 3 -----> 5 -----> 7 -----> 9 -----> 17
Level 1 是完整的链表，包含所有数据。每一层向上的索引会抽取一部分数据（比如每两个节点抽取一个）。查询时，通过高层索引快速跳过多个节点，从而加速查找。
跳表的查询效率
跳表的查询时间复杂度是 O(log n)，原因如下：
跳表的层数为 log(n)（近似）。每层的链表查找的节点数量是常数级别的。
为什么 MySQL 不使用跳表而使用 B+ 树？
在 MySQL 中，特别是使用磁盘作为存储设备时，B+ 树比跳表具有明显的优势，主要体现在以下几个方面：
磁盘 I/O 的影响
B+ 树的优势：B+ 树是一种多叉树结构，叶子节点存储实际数据，内部节点存储索引。一个节点的大小通常设置为和磁盘页大小（一般为 4KB）一致，这样一个节点可以存储多个索引值。在树的高度为 3 时，可以容纳数千万级别的数据，查询数据时只需 3 次磁盘 I/O（树的高度）。跳表的劣势：跳表是链表的变种，其多层索引分布在不同的节点上，节点之间通过指针连接。这种结构会导致查询时需要频繁访问多个节点，跳表的每一层访问都可能需要一次磁盘 I/O，导致磁盘访问次数更多。
存储效率
B+ 树：内部节点只存储索引值，而叶子节点存储完整数据。B+ 树利用磁盘页大小来最大化节点的存储容量，能够有效减少存储开销和磁盘访问次数。跳表：跳表需要存储多个索引层的数据，并且每个索引节点需要额外的指针来维护链表结构。相比之下，跳表的存储效率更低。
范围查询的性能
B+ 树的优势：B+ 树的叶子节点通过指针相连，可以高效地支持范围查询（Range Query）。例如，直接从一个节点遍历到下一个节点即可。跳表的劣势：虽然跳表也支持范围查询，但由于链表的结构特点，每次范围查询都可能会带来大量随机的指针访问，性能不如 B+ 树高效。
复杂度和成熟度
B+ 树的成熟度：B+ 树是一种成熟的磁盘存储数据结构，广泛应用于数据库系统，尤其在事务管理、并发控制和磁盘优化方面非常成熟。跳表的复杂度：跳表更多用于 内存场景，而不是面向磁盘优化。因为磁盘访问的开销远高于内存访问，跳表在磁盘场景下无法充分发挥其优势。
动态平衡性
B+ 树的动态平衡：B+ 树通过分裂和合并节点来动态维护平衡，确保树的高度尽量保持最小。跳表的随机性：跳表通过概率算法来决定索引层的节点分布，虽然简单，但它不如 B+ 树的平衡性高效和稳定。
跳表的实际应用场景
跳表不适合磁盘场景，但在 内存中的有序数据管理 场景下非常有用。例如：
Redis：Redis 的有序集合（ZSET）实现中使用了跳表。跳表在内存中快速、高效，且实现简单，是 Redis 的理想选择。内存数据库：跳表适合用于纯内存数据库场景，数据访问快速，插入、删除效率高。日志系统：在一些高效的日志存储与查询系统中，跳表可以作为索引的一种结构。
总结
跳表 是一种简单、高效的内存数据结构，但在磁盘场景下，存储效率和访问性能都不如 B+ 树。B+ 树 是一种更适合磁盘的存储结构，具有高效的磁盘 I/O、范围查询能力和动态平衡性能，因此 MySQL 和其他关系型数据库优先选择 B+ 树。跳表更适合用于 内存场景，例如 Redis、内存数据库或其他需要有序数据结构的应用场景。
MySQL 联合索引的最左匹配原则
联合索引是指在一个索引中包含多个列，例如 (a, b, c) 这样的多列索引。MySQL 的查询优化器在使用联合索引时，会遵循 最左前缀匹配原则，这意味着联合索引的查询必须从最左边的列开始，按顺序逐层匹配。
最左匹配原则的规则
从联合索引的最左列开始匹配，只要某一列中断匹配，后续的列将无法继续使用索引。支持部分匹配，例如联合索引 (a, b, c) 中，可以只匹配 a 或 a, b，但无法直接从 b 或 c 开始匹配。
示例：创建联合索引
假设我们有如下表和索引：
CREATE TABLE example (
a INT,
b INT,
c INT,
d VARCHAR(50),
PRIMARY KEY (a, b, c) -- 联合索引 (a, b, c)
);
查询示例及索引使用情况
完全匹配左侧字段：使用整个联合索引 (a, b, c)。索引命中最优。
SELECT * FROM example WHERE a = 1 AND b = 2 AND c = 3;
部分匹配左侧字段：使用索引 (a, b)，未涉及的 c 列无法使用索引。
SELECT * FROM example WHERE a = 1 AND b = 2;
仅匹配最左前缀：使用索引 (a)，b 和 c 无法使用。
SELECT * FROM example WHERE a = 1;
跳过中间列（不满足最左原则）：无法使用索引，因为查询未从最左列 a 开始。
SELECT * FROM example WHERE b = 2 AND c = 3;
跨列范围查询（部分失效）：索引只会用于 (a, b)，因为范围查询 b > 2 导致后续的 c 无法使用索引。
SELECT * FROM example WHERE a = 1 AND b > 2 AND c = 3;
设计联合索引
设计联合索引时，可以根据查询的使用频率和条件的选择性（唯一性高的列优先）来决定列的顺序。例如：
如果查询条件大多是 a 或 a, b，优先设计索引为 (a, b, c)。如果查询条件大多是 b 或 b, c，优先设计索引为 (b, c, a)。
MySQL 的索引下推优化（Index Condition Pushdown, ICP）
索引下推 是 MySQL 5.6 引入的一种优化机制，用于减少全表扫描，提高索引的利用效率。它的作用是在使用 联合索引 时，将部分查询条件尽可能下推到存储引擎层处理，减少不必要的数据传输和服务器层的判断开销。
索引下推的工作原理
在没有索引下推优化之前，MySQL 的查询流程如下：
存储引擎根据索引查找到匹配的记录。将记录返回给 MySQL 服务器层。在服务器层进行查询条件的过滤。
在索引下推优化开启后：
存储引擎层可以根据索引中的列直接对记录进行部分过滤。只有满足部分查询条件的记录才会返回给服务器层，减少数据传输量和服务器层的计算开销。
索引下推示例
示例表结构
CREATE TABLE example (
id INT PRIMARY KEY,
a INT NOT NULL,
b INT NOT NULL,
c VARCHAR(50),
INDEX idx_a_b (a, b)
);
查询示例及执行情况
无索引下推时（MySQL 5.5 及以下）：
SELECT * FROM example WHERE a = 1 AND b > 2;
存储引擎会根据 a = 1 找到所有符合条件的记录。然后将这些记录返回给服务器层，再在服务器层判断 b > 2。如果 a = 1 找到了很多行，但只有很少的行满足 b > 2，则会有大量无用数据被返回给服务器层。 开启索引下推后（MySQL 5.6 及以上）：
SELECT * FROM example WHERE a = 1 AND b > 2;
存储引擎会先根据 a = 1 找到符合条件的记录。然后在存储引擎层判断 b > 2，只将满足条件的记录返回给服务器层。减少了传输和服务器层的计算开销。
索引下推的优势
减少数据传输：数据过滤尽量在存储引擎层完成，减少传递给服务器层的数据量。提高查询效率：减少了服务器层的判断和过滤工作，提升了整体查询性能。充分利用索引：即使索引无法完全覆盖查询条件，存储引擎层仍可以利用索引的部分列进行优化。
索引下推的适用场景
范围查询： 存储引擎可以通过 a = 1 和 b > 2 下推条件，减少不必要的返回行。SELECT * FROM example WHERE a = 1 AND b > 2;
带前缀匹配的模糊查询：如果索引中包含列 c，存储引擎可以直接过滤掉不满足 c LIKE 'abc%' 的记录。SELECT * FROM example WHERE a = 1 AND c LIKE 'abc%';
联合索引和索引下推优化的实际案例
假设有如下表和索引：
CREATE TABLE orders (
order_id INT PRIMARY KEY,
user_id INT,
product_id INT,
order_date DATE,
total_amount DECIMAL(10, 2),
INDEX idx_user_product_date (user_id, product_id, order_date)
);
执行查询：
SELECT * FROM orders
WHERE user_id = 123
AND product_id > 1000
AND order_date >= '2025-01-01';
优化过程：
联合索引使用情况：
user_id = 123：匹配索引的第一列。product_id > 1000：匹配索引的第二列。order_date >= '2025-01-01'：匹配索引的第三列。联合索引 (user_id, product_id, order_date) 完全生效。 索引下推的作用：
存储引擎先通过索引 (user_id, product_id, order_date) 定位记录。然后在存储引擎层过滤掉 product_id > 1000 和 order_date >= '2025-01-01' 不符合条件的记录。最终返回满足所有条件的记录到服务器层。
性能对比
无索引下推：存储引擎返回大量 user_id = 123 的记录，服务器层需要逐条判断其他条件。有索引下推：存储引擎层直接过滤不必要的数据，显著减少返回记录的数量。
总结
联合索引的最左原则：必须从索引的最左列开始，按顺序逐列匹配。中断匹配后，后续列无法使用索引。索引下推优化：将更多的过滤条件下推到存储引擎层，提高索引的利用率。减少数据传输量，提升查询性能。
