索引

什么是索引？

索引（Index） 是数据库中用来快速查找数据的一种数据结构，通过用空间换时间的数据结构，达到减少磁盘 I/O的目的。

你可以把它简单理解为 “书籍的目录”。 想象一本 1000 页的字典：

• 没有索引（全表扫描）： 如果你想找“MySQL”这个词，你必须从第 1 页开始，一页一页往后翻，直到找到为止。如果这个词在第 999 页，你就要翻 999 次。效率极低。
• 有索引： 你打开目录（或利用字典的字母排序），直接定位到 M 开头的区域，几秒钟就能找到。

在数据库中，索引就是那个“目录”。它通过特定的算法（通常是 B+ 树）将数据有序地组织起来，让你不用扫描整个表就能找到你想要的那一行。

索引的分类

在数据库（尤其是 MySQL InnoDB）中，索引的分类方式主要取决于你看待它的角度。最常见的分类维度有四种：数据结构、物理存储、逻辑功能、字段个数。

这是面试中非常核心的知识点，建议按照以下结构回答：

---

1.按物理存储方式分类 (核心)

这是 InnoDB 引擎特有的概念，区分了数据究竟是怎么存的。

• 聚簇索引 (Clustered Index)
  • 定义： 索引的叶子节点存放的是整行数据。
  • 特点： 数据本身就是按索引顺序存储的。一张表只能有一个聚簇索引（通常是主键）。
  • 优势： 找到索引就找到了数据，速度最快。
• 二级索引 / 非聚簇索引 (Secondary Index / Non-Clustered)
  • 定义： 索引的叶子节点存放的是主键的值（而不是真实数据）。
  • 特点： 一张表可以有多个二级索引。
  • 回表 (Back to Table)： 如果你查二级索引（比如 name），找到后得到的是 ID，通常还需要拿 ID 去聚簇索引里再查一次才能拿到完整数据。这个过程叫回表。

2.按逻辑功能分类

这是我们在写 SQL 建表语句时最常接触的分类。

索引类型	含义	作用
主键索引 (Primary Key)	特殊的唯一索引，不允许为空。	它是表的身份标识，InnoDB 会自动用它建立聚簇索引。
唯一索引 (Unique Index)	索引列的值必须唯一，但允许有空值 (NULL)。	既能加速查询，又能约束数据的唯一性（例如身份证号）。
普通索引 (Normal Index)	没有任何限制，仅仅是为了加快查询速度。	最基本的索引。
全文索引 (Full-text Index)	类似于搜索引擎（倒排索引），用于查找文本中的关键词。	解决 LIKE '%word%' 效率低下的问题（MySQL 5.6+ InnoDB 开始支持）。
空间索引 (Spatial Index)	用于地理数据类型（如 GPS 坐标）。	用于地理空间数据的查询和计算。

3.按字段个数分类

• 单列索引：一个索引只包含一个列。
• 联合索引 (Composite Index / Joint Index)：一个索引包含多个列（例如 name + age）。
  • 核心原则： 最左前缀原则 (Leftmost Prefixing)。
  • 例子： 建立了 (a, b, c) 的联合索引：
    • 查 a -> 走索引。
    • 查 a, b -> 走索引。
    • 查 b, c -> 不走索引（因为跳过了老大 a）。

4.按底层数据结构分类

• B+ 树索引 (B+ Tree)：MySQL InnoDB 的默认且最常用的结构，适合范围查询、排序、精确查找。
• 哈希索引 (Hash)：基于哈希表实现，精确查找 (=, IN) 极快（O(1)），但不支持范围查询 (>, <) 和排序。
  • Memory 引擎默认使用，InnoDB 只有“自适应哈希索引”（内部自动优化，用户不可控）。
• R-Tree 索引：主要用于空间地理数据。

建立索引的注意事项

建立索引是一门平衡的艺术。索引不是越多越好，因为索引会占据磁盘空间，并且会拖慢写入速度（INSERT/UPDATE/DELETE 时需要维护索引树）。

