B 树、B + 树完整详解 + MySQL 选用 B + 树的核心原因

一、前置基础磁盘 IO 是数据库性能瓶颈数据库索引存在磁盘上磁盘读取有巨大开销磁盘寻道、旋转耗时远大于内存运算磁盘按页Page读写MySQL 默认一页 16KB一次 IO 读取一整页数据索引设计核心目标最小化磁盘 IO 次数减少树的高度。二叉搜索树、平衡二叉树缺陷树高极高查询需要大量磁盘 IO不适合磁盘存储因此诞生多路平衡查找树 ——B 树 / B 树。二、B 树多路平衡查找树1. B 树定义m 阶 B 树m 代表最大子节点数节点关键字数量ceil(m/2)-1 ≤ 关键字数 ≤ m-1每个关键字同时存储索引键 完整数据行n 个关键字对应n1个子节点所有叶子节点在同一层绝对平衡关键字有序左子树 当前键 右子树。2. B 树结构示例3 阶 B 树最多 2 个关键字3 个子节点plaintext[20,50] / | \ [10,15] [30,40] [60,80,90]每个节点里索引值 对应整条数据查找逻辑从根节点对比关键字命中直接取数据否则向下遍历子节点范围查询需要上下遍历多个节点叶子无链表相连。3. B 树优缺点优点多路平衡树高远低于二叉树IO 次数少命中关键字直接拿到数据单条数据查询平均 IO 少。缺点节点同时存索引 数据单页能存放的索引数量极少树高更高范围查询极差叶子节点无链表区间扫描需要多次回溯上层节点插入删除会频繁分裂 / 合并节点磁盘页分裂开销大。三、B 树B 树改良版MySQL 索引底层1. B 树核心特性m 阶区分非叶子节点索引层、叶子节点数据层非叶子节点只存索引键不存真实数据仅用于路由查找叶子节点存储全部索引键 完整行数据且所有叶子节点通过双向链表串联。关键字规则非叶子关键字 下层子树最小关键字所有数据只存在叶子节点上层只是索引导航所有叶子节点高度一致天然平衡叶子链表有序支持顺向 / 逆向范围遍历。2. B 树结构示例plaintext[20,50,80] / | \ [10,15] [30,40] [60,70] / \ / \ / \ [10,15] [20] [30][40] [50] [60,70] [80,90] ↑——————————————————————————————————————↑ 叶子节点双向链表有序串联上层节点只有索引体积极小全部数据落在最底层叶子链表串联。3. B 树优缺点优点单页存储更多索引树极低IO 更少非叶子节点不存数据一页 16KB 可以存放成千上万索引键树高通常 2~3 层百万 / 千万数据仅 2 次磁盘 IO。范围查询、全表扫描性能碾压 B 树找到区间起点后直接顺着叶子链表向后遍历无需回溯上层节点分页、between、like 前缀匹配效率极高。查询性能稳定任何查询都必须走到叶子节点单条数据最多 3 次 IO不会出现 B 树 “根节点直接命中” 的极端快慢差距性能可控。插入删除更友好磁盘页分裂更少上层节点仅做路由数据变动只影响叶子节点非叶子节点改动频率极低减少磁盘页分裂、合并开销。叶子链表便于数据库优化预读缓存磁盘有顺序预读机制连续叶子节点物理存储相邻批量读取可以充分利用磁盘预读缓冲区。缺点等值查询略逊于 B 树B 树根节点命中直接返回B 树必须走到叶子多一次 IO但工程中树高仅 2-3 层差距可以忽略。四、MySQL 为什么放弃 B 树选用 B 树做索引底层InnoDB、MyISAM 索引底层均为 B 树四大核心原因1. 极大降低树高度减少磁盘 IO最关键磁盘 IO 是数据库最大性能瓶颈。B 树节点存索引 数据一页能放的索引少同等数据量树更高B 树非叶子节点纯索引一页容纳海量索引千万级数据树高仅 2~3 层。 一次 SQL 查询最多 2~3 次磁盘读取性能大幅提升。2. 完美适配数据库高频场景范围查询、分页、排序业务中大量 SQL 不是等值查询 between order by limitB 树叶子无链表区间查询需要来回遍历上层节点频繁换页 IOB 树叶子有序双向链表找到起始值后连续向后读取一次连续磁盘扫描即可完成范围遍历。 全表扫描等价于遍历叶子链表效率远高于 B 树。3. 查询性能稳定优化器更容易预估成本B 树查询波动极大根命中 1 次 IO叶子命中多层 IO B 树无论查询哪条数据都必须走到叶子节点IO 次数固定MySQL 优化器可以精准统计扫描行数、评估 SQL 执行代价生成更优执行计划。4. 磁盘读写、缓冲利用更高效磁盘预读特性操作系统读取磁盘时会预读相邻页放入缓存B 树叶子有序连续批量查询能充分利用预读缓存缓冲池利用率高非叶子节点体积小会长期缓存在 InnoDB Buffer Pool内存中绝大多数路由查找直接走内存只有叶子节点需要磁盘 IO增删改开销更低数据修改仅影响叶子节点上层索引很少变动减少磁盘页分裂、合并带来的随机写开销。补充InnoDB 主键索引 vs 普通索引 B 树差异聚簇索引主键索引叶子节点存储完整整行数据一张表只有一棵聚簇 B 树。二级索引普通索引叶子节点只存储主键值查询到主键后再回表查询聚簇索引获取完整数据。 二者底层结构都是 B 树只是叶子存储内容不同。总结对比表表格特性B 树B 树MySQL 适配度节点存储内容索引 数据共存上层仅索引叶子存全部数据B 树更优树高度同等数据量更高极低2~3 层B 树更优等值查询偶尔更快根命中稳定多一次 IO差距极小接近范围 / 分页查询差频繁回溯极强链表顺序遍历B 树碾压磁盘 IO 次数更多极少B 树更优内存缓存利用率低节点大缓存少上层索引常驻内存B 树更优增删改页分裂开销大小仅叶子变动B 树更优