B+树揭秘：MySQL索引核心原理全解析

MySQL 索引按不同维度可以分成多类底层核心是 ‌B 树‌配合 ‌哈希索引‌ 做特定场景加速整体查询时间复杂度为 ‌O(log N)‌。索引类型‌按数据结构‌B 树索引、哈希索引、全文索引倒排索引、空间索引R-Tree。‌按物理存储‌聚簇索引叶子节点存整行数据InnoDB 主键默认和非聚簇索引叶子节点存数据地址或主键值MyISAM 默认。‌按字段特性‌主键索引、唯一索引、普通索引、全文索引。‌按字段个数‌单列索引、联合索引复合索引遵循最左前缀原则。‌‌底层实现原理‌B 树是 MySQL 默认且最核心的索引结构‌InnoDB 和 MyISAM 都支持它的设计目标就是减少磁盘 I/O‌非叶子节点只存索引键‌不存数据因此单个节点能容纳大量键值树高度很低通常 2~4 层查询任意数据只需少量磁盘 I/O。‌所有数据都存在叶子节点‌且叶子节点通过有序链表串联范围查询BETWEEN、、和排序效率极高直接沿链表遍历即可。‌数据物理有序‌聚簇索引下InnoDB 表数据本身按主键顺序存储在 B 树的叶子节点上主键查询直接定位到行数据。‌‌‌哈希索引‌ 在 InnoDB 中以“自适应哈希索引”形式存在当某个索引值被频繁访问时InnoDB 会在 B 树之上自动构建哈希索引等值查询可以 O(1) 定位但‌不支持范围查询‌且该过程由引擎自动管理无法人工干预。‌‌‌MyISAM 与 InnoDB 的关键差异‌MyISAM 的索引叶子节点存的是‌数据行的物理地址‌查到地址后直接取数据InnoDB 的二级索引叶子节点存的是‌主键值‌需要再回主键索引树查一次回表查询。‌‌时间复杂度对比引类型等值查询范围查询排序说明B 树索引O(log N)O(log N M)支持M 为结果集大小InnoDB 默认哈希索引O(1)不支持不支持仅等值有哈希冲突风险全文索引O(N)不支持不支持倒排索引实现关键词匹配无索引全表扫描O(N)O(N)不支持性能最差B 树查询之所以稳定在 O(log N)是因为‌树高可控‌通常 3~4 层百万和千万级数据量下等值查询耗时几乎一致而哈希索引虽然等值 O(1)但无法用于范围查询和排序所以不能作为通用索引结构。‌‌面试/理解要点‌为什么不用哈希做默认索引‌等值查询虽快但数据库高频操作是范围查询和排序哈希完全无法支持。‌为什么不用二叉树/红黑树‌数据量巨大时树高过深每次向下查找都是一次磁盘 I/O性能急剧下降B 树通过多路分支大幅降低树高。‌聚簇索引与二级索引‌InnoDB 表必有且仅有一个聚簇索引优先主键二级索引查询通常需要回表‌覆盖索引‌可以避免回表是常见优化手段。‌联合索引最左前缀‌复合索引查询时必须从最左列开始否则索引失效这是 B 树结构直接决定的。‌‌MySQL 索引按不同维度可以分成好几类底层最核心的实现是 ‌B树‌InnoDB 引擎下主键索引就是典型的聚簇索引。下面给你按分类讲清楚再配个例子说明查找过程。按数据结构分类‌B树索引‌绝大多数存储引擎的默认索引类型也是 InnoDB 和 MyISAM 最常用的实现方式。数据有序存储支持等值、范围和排序查询。‌哈希索引‌能以 O(1) 时间复杂度做等值查找但数据无序不支持范围查询。InnoDB 有个特殊优化叫“自适应哈希索引”当某个索引值被频繁访问时会在 B树之上自动建一层哈希索引兼顾两者优点。‌全文索引‌用于在文本列中查找关键词而不是比较是否相等。底层用倒排索引实现记录“关键词 → 所在文档”的映射配合MATCH AGAINST使用。MyISAM 一直支持InnoDB 从 MySQL 5.6.4 开始支持。‌空间数据索引‌用于存储地理数据能从所有维度索引数据支持任意维度组合查询。MyISAM 支持MySQL 从 5.7 版本开始支持。按应用功能分类‌普通索引‌最基本的索引基于普通字段建立没有任何限制创建方式CREATE INDEX idx_name ON table(col);‌唯一索引‌与普通索引类似但索引字段的值必须唯一允许有空值。创建或修改表时加唯一约束会自动创建对应索引。‌主键索引‌一种特殊的唯一索引不允许有空值。每个表只能有一个主键InnoDB 中它同时就是聚簇索引。‌复合索引联合索引‌在多个列上建立的索引如(a, b, c)。相比多个单列索引复合索引开销更小但使用时必须遵循‌最左前缀原则‌——查询条件从最左列开始连续匹配才能用到索引。按物理存储分类‌聚簇索引聚集索引‌叶子节点直接存储完整行数据数据物理顺序与索引顺序一致。InnoDB 中主键索引就是聚簇索引一个表只能有一个。如果没有定义主键InnoDB 会选第一个非空唯一索引再没有的话自动生成一个 6 字节的隐藏主键。‌非聚簇索引二级索引/辅助索引‌叶子节点不存完整行数据只存索引字段值和主键值。通过二级索引查数据时需要先用主键到聚簇索引里再查一次这个过程叫‌回表‌。MyISAM 的索引叶子节点存的是数据行地址也属于非聚簇实现。底层实现原理举例‌InnoDB 主键查询‌假设有一张用户表user(id, name, age)id是主键。InnoDB 会把整张表按主键id构建成一棵 B树树的叶子节点就是完整的数据行。当执行SELECT * FROM user WHERE id 5时从根节点开始二分查找约 2—3 次磁盘 I/O 就能定位到叶子节点直接取出整行数据速度非常快。‌二级索引回表查询‌如果给name建了普通索引会再生成一棵 B树叶子节点存的是(name, id)。执行SELECT * FROM user WHERE name 张三时先在这棵二级索引树里找到id再用id到主键聚簇索引树里查完整行数据——这就是回表。如果只查SELECT id FROM user WHERE name 张三二级索引里已经有id不需要回表这种情况叫‌覆盖索引‌效率更高。‌为什么选 B树而不是其他结构‌数据库的瓶颈在磁盘 I/O。二叉树或红黑树每个节点只能存一个 key数据量大时树很高查询要多次 I/OB树虽然能存多个 key但非叶子节点也存数据单个节点能容纳的 key 数量有限。B树的非叶子节点只存索引不存数据同样大小的节点能存更多 key树更矮千万级数据通常 3 层一次查询只需 2—3 次磁盘 I/O而且叶子节点用链表串起来范围查询和排序遍历非常高效。‌‌使用建议‌主键尽量用自增整型‌避免用 UUID 等随机值。随机主键会导致频繁页分裂和碎片自增主键顺序写入效率最高。‌复合索引遵循最左前缀原则‌比如建立了(a, b, c)索引查询条件里有a和c但缺b只有a能用上索引。‌索引不是越多越好‌每个索引都要额外占用存储空间还会拖慢插入、更新和删除操作。