在建立索引时，你应该遵循 “三多、三少、一原则”，并注意一些避坑指南。

一、 核心原则

1. 考虑字段的“区分度” (Cardinality) —— 最重要

不要给“区分度低”的字段加索引。

• 什么是区分度？ 字段中不重复值的比例。
• 反例： 性别（男/女）、状态（0/1/2）。
• 原因： 如果一个字段只有几种可能的值，数据库在查询时发现通过索引筛出来的数据仍然占全表的一半，优化器就会觉得：“还要回表这么多次，不如直接全表扫描算了”。此时索引失效，浪费空间。
• 建议： 只有当某个字段的值分布比较散（如身份证号、手机号、订单ID），或者能过滤掉 80% 以上的数据时，才适合建索引。

2. 最左前缀原则 (Leftmost Prefixing)

在建立联合索引（多列索引）时，顺序至关重要。

• 假设建立了 (a, b, c) 的索引。
• 有效： WHERE a = 1，WHERE a = 1 AND b = 2。
• 无效： WHERE b = 2，WHERE c = 3（跳过了老大 a，索引完全失效）。
• 建议： 将查询频率最高、区分度最高的字段放在最左边。

3. 覆盖索引 (Covering Index)

尽量让索引包含查询所需的所有列。

• 场景： SELECT name FROM user WHERE age = 20;
• 优化： 建立 (age, name) 的联合索引。
• 好处： B+ 树的叶子节点里已经有了 age 和 name，查询时不需要去聚簇索引查整行数据（避免了回表），性能极高。

---

二、 应该给哪些字段加？

1. 主键和外键： 必须加（主键自带，外键为了连接速度）。
2. 高频查询字段： 经常出现在 WHERE 子句中的字段。
3. 排序和分组字段： 经常出现在 ORDER BY、GROUP BY 中的字段（利用 B+ 树的有序性，避免内存排序）。
4. 连接字段： 多表 JOIN 时，ON 两边的字段必须都要建立索引，且类型必须一致，否则索引失效。

---

三、 应该避免的情况 (避坑指南)

1. 避免对“长字符串”直接建立完整索引

• 问题： 如果你给一个 255 长度的 VARCHAR 建索引，索引文件会非常庞大，且比较慢。
• 解法： 使用前缀索引。
  • ALTER TABLE user ADD INDEX index_name (email(6));
  • 只索引邮箱的前 6 个字符，既节省空间，又能保持不错的区分度。

2. 避免在索引列上做计算

• 大忌： 永远不要在 WHERE 条件的等号左边做运算或使用函数。
• 反例： WHERE YEAR(create_time) = 2024 -> 索引失效（因为数据库不知道经过函数转换后的值在树的哪里）。
• 正例： WHERE create_time BETWEEN '2024-01-01' AND '2024-12-31'。

3. 避免 NULL 值陷阱

• 虽然现在的 InnoDB 对 NULL 的处理优化了很多，但最佳实践仍然是：尽量把列定义为 NOT NULL，并给一个默认值（如空字符串或 0）。
• 原因：NULL 使得索引统计和数值比较变得复杂。

4. 类型隐式转换导致索引失效

• 场景： 字段 phone 是 VARCHAR 类型。
• 错误： WHERE phone = 13800000000; （你传了个数字）。
• 后果： MySQL 会默默把字符串转成数字再比对，相当于使用了函数，索引失效。
• 正确： WHERE phone = '13800000000';。

解释“范围之后全失效”： 如果是联合索引 (a, b, c)，你的查询是 WHERE a = 1 AND b > 10 AND c = 5。 结果是：a 用到了索引，b 用到了索引（范围查询），但 c 无法使用索引。因为在 b > 10 的范围内，c 是无序的。

索引失效的场景

索引失效是面试中的必考题，也是工作中排查慢 SQL 的核心技能。 索引失效的本质原因通常只有两个：

1. 破坏了 B+ 树的有序性（导致无法利用索引快速定位）。
2. MySQL 优化器认为全表扫描更划算（比如要查的数据量太大）。

