为什么需要索引
假设一张用户表有 100 万行数据，执行 SELECT * FROM users WHERE id = 500000。如果没有索引，数据库只能逐行扫描，直到找到匹配的行——最坏情况下要读取 100 万行。有了索引，数据库可以直接定位到目标行，通常只需 3~4 次磁盘 I/O。这就是索引的核心价值：把 O(n) 的全表扫描变成 O(log n) 的查找。
索引的底层结构：B+ 树
大多数关系型数据库（MySQL InnoDB、PostgreSQL 等）的默认索引结构是 B+ 树。它是一种平衡多路查找树，具有以下特点：
- 所有数据都存储在叶子节点，非叶子节点只存键值，用于导航。
- 叶子节点之间用指针相连，形成有序链表，便于范围查询。
- 树的高度通常很低。例如 InnoDB 一个页默认 16KB，若每行索引记录约 100 字节，一个节点可存上百个键值，100 万行数据树高一般只有 3 层左右。
这意味着查找一个值时，只需从根节点向下走 3 次，每次读取一个页（通常缓存在内存中），就能定位到叶子节点。
索引如何加速查询
1. 等值查询
WHERE id = 500000：B+ 树从根节点开始，比较键值决定走哪个分支，最终到达叶子节点找到对应记录。时间复杂度 O(log n)。
2. 范围查询
WHERE age BETWEEN 20 AND 30：先在 B+ 树中找到 age=20 的位置，然后沿着叶子节点的链表顺序扫描，直到 age>30 停止。因为叶子节点有序且相连，范围扫描非常高效。
3. 排序与分组
如果查询包含 ORDER BY age，且 age 上有索引，数据库可以直接按索引顺序读取数据，避免额外的排序操作（filesort）。
4. 覆盖索引
如果查询需要的列都包含在索引中（例如 SELECT age FROM users WHERE age > 20，索引为 (age)），数据库无需回表读取完整行，直接从索引返回结果，进一步减少 I/O。
索引的代价
索引不是免费的午餐：
- 占用存储空间：每个索引都需要额外的磁盘空间。
- 降低写入速度：INSERT、UPDATE、DELETE 都需要维护索引，导致写入变慢。
- 可能不被使用：如果查询条件区分度低（如性别字段），优化器可能选择全表扫描。
因此，索引应建在高频查询、区分度高的列上，避免过度索引。
如何验证索引是否生效
以 MySQL 为例，使用 EXPLAIN 命令查看执行计划：
EXPLAIN SELECT * FROM users WHERE id = 500000;
关注输出中的 type 列（如 const、ref、range 表示使用了索引，ALL 表示全表扫描）和 key 列（实际使用的索引）。
小结
索引通过 B+ 树等数据结构，将随机查找转化为有序查找，从而大幅减少磁盘 I/O。理解其原理后，你就能更合理地设计索引：在加速查询和写入开销之间取得平衡。