数据库索引原理与优化

一、为什么数据库选择 B\+ 树作为索引结构

数据库存储的数据常驻磁盘，磁盘读写的最大开销是随机 IO。相比二叉树、红黑树、哈希表等结构，B+ 树具备层高更低、磁盘读写更少、区间查询极强、数据有序的特点，完美适配数据库海量数据、范围查询、分页查询的业务场景，因此 MySQL InnoDB 引擎默认采用 B+ 树实现索引。

B+ 树是一种多路平衡查找树，所有节点严格平衡，叶子节点在同一层，保证每次查询的磁盘 IO 次数稳定可控。B+ 树最核心的设计特点是非叶子节点与叶子节点职责完全分离。

B+ 树的所有非叶子节点（根节点、中间节点）仅存储索引键值 + 子节点指针，不会存储任何行数据。非叶子节点的唯一作用就是路由检索，指导查询流程向下一层匹配，快速缩小查询范围。

该设计让单个节点能够存储海量索引键，树的层高极低。哪怕存储千万级数据，B+ 树层高通常仅为 3~4 层，意味着一次查询最多只需要 3~4 次磁盘 IO，查询效率极其稳定。

B+ 树的所有真实数据全部存储在叶子节点，所有叶子节点按照索引键从小到大有序排列，并且叶子节点之间通过双向链表串联。

这种结构带来两个巨大优势：第一，等值查询精准高效；第二，范围查询、分页查询、排序查询无需再次排序，直接遍历链表即可完成，完美适配数据库高频业务场景。

MySQL InnoDB 引擎的索引分为两大类：聚簇索引（主键索引）和二级索引（普通索引、辅助索引），二者存储结构、查询逻辑、数据存放形式完全不同，也是索引优化的核心理论基础。

聚簇索引是数据表的核心索引，每张表有且仅有一个聚簇索引。InnoDB 会根据主键自动生成聚簇索引，如果没有主键则选用唯一索引，无唯一索引则自动生成隐藏 rowid 作为聚簇索引。

聚簇索引最大特点：索引和真实行数据完全绑定、存放在一起。

聚簇索引的 B+ 树叶子节点，直接存储整行完整数据。通过主键查询时，命中叶子节点即可直接拿到所有字段数据，无需二次查询，因此主键查询是数据库中速度最快的查询方式。

同时数据表在磁盘上的物理存储顺序，完全按照聚簇索引排序，这也是“聚簇”的含义：数据和索引聚集存储。

除聚簇索引外的所有索引统称为二级索引，包括普通单列索引、联合索引、唯一索引等。二级索引的结构和聚簇索引完全不同：叶子节点不存储完整行数据。

二级索引的 B+ 树叶子节点，仅存储「索引键 + 主键值」。当我们通过二级索引查询数据时，流程分为两步：

第一步：在二级索引树中根据字段检索，拿到对应的主键 ID；

第二步：拿着主键 ID 再次去聚簇索引中查询完整行数据。

这个二次查询聚簇索引获取完整数据的过程，就是数据库经典的回表查询。

回表查询会产生额外的磁盘 IO，是二级索引慢于主键查询的核心原因，也是日常 SQL 优化需要重点规避的场景。而覆盖索引的设计原理，就是让二级索引叶子节点包含查询所需的全部字段，避免回表，大幅提升查询性能。

1. 数据库索引基于 B+ 树实现，非叶子节点仅用于路由、不存数据，层高极低、IO 开销极小；

2. 所有真实数据全部存放于有序叶子节点，天然适配等值、范围、排序、分页查询；

3. 聚簇索引数据与索引合一，主键查询无需回表，性能最优；

4. 二级索引仅存储索引键和主键，查询大概率需要回表，存在性能损耗，可通过覆盖索引优化。

理解 B+ 树结构与两类索引的差异，是掌握慢查询优化、索引失效、覆盖索引、最左匹配原则的底层前提。