以下是 7 大常见索引失效场景，我把它们总结为**“三不、两无、一转换”**。

---

一、 违反“最左前缀法则”

这是针对联合索引的。假设你建了 (a, b, c) 的联合索引。

1. 带头大哥失踪了：
   • ❌ SELECT * FROM table WHERE b = 1;
   • 原因： 跳过了 a，B+ 树无法开始查找。
2. 中间兄弟断了：
   • ❌ SELECT * FROM table WHERE a = 1 AND c = 3;
   • 后果： 只有 a 用到了索引，c 变成了普通条件（因为断了 b）。
3. 范围查询阻断了后续：
   • ⚠️ SELECT * FROM table WHERE a = 1 AND b > 10 AND c = 3;
   • 后果： a 和 b 走了索引，但 c 失效。因为在 b > 10 的范围内，c 是无序的。

---

二、 对索引列做了“手脚” (严禁操作)

只要你在索引列上做了任何计算、函数操作，索引直接作废。

1. 在列上做计算：
   • ❌ WHERE id + 1 = 10;
   • ✅ WHERE id = 10 - 1; （把计算放到等号右边）
2. 在列上用函数：
   • ❌ WHERE LEFT(name, 3) = 'abc';
   • ❌ WHERE DATE(create_time) = '2024-01-01';
   • 原因： 数据库存的是原始值，经过函数转换后的值在 B+ 树中是不知道在哪里的，必须全表扫描并计算。

---

三、 隐式类型转换 (最坑的陷阱)

这是一个非常隐蔽的坑，很多老手都会翻车。

• 场景： phone 字段是 VARCHAR 类型，且建了索引。
• 错误写法： SELECT * FROM user WHERE phone = 13800000000;
  • 你传了一个数字给字符串字段。
• 后果： 索引失效。
• 原因： MySQL 会自动把字符串转成数字进行比对，这相当于在列上隐式地使用了 CAST() 函数。即 WHERE CAST(phone AS signed) = 138...。根据上一条规则，对列用函数，索引失效。
• 反过来： 如果字段是 int，你传字符串 WHERE id = '1'，索引有效（因为MySQL是把字符串常量转数字，不是转字段）。

---

四、 LIKE 查询以 % 开头

• ❌ SELECT * FROM user WHERE name LIKE '%三';
• ❌ SELECT * FROM user WHERE name LIKE '%三%';
• 原因： B+ 树是按照“首字母”排序的。如果你的首字母是通配符 %，数据库就不知道该从哪里找起，只能全表扫描。
• ✅ SELECT * FROM user WHERE name LIKE '张%'; （这是有效的，属于范围查询）。

---

五、 OR 语句的两边不一样

• 场景： WHERE a = 1 OR b = 2;
• 失效条件： 如果 a 有索引，但 b 没有索引。
• 后果： 整个 SQL 都不会走索引。
• 原因： 即使 a 走了索引查出一部分数据，但也必须对其余数据进行全表扫描来查 b。既然都要全表扫描，优化器索性直接放弃 a 的索引，一次性扫完。
• 解决： 给 b 也加上索引，或者用 UNION 代替 OR。

---

六、 不等于和 NULL (看情况)

1. 不等号： != 或 <>
   • 通常会导致索引失效，改为全表扫描。因为“不等于”意味着要取反面的所有数据，数据量通常很大。
2. IS NOT NULL：
   • 通常也会导致索引失效。
3. IS NULL：
   • 如果字段允许为空，IS NULL 一般是可以走索引的。

---

七、 优化器的“成本判断” (全表扫描更快)

这是最无奈的一种情况：你语法没写错，但 MySQL 觉得走索引太慢了。

• 场景： 比如表里有 100 行数据，你要查 WHERE id > 1。这涵盖了 99 行数据。
• 决策： 如果走索引，需要“查索引 -> 回表 -> 查索引 -> 回表”循环 99 次，这全是随机 I/O。与其这样，不如直接全表扫描（顺序 I/O）来得快。
• 阈值： 一般当查询的数据量超过表总行数的 30% 左右（经验值，具体看引擎统计），优化器就会放弃索引。

