B树和B+树详解

在学习数据库索引、文件存储系统时B 树和 B 树是绕不开的核心数据结构。它们不只是面试高频考点更是 MySQL InnoDB 索引的底层基石。这篇博客用最通俗的语言从零讲清 B 树、B 树的结构、区别与实际应用看完就能理解为什么数据库非要用 B 树。一、先搞懂为什么需要 B 树 / B 树我们学过二叉查找树、红黑树它们查找效率很高O (logn)但为啥数据库不用反而要用 B 树 / B 树核心原因磁盘 I/O 太慢了。数据库数据存在磁盘上每次读取数据都要发生磁盘 I/O而磁盘 I/O 的速度远远慢于内存操作。树的高度越高磁盘 I/O 次数越多查询速度就越慢。二叉树结构容易变得很高数据量大时磁盘 I/O 次数爆炸。因此需要一种矮胖、多路平衡的树结构减少树的高度从而减少磁盘 I/O这就是 B 树和 B 树诞生的原因。二、什么是 B 树多路平衡查找树B 树也叫 B- 树是一种平衡的多路查找树这里的 “路” 可以理解为每个节点能存储的关键字数量。1. B 树的核心特性m 阶 B 树每个节点最多有m个子节点最少有ceil(m/2)个子节点根节点至少 2 个子节点只有根节点时例外每个节点中的关键字有序排列左子树关键字 当前关键字 右子树关键字所有叶子节点都在同一层保证绝对平衡每个节点既存储关键字也存储关键字对应的数据记录查找过程类似二分查找找到关键字就能拿到数据。2. B 树的查找流程从根节点开始加载节点到内存在节点内的有序关键字中二分查找找到目标直接返回数据没找到就根据大小关系进入对应的子节点重复查找直到叶子节点找到或查找失败。3. B 树的优缺点优点多路平衡树高度极低大幅减少磁盘 I/O节点内有序查找效率稳定每个节点都存数据找到关键字即可返回适合随机查找。缺点每个节点都存数据导致单个节点能存储的关键字变少树高会相对变高范围查询效率低需要遍历整棵树无法连续读取。三、什么是 B 树B 树的升级版B 树是 B 树的优化版本MySQL InnoDB 索引底层就是 B 树也是实际工程中最常用的结构。1. B 树的核心特性m 阶 B 树继承 B 树所有平衡、多路、有序的特性非叶子节点只存储关键字不存储真实数据仅用于索引导航所有数据都存储在叶子节点叶子节点包含全部关键字和对应数据叶子节点之间用双向链表连接形成有序链表结构非叶子节点的关键字会在叶子节点重复出现作为索引查找必须走到叶子节点才能拿到数据查找路径长度一致。2. B 树的查找流程从根节点开始根据关键字大小逐层向下查找非叶子节点只做导航不存数据一直走到叶子节点在叶子节点中找到目标数据范围查询时直接遍历叶子节点的链表即可无需回溯整棵树。3. B 树相比 B 树的关键优化非叶子节点不存数据单个节点能存储更多关键字树更矮磁盘 I/O 更少叶子节点链表化范围查询、排序查询极快完美适配数据库场景查询稳定性更强所有查询都必须走到叶子节点效率均匀更适合磁盘存储批量读取数据效率极高。四、B 树 vs B 树一张表看懂核心区别表格对比维度B 树B 树数据存储位置所有节点都存关键字 数据仅叶子节点存数据非叶子只存索引叶子节点结构独立节点无链表双向链表连接有序连续范围查询效率低需要遍历整棵树极高直接遍历链表单个节点关键字数较少树相对较高极多树更矮查询稳定性有的快有的慢可能在根节点所有查询路径长度一致数据库适用性一般适合小数据量索引极佳MySQL InnoDB 标准索引五、为什么 MySQL 选择 B 树做索引结合数据库的实际使用场景B 树的优势完全碾压 B 树磁盘 I/O 次数最少非叶子节点只存索引一个磁盘页能存更多关键字树高极低百万级数据也只有 3~4 层I/O 极少。范围查询极快数据库最常用where id 10 and id 100这类范围查询B 树叶子节点链表直接遍历无需多次磁盘 I/O。排序与分页友好order by、limit等操作直接依赖叶子节点的有序链表性能极高。查询效率稳定无论查询什么数据都要走到叶子节点不会出现极端慢查询。适合批量加载磁盘预读特性可以一次性加载相邻叶子节点充分利用磁盘顺序读写优势。六、简单总结B 树是多路平衡查找树解决了二叉树过高、磁盘 I/O 过多的问题B 树是 B 树的优化版非叶子节点只存索引数据全在叶子节点且链表化B 树适合随机查找B 树适合范围查询、数据库索引场景MySQL InnoDB 选用 B 树核心是为了减少磁盘 I/O、优化范围查询、提升整体稳定性。