MySQL 索引

一、索引是什么？为什么需要索引？

核心目的：提高数据库 查询效率。
类比：就像书的目录，可以快速定位到需要查找的内容，避免全表扫描。
实现层面：在 MySQL 中，索引是在 存储引擎层 实现的（如 InnoDB, MyISAM），因此不同引擎的索引实现可能不同。

二、常见的索引模型（数据结构）

哈希表 (Hash Table)：
- 结构：键值 (Key-Value) 存储，通过哈希函数计算 Key 的位置。可能存在哈希冲突，常用链表法解决。
- 优点：等值查询 速度极快（理论 O(1)）。
- 缺点：范围查询 效率低（需要扫描整个链表或全表），无法利用索引排序。
- 适用场景：只有等值查询的场景，如 Memcached、某些 NoSQL。
有序数组 (Sorted Array)：
- 结构：按索引列的值排序存储。
- 优点：等值查询 (O(logN) - 二分查找) 和 范围查询 效率都很高。
- 缺点：更新（插入、删除） 成本高，需要移动大量元素来维护有序性。
- 适用场景：静态数据 或很少变更的数据，如历史人口信息。
搜索树 (Search Tree)：
- 二叉搜索树：左子节点 < 父节点 < 右子节点。查询/更新理论 O(logN)。
  - 问题：树可能不平衡，退化成链表。需要平衡二叉树（如 AVL, 红黑树）来保证性能。
  - 数据库不常用原因：树高相对较高。数据库索引不仅在内存，还要 读写磁盘。树高意味着可能需要多次磁盘 I/O（机械硬盘随机读写慢，约 10ms/次），性能差。
- N 叉树 (B-Tree / B+ Tree)：为了 减少磁盘 I/O 次数 而生。
  - 特点：每个节点可以存储更多的数据和指针（N 很大，取决于数据块大小，如 InnoDB 中 N ≈ 1200），树的高度 非常低（如 3-4 层就能存几十亿条记录）。
  - 优势：查询时访问的数据块少，大大减少磁盘随机读次数。非常适合磁盘存储。
  - B+ 树：是 B-Tree 的变种，被 InnoDB 等数据库广泛使用。
    - 非叶子节点只存 Key，不存 Data，可以容纳更多 Key，进一步降低树高。
    - 叶子节点包含所有 Key 和对应的 Data (或 Data 指针)。
    - 叶子节点之间有 双向链表 连接，便于范围查询。

三、 InnoDB 索引模型 (B+ Tree 实现)

索引组织表 (Index-Organized Table)：InnoDB 的表数据本身就是按照主键顺序存放在一个 B+ 树（聚簇索引）中的。
索引类型：
- 主键索引 (Primary Key Index) / 聚簇索引 (Clustered Index)：
  - 叶子节点存储的是 整行数据。
  - 一张表 只有一个 聚簇索引。
- 非主键索引 (Non-Primary Key Index) / 二级索引 (Secondary Index)：
  - 叶子节点存储的是 主键的值。
  - 一张表可以有多个二级索引。
查询过程与回表 (Table Access by Index)：
- 主键查询：SELECT * FROM T WHERE ID = 500; -> 只需搜索 主键索引树 一次。
- 二级索引查询：SELECT * FROM T WHERE k = 5;
  1. 搜索 k 索引树，找到 k=5 对应的 主键值 (ID=500)。
  2. 拿着主键值 ID=500，再搜索 主键索引树，找到对应的行数据。
  3. 这个 第 2 步 就是回表。基于二级索引的查询（如果需要非索引列数据）通常需要多扫描一棵树。
- 优化原则：尽量使用主键查询，或者使用覆盖索引避免回表。

四、索引优化技术

覆盖索引 (Covering Index)：
- 定义：一个查询语句所需要的数据，仅仅从二级索引树中就能全部获取到，不需要回表。
- 例子：SELECT ID FROM T WHERE k BETWEEN 3 AND 5; (假设有 index k(k))，ID 值就在 k 索引树的叶子节点上。
- 优点：减少树搜索次数（避免回表），显著提升查询性能。
- 应用：为高频查询创建冗余的联合索引以实现覆盖。如为 根据身份证号查姓名 的高频请求，创建 (id_card, name) 联合索引，即使 id_card 本身已有索引。需要权衡索引维护成本和查询收益。
最左前缀原则 (Leftmost Prefix Principle)：
- 定义：对于 联合索引 (a, b, c)，查询条件使用索引列的 最左边连续的部分 时，可以用上索引。
- 适用情况：
  - WHERE a = 1 (使用 a)
  - WHERE a = 1 AND b = 2 (使用 a, b)
  - WHERE a = 1 AND b = 2 AND c = 3 (使用 a, b, c)
  - WHERE a = 1 AND c = 3 (仅使用 a)
  - WHERE b = 2 或 WHERE c = 3 (无法使用该索引)