联合索引

这也是数据库面试中最经典、最高频的问题之一。

理解联合索引和最左前缀原则，不能死记硬背，必须从 B+ 树的底层存储结构去理解。一旦你明白了 B+ 树是怎么存数据的，这两个概念就成了常识。

一、 什么是联合索引？

联合索引（Composite Index）是指对表上的多个列同时建立一个索引。 例如：CREATE INDEX idx_abc ON table_name (a, b, c);

这就相当于我们建立了一本目录，这本目录的排序规则是：

1. 先按 a 排序。
2. 如果 a 相同，再按 b 排序。
3. 如果 b 相同，再按 c 排序。

关键点： 联合索引在底层只有一棵 B+ 树，而不是三棵树。叶子节点存的是 (a, b, c) 三个字段的数据以及主键。

---

二、 B+ 树里的“排序秘密”

要理解最左前缀，必须看透这棵树的排序逻辑：

• 全局有序，局部无序。
  • 对于第一个字段 a，它是全局有序的（1, 1, 2, 2, 3, 4...）。
  • 对于第二个字段 b，它是全局无序的。你看整个 b 列可能是 (1, 3, 1, 4, 2...) 乱序的。
  • 但是，在 a 确定的范围内，b 是局部有序的。比如当 a=1 时，b 是有序排列的。

这就像“通讯录”：

• 通讯录首先按“姓”排序（赵、钱、孙...）。
• 只有“姓”相同的时候，才会按“名”排序。
• 如果你不看“姓”，直接去找“名”叫“建国”的人，你必须翻遍整本通讯录（全表扫描），因为“建国”可能姓赵，也可能姓李，散落在书的各个角落。

---

三、 最左前缀匹配原则 (Leftmost Prefixing)

基于上面的排序逻辑，MySQL 在使用联合索引时，必须遵守“从左到右”的顺序，一旦中间断了，后面的索引就失效了。

假设建立索引 (a, b, c)

我们来看看各种 SQL 写法是否用到了索引：

1. 全值匹配（完美）

• WHERE a=1 AND b=2 AND c=3
• 结果： ✅ 全部走索引。
• 注意： SQL 里字段的顺序不重要，MySQL 优化器会自动调整为 a -> b -> c。即 WHERE b=2 AND a=1 AND c=3 也是完美的。

2. 匹配最左边（有效）

• WHERE a=1 -> ✅ 走索引（只用 a）。
• WHERE a=1 AND b=2 -> ✅ 走索引（用到 a 和 b）。

3. 跳过老大（完全失效）

• WHERE b=2
• WHERE c=3
• WHERE b=2 AND c=3
• 结果： ❌ 完全不走索引。
• 原因： 跳过了开头 a，B+ 树不知道从哪里开始查，只能全表扫描。（就像在通讯录里直接找“名”，没法找）。

4. 跳过中间兄弟（部分失效）

• WHERE a=1 AND c=3
• 结果： ⚠️ 部分走索引。
• 分析：
  • a=1 用到了索引，能快速定位。
  • 但是 c=3 无法利用索引查找。因为在 a=1 确定后，b 是有序的，但 c 是无序的（只有 a 和 b 都确定，c 才有序）。
  • 注：MySQL 5.6+ 会利用“索引下推”优化，在扫描 a=1 的索引节点时顺便过滤 c，但从索引查找角度看，c 没起到定位作用。

5. 范围查询中断（重要陷阱）

• WHERE a=1 AND b > 2 AND c=3
• 结果： ⚠️ a 和 b 走了索引，c 失效。
• 原因：
  • a=1 找到了，锁定一个范围。
  • b > 2 也是有序的，可以接着找。
  • 但是，在 b > 2 这个范围内（比如 b=3, b=4, b=5...），c 是无序的。所以数据库只能把 b > 2 的数据都拿出来，挨个判断 c 是否等于 3。

---

四、 为什么要用联合索引？

既然这么麻烦，为什么不建三个单列索引 (a), (b), (c)？

