MySQL 索引数据结构与算法一、索引的本质索引是帮助 MySQL 高效获取数据的排好序的数据结构通过优化查找路径提升查询效率。类比书的目录——无需逐页翻阅即可快速定位。二、索引数据结构对比1. B-Tree[20 | 40] / | \ [5|10] [25|30] [50|60]所有叶节点深度相同节点内索引元素不重复数据从左到右递增排列叶节点指针为空2. BTreeMySQL 主力索引[20 | 40] ← 非叶子节点仅索引不存数据 / | \ [5|10] → [25|30] → [50|60] ← 叶子节点存完整数据双向链表 data data data与 B-Tree 的核心区别特性B-TreeBTree非叶子节点存索引数据仅存冗余索引容纳更多项树更低更胖叶子节点无链表连接双向指针串联范围查询极快数据存储分散在各层节点全部在叶子节点查找稳定性可能中途命中必须查到叶子节点IO 次数稳定3. Hash 表key → hash(key) → 桶定位 → 数据优势劣势等值查询、IN极快不支持范围查询、、BETWEEN单条定位 O(1)存在 hash 冲突不支持排序和部分索引匹配三、BTree 深度解析1. 为什么 BTree 比二叉树更适合磁盘存储二叉搜索树 100 高度 节点数 → 磁盘 IO 次数多 / \ 50 200 / \ 30 70 每层一个节点 → 一次磁盘 IO → 效率低 BTree [100 | 200 | 300] 高度 3~4 层每层存几百个索引 / | | \ [叶子叶子叶子叶子叶子叶子] 一个节点 一个磁盘页16KB→ IO 次数少核心思想让每个节点大小等于磁盘一页16KB一次 IO 读入大量索引项从而将树高度控制在 3~4 层百万级数据仅需 2~4 次 IO。2. 叶子节点链表的作用[1|data] → [3|data] → [5|data] → [7|data] → [9|data] ↑ ↓ └──────────── 双向链表遍历 ←────────────────┘等值查询从根走 BTree 到叶子范围查询定位起点后沿链表顺序遍历无需回到非叶子节点 —— 这是 BTree 相比 B-Tree 的最大优势四、存储引擎的索引实现1. MyISAM非聚集索引.MYI 索引文件 .MYD 数据文件 ┌──────────┐ ┌──────────┐ │ 索引 指针 │ ──────→ │ 完整数据行 │ └──────────┘ └──────────┘索引与数据分离存储叶子节点存的是数据物理地址主键索引和二级索引结构相同2. InnoDB聚集索引主键索引聚集索引 二级索引非主键索引 ┌─────────────────┐ ┌───────────────┐ │ 主键 完整数据行 │ │ 索引列 主键值 │ │ 数据即索引 │ │ 不存完整数据 │ └─────────────────┘ └───────┬───────┘ ↑ │ └─────── 回表查询 ←─────────────────┘核心特点表数据文件本身就是按 BTree 组织的索引结构聚集索引叶子节点存完整数据记录二级索引叶子节点只存主键值查到后还需回表取完整数据两个关键问题Q1为什么 InnoDB 表建议必须有主键且推荐整型自增InnoDB 用主键组织 BTree无主键则自动选唯一键都没有则生成隐藏 rowid6 字节无业务意义整型比大小快占用空间小4/8 字节UUID 字符串长且无序自增新数据永远追加到最右叶子避免页分裂和索引重建写入效率最高Q2为什么二级索引叶子节点存主键值而不是数据地址数据一致性数据移动页分裂时只需维护主键索引二级索引无需更新节省空间避免每条记录在多个索引中重复存储完整数据五、联合索引与最左前缀联合索引结构示例(a, b, c)联合索引BTree 按 (a, b, c) 字典序排列 (1,1,1) → (1,2,2) → (1,2,3) → (2,1,1) → (2,3,4) → (3,1,2) 先按 a 排 → a 相同时按 b 排 → b 相同时按 c 排最左前缀原理SQL 条件是否走索引原因WHERE a 1走命中第一列WHERE a 1 AND b 2走命中前两列WHERE a 1 AND b 2 AND c 3a、b 走c 不走范围查询后的列索引失效WHERE b 2不走跳过第一列无法定位WHERE a 1 AND c 3仅 a 走中间断档c 无法使用本质原因BTree 按联合索引从左到右排序跳过左边就无法利用有序性定位。总结知识点核心要点BTree非叶子仅索引叶子链表串联适合磁盘存储和范围查询聚集索引InnoDB 数据即索引叶子存完整行二级索引叶子存主键值查完需回表主键建议整型自增 → 避免页分裂写入高效联合索引遵循最左前缀范围查询右侧列失效