- 字符串索引也类似：WHERE name LIKE '张%' 可以使用 name 索引。
- 索引设计原则：
  1. 复用性：调整联合索引内字段顺序，看是否能覆盖更多的查询场景（比如有了 (a, b) 就可能不需要单独的 (a) 索引了）。优先考虑能减少索引总数的顺序。
  2. 空间：如果无法通过调整顺序减少索引，优先将选择性高或字段长度小的列放在前面（虽然 InnoDB 索引选择性影响不大，但长度影响空间）。如 (name, age) 和 (age) 比 (age, name) 和 (name) 可能更优（如果 name 比 age 长）。
索引下推 (Index Condition Pushdown - ICP)：(MySQL 5.6+ 引入)
- 场景：对于联合索引，查询条件中使用了索引的前缀，但还包含未形成前缀的其他索引列的条件。
- 例子：SELECT * FROM tuser WHERE name LIKE '张%' AND age = 10 AND ismale = 1; (索引 (name, age))
- 无 ICP (MySQL 5.6 之前)：
  1. 存储引擎根据 name LIKE '张%' 在索引树中找到所有匹配项。
  2. 对每一条匹配项，都进行回表。
  3. Server 层再根据 age = 10 和 ismale = 1 过滤数据。
- 有 ICP (MySQL 5.6 及之后)：
  1. 存储引擎根据 name LIKE '张%' 在索引树中找到匹配项。
  2. 在索引遍历过程中，同时判断 age = 10 是否满足 (因为 age 也在索引中)。
  3. 只对满足 name LIKE '张%' AND age = 10 的项 才进行回表。
  4. Server 层再根据 ismale = 1 过滤数据。
- 优点：在存储引擎层面就过滤掉了部分不满足条件的记录，显著减少回表次数。

五、索引设计与维护

主键选择：
- 自增主键 (推荐)：
  - 优点：插入时是追加操作，减少页分裂，性能好；主键通常较小 (int 4字节, bigint 8字节)，使得 二级索引更小，节省空间。
  - 缺点：与业务无关。
- 业务字段做主键 (如身份证号)：
  - 优点：对于典型的 KV 场景（只有一个唯一索引，且查询都基于此列），可以直接设为主键，避免回表。
  - 缺点：插入可能无序，导致 页分裂，性能较低；如果主键较长（如字符串），二级索引会很大。
- 结论：大部分场景下，推荐使用 自增主键。
索引维护：
- 页分裂 (Page Split)：当插入数据导致 B+ 树的某个叶子节点满了，需要分裂成两个节点，会影响性能并降低空间利用率 (约 50%)。无序插入更容易触发。
- 页合并 (Page Merge)：当删除数据导致相邻两个页利用率很低时，会合并成一个页。
- 重建索引：ALTER TABLE T DROP INDEX k; ALTER TABLE T ADD INDEX(k); (重建二级索引) 或 ALTER TABLE T DROP PRIMARY KEY; ALTER TABLE T ADD PRIMARY KEY(id); (重建主键/聚簇索引)。
  - 注意：重建主键索引代价很大，相当于重建整张表。重建二级索引相对较快。线上操作需谨慎，考虑使用 pt-online-schema-change 或 gh-ost 等工具。

六、核心原则与总结

索引的核心价值在于 提高查询效率，但会 增加写操作（INSERT/UPDATE/DELETE）的成本 和 存储空间。
理解不同索引模型（哈希、有序数组、B+树）的优缺点和适用场景。
深入理解 InnoDB 的 B+ 树实现：聚簇索引、二级索引、回表机制。
善用索引优化手段：覆盖索引、最左前缀原则、索引下推。
数据库设计的重要原则：在满足需求的前提下，尽量少地访问资源（减少磁盘 I/O、减少扫描行数）。
索引设计需权衡：查询性能、写入性能、存储空间、维护成本。没有绝对最优，只有相对适合。

MySQL 索引

一、 索引是什么？为什么需要索引？

二、 常见的索引模型（数据结构）

三、 InnoDB 索引模型 (B+ Tree 实现)

四、 索引优化技术

五、 索引设计与维护

六、 核心原则与总结

一、索引是什么？为什么需要索引？

二、常见的索引模型（数据结构）

四、索引优化技术

五、索引设计与维护

六、核心原则与总结