1. 减少开销： 建 1 个联合索引只需维护 1 棵 B+ 树；建 3 个单列索引需要维护 3 棵树，占用更多磁盘空间，写入时更慢。
2. 覆盖索引 (Covering Index)： 联合索引 (a, b, c) 的叶子节点包含了这三个值。如果你 SELECT a, b, c WHERE a=1，数据库直接从索引树就拿到了数据，不用回表，速度极快。
3. 效率更高： 比如 WHERE a=1 AND b=2。
   • 单列索引： 可能会先查 a 的索引得到 ID 集合，再查 b 的索引得到 ID 集合，然后取交集（或者只用一个索引回表过滤）。
   • 联合索引： 直接定位到 a=1, b=2 的位置，一步到位。

---

五、 总结口诀（面试必背）

全值匹配我最爱，最左前缀要遵守。 带头大哥不能死，中间兄弟不能断。 索引列上少计算，范围之后全失效。

• 带头大哥不能死： 查询条件里必须包含索引最左边的列（a）。
• 中间兄弟不能断： a 和 c 中间断了 b，c 就没法用。
• 范围之后全失效： 只要遇到 > < BETWEEN LIKE 这种范围查询，索引利用就到此为止，后面的列失效。

覆盖索引

覆盖索引 (Covering Index) 不是一种特殊的索引结构，而是一种查询方式或优化状态。 用一句话概括：当一个索引包含了（覆盖了）查询所需要的所有字段时，就叫覆盖索引。 为了理解它，我们需要先理解“回表”。

---

1. 什么是“回表”？

回表是指在使用非聚簇索引（二级索引）进行查询时，需要根据索引中存储的主键值，再次回到主键索引（聚簇索引）中查找完整数据行的过程。 在 InnoDB 引擎中，有两类索引：

1. 聚簇索引（主键索引）： 叶子节点存的是整行数据。
2. 二级索引（普通索引）： 叶子节点存的是索引列的值 + 主键 ID。

普通查询流程（回表）： 假设你有一个表 user (id, name, age)，你建立了一个普通索引 index_name (name)。 执行语句：SELECT name, age FROM user WHERE name = '张三';

1. 查二级索引树： 找到 name='张三' 的节点。
2. 拿主键： 获取到对应的 id = 1。
3. 回表（Back to Table）：拿着 id=1 去聚簇索引树里再查一次，找到这一行数据。
4. 取数据： 把 age 字段拿出来返回。

痛点： 这种查询需要扫描两棵树，多了一次随机 I/O，性能有损耗。

2. 覆盖索引是如何优化的？

如果我们将上面的索引改为联合索引 index_name_age (name, age)。

再次执行：SELECT name, age FROM user WHERE name = '张三';

1. 查二级索引树： 找到 name='张三' 的节点。
2. 直接取数据： 此时，叶子节点里已经包含了 name 和 age 的值。
3. 结束： 数据库发现你需要的数据都在这棵树上了，不需要去查聚簇索引了（不需要回表）。

这就是覆盖索引。

3. 怎么判断是否用到了覆盖索引？

使用 EXPLAIN 命令查看 SQL 的执行计划。

• 查看 Extra 列。
• 如果显示 Using index，说明触发了覆盖索引，性能非常好。

注意： Using index 和 Using index condition 是不一样的，前者才是真正的覆盖索引。

4. 经典面试题示例

假设表结构：id (PK), name, age, city。 现有索引：idx_name_age (name, age)。

SQL 语句	是否触发覆盖索引？	原因
SELECT age FROM user WHERE name = 'A'	是	查 name 找 age，都在索引里。
SELECT id, age FROM user WHERE name = 'A'	是	二级索引隐含了主键 ID，所以 ID 也在树上。
SELECT city FROM user WHERE name = 'A'	否	索引里没有 city，必须回表去查。
SELECT * FROM user WHERE name = 'A'	否	* 包含所有字段，索引不能覆盖所有字段，必须回表。

5. 覆盖索引的优缺点

✅ 优点：

