mysql索引底层采用b+树，因其相比二叉树和b树更适配磁盘io：b+树非叶节点仅存键和指针，树高仅2~4层，叶子节点存全量数据并以双向链表连接，兼顾高效单值与范围查询。

MySQL 索引底层用树结构表达，核心是B+树——它不是凭空设计的，而是从简单到复杂、从内存友好到磁盘友好的演进结果。用树结构讲清楚，关键在对比层级、节点内容和数据流向。

为什么不用二叉树？树太高、太瘦、太耗磁盘IO

二叉搜索树每个节点只存1个键+1个指针，插入有序数据（如1,2,3,…）会退化成链表，查找变O(N)。即使改用红黑树或AVL树，高度仍达20~30层（千万级数据）。每次比较都要一次磁盘读取（毫秒级），20次IO就是20毫秒以上——数据库无法接受。

B树：把“一页”当一个节点，树开始变矮

B树让每个节点容纳多个键和多个子指针，节点大小对齐磁盘页（如16KB）。例如一个节点存100个键，三层B树就能索引百万级记录。但它仍有缺陷：

deep-java-review

Java项目代码review工具。分析Git变更+完整调用链路上下文，推断业务需求，进行多维度评分和分类汇总，生成完整PRD文档。包含细粒度Java代码审查清单（Null安全、异常处理、Streams、并发、equals/hashCode、资源管理、API设计、性能、MyBatis/ORM、事务边界、SQL/DD...

下载

• 非叶子节点也存数据（或数据指针），挤占空间，限制单节点键数量
• 范围查询要中序遍历整棵树，无法连续读取

B+树：数据全沉底、叶子连成链，专为磁盘优化

这是InnoDB实际使用的结构，树形逻辑清晰可拆解为三层：

• 根节点和中间层：只存索引键 + 子节点指针，不存任何真实数据。比如INT键（4字节）+指针（6字节）≈10字节，16KB页能塞约1600个键 → 分叉多、树高仅2~4层
• 叶子节点：存完整数据行（聚集索引）或主键值+指针（二级索引），且所有叶子节点用双向链表串起来
• 查找路径固定：无论查单值还是范围，都必须走到叶子节点；等值查走树向下，范围查定位起点后沿链表向右扫

树结构图示一句话总结

想象一棵倒挂的树：顶部是轻量索引层（只有键和指针），底部是一排平铺的数据层（带前后链接），所有查询都从顶到底、再在底端横着走——这就是B+树用树结构说清索引原理的方式。