数据库索引，是数据库管理系统中一个排序的数据结构，以协助快速查询、更新数据库表中数据。索引的实现通常使用 BTree 及其变种 B+Tree。

一句话定义之后，原理要回答四个问题：索引凭什么快（数据结构）、代价是什么（写放大与空间）、B+Tree 长什么样（节点与指针）、以及”回表/覆盖索引”这些高频词在结构上对应什么。本文逐层拆开。

索引凭什么快：把无序扫描变成有序查找

无索引时查询是全表扫描 O(N)；索引把键值组织成有序的多路搜索树，查找变为 O(logN) 的树下行。以千万行表为例：全表扫千万次 IO vs B+Tree 三四层树高即三四次 IO——索引的本质是用预排序换查询路径。

B+Tree 结构细节（InnoDB 视角）

  • 非叶节点只存键与子指针（不存行数据），一页（16KB）能装上千个键 → 树极矮：千万行约 3-4 层
  • 叶节点存完整索引记录（二级索引存键+主键值；聚簇索引存整行），且叶节点间以双向链表相连 → 范围查询（BETWEEN/>/<）沿链表顺序扫，无需回溯树
  • 插入分裂、删除合并维持平衡与填充率（约 15/16 填充），保证树高稳定

对比被放弃的方案：哈希（等值 O(1) 但不支持范围与排序）、二叉树（树高 log2(N) 太深、IO 次数多）、跳表（内存结构友好但磁盘页利用率低）、B-Tree（非叶存数据浪费页空间）——B+Tree 是为磁盘页模型量身定制的。

聚簇与二级索引：回表的来源

  • 聚簇索引（主键索引）：叶节点即整行数据，表本身就是这棵树
  • 二级索引：叶节点存”索引键 + 主键值”；按二级索引查到主键后，若查询列不在索引中，需拿主键回聚簇索引再查一次（回表）
  • 覆盖索引：查询列全部包含在二级索引中（含主键），无需回表——EXPLAIN 中 Extra: Using index 即此；优化慢查询的第一板斧

索引的代价

  • 写放大：每次 INSERT/UPDATE/DELETE 需维护所有二级索引（多棵树同时改），索引越多写越慢
  • 空间：每个二级索引约等于一份”键+主键”的副本
  • 维护：页分裂产生碎片（OPTIMIZE/重建）、统计信息过期影响优化器选索引

所以索引设计是读写权衡：按查询负载建索引，而非”每列都建”。

优化器与索引选择

优化器基于统计信息（基数 cardinality）估算各索引成本选执行计划；常见”索引失效”场景：对索引列做函数/运算、隐式类型转换（字符串列传数字）、前导模糊 LIKE ‘%x’、OR 连接非索引列、基数过低优化器弃用（如性别列）。索引原理决定失效规律：任何破坏”有序可二分”性质的用法都会让树查找退化为扫描。

原理速记

索引 = 为磁盘页模型优化的有序多路树（B+Tree）：矮树高换少 IO、叶链表换范围扫、聚簇/二级之分产生回表与覆盖索引、写放大与空间是它的价格。把这五句话串起来，索引相关的全部高频问题（为什么快、为什么慢、为什么失效、为什么要覆盖）都有了统一答案。