1. 无需回表： 减少了大量的随机磁盘 I/O。
2. 减少内存消耗： 索引通常比数据行小，能更好地利用 Buffer Pool。

❌ 缺点：

1. 索引维护成本： 为了实现覆盖，你可能需要建立包含多个字段的“宽索引”或“联合索引”，这会占用更多的磁盘空间，并拖慢写入速度（Insert/Update）。

索引下推

索引下推 (Index Condition Pushdown，简称 ICP) 是 MySQL 5.6 版本引入的一项重要性能优化技术。 它的核心目的是：在“回表”之前，利用索引中已有的数据，先把不符合条件的数据过滤掉，从而减少回表次数，减少磁盘 I/O。

---

通俗易懂的例子

为了让你彻底明白，我们举个具体的场景： 假设有一张表 user，包含字段 (id, name, age, address)。 建立了一个联合索引：idx_name_age (name, age)。 现在执行 SQL 语句：

SELECT * FROM user WHERE name LIKE '张%' AND age = 10;

分析这条语句：

1. name LIKE '张%'：可以用到索引的范围查询（根据最左前缀原则）。
2. age = 10：因为 name 是模糊查询（范围），根据规则，后面的 age 索引失效了。即无法直接通过索引树定位到 age=10 的位置。

没有 ICP 时的执行过程 (MySQL 5.6 之前)

在没有索引下推的时候，Server 层和存储引擎（InnoDB）是这样配合的：

1. Server 层命令引擎：“把所有 name 以 '张' 开头的数据给我。”
2. InnoDB 在索引树上找到所有 name 像 '张' 的节点（假设有 100 个）。
   • 注意：虽然索引叶子节点里也存了 age 的值，但旧版本的 InnoDB 会忽略它。
3. InnoDB 拿着这 100 个节点的 ID，进行 100 次回表，把 100 行完整的用户数据读出来，返回给 Server 层。
4. Server 层 拿到这 100 行数据，挨个判断 age 是不是等于 10。
   • 结果发现只有 2 个人是 10 岁，把这 2 条返回给用户，丢弃剩下的 98 条。

痛点： 明明索引里就有 age，引擎却视而不见，非要回表去查完整数据，导致多做了 98 次无用的磁盘 I/O。

有了 ICP 后的执行过程 (MySQL 5.6 及之后)

有了索引下推，Server 层把“筛选 age”这个条件**“下推”**给了存储引擎：

1. Server 层命令引擎：“把所有 name 以 '张' 开头，且 age 等于 10 的数据给我。”
2. InnoDB 在索引树上找到所有 name 像 '张' 的节点。
3. InnoDB 此时变聪明了：它在读索引节点时，顺便看了一眼旁边的 age 字段。
   • 如果 age 不等于 10：直接跳过，不用去回表了！
   • 如果 age 等于 10：才去进行回表，拿完整数据。
4. 结果：最终只进行了 2 次回表。

优势： 从 100 次回表变成了 2 次回表，性能极大提升。

---

总结对比图

阶段	动作	效果
无 ICP	只要满足 name LIKE '张%'，不管 age 是多少，统统回表查数据，查完再由 Server 过滤。	回表次数多，I/O 浪费严重。
有 ICP	发现索引里有 age，先在索引内部判断 age=10。不满足的直接丢弃，满足的才回表。	回表次数少，利用了索引中的剩余价值。

---

tip

怎么判断是否用到了索引下推？

使用 EXPLAIN 查看执行计划。 如果 Extra 列显示：Using index condition，这就说明用到了索引下推。

使用条件

1. 只能用于二级索引（非聚簇索引）。
2. 一般发生在联合索引中，且满足最左前缀法则被截断的情况（如前一个字段用了范围查询 > < LIKE）。
3. 目的是为了减少回表（如果已经是覆盖索引 Using index，就不需要 ICP 了，因为压根不需要回表）。

为什么InnoDB选择 B+ 树作为索引的数据结构

InnoDB 选择 B+ 树 而不是 B 树、二叉树或哈希表，根本原因只有两个：

1. 为了减少磁盘 I/O 次数（让树尽可能“矮胖”）。
2. 为了方便范围查询和排序（这是数据库最常做的操作）。

下面详细对比 B+ 树与其他数据结构的劣势，你就明白为什么 B+ 树是“天选之子”了。

---

1. 为什么不用 B 树 (B-Tree)？

B 树和 B+ 树非常像，唯一的区别在于：B 树的非叶子节点（中间节点）也存储数据。

A. 树的高度问题 (磁盘 I/O)

• B 树： 因为中间节点存了数据（比如一行表记录），那么一个 16KB 的数据页（Page）能存下的“索引键值”就变少了。
  • 结果： 树的分叉（Fan-out/扇出）变少，树为了存下同样多的数据，只能往“高”了长。树越高，查询时需要的磁盘 I/O 次数就越多。
• B+ 树： 非叶子节点只存索引（key），不存具体数据。
  • 结果： 一个 16KB 的页可以存下成千上万个索引键。这使得 B+ 树非常“矮胖”。
  • 数据： 哪怕是千万级的数据量，B+ 树的高度通常也只有 3 层左右。这意味着只需要 1-3 次磁盘 I/O 就能找到数据。

B. 范围查询问题 (最致命的差距)

• B 树： 节点之间是独立的。如果你要查 SELECT * FROM table WHERE id > 10，在 B 树中，你可能需要进行“中序遍历”，在树的各个层级之间反复跳跃（上一层、下一层、再上一层），这是大量的随机 I/O，性能极差。
• B+ 树： 所有的数据都按顺序存放在叶子节点，且叶子节点之间通过双向链表连接。
  • 做法： 只需要找到 id=10 的位置，然后沿着链表向后遍历即可。这是顺序 I/O，速度极快。

---

2. 为什么不用二叉查找树 (AVL / 红黑树)？

二叉树也就是一个节点只能有两个孩子。

• 树太高了： 数据库的数据量通常很大（百万、千万级）。如果是二叉树，存 100 万行数据，树的高度大概是 $log_2(1,000,000) \approx 20$ 层。 这意味着查一条数据可能需要 20 次磁盘 I/O。相比之下，B+ 树只需要 3 次。
  • 形象比喻： 二叉树像一个瘦高的竹竿，B+ 树像一个矮胖的墩子。爬竹竿肯定比跨墩子累。
• 物理存储不友好： 数据库的数据是按“页”（Page，通常 16KB）读取的。二叉树的一个节点很小，读取一个节点就浪费了一次 I/O 加载整个页的机会。而 B+ 树的一个节点设计大小正好等于一页，利用率最高。

---

3. 为什么不用哈希表 (Hash)？

哈希索引在精确查找（如 WHERE id = 1）时速度是 $O(1)$，比 B+ 树还快，但它有两个致命弱点，导致它无法成为主流通用引擎的数据结构：

1. 不支持范围查询： 哈希是无序的。你没法高效地做 WHERE id > 10 或 ORDER BY id。
2. 不支持模糊查询： LIKE 'ABC%' 这种操作哈希完全做不了。
3. 哈希冲突： 数据量巨大时，哈希冲突会影响性能。 (注：InnoDB 内部有“自适应哈希索引”，但这属于内存优化，不是持久化的存储结构)

---

总结：B+ 树的“必杀技”

特性	B+ 树	B 树	二叉树	哈希表
单点查询效率	高 (1-3次 I/O)	高 (可能比 B+ 树快一点点，如果数据在根节点)	低 (树太高)	极高 (O(1))
范围查询效率	极高 (链表顺滑)	低 (反复回溯)	一般	无法支持
树的高度	矮胖 (3层存千万数据)	较高	极高 (瘦高)	N/A
磁盘利用率	高 (非叶子节点全存索引)	低 (存了数据占地方)	低	N/A

结论： InnoDB 选择 B+ 树，是因为它在**“保持树的层级尽可能低（少读盘）”和“支持高效的范围扫描（顺序读盘）”**之间找到了完美的平衡点。