B 树与 B+ 树从零理解：阶、节点结构与查找/插入/删除

目标你能从“为什么要多路平衡树”讲起把 B 树/B 树的节点长什么样、为什么高度低、以及插入删除的分裂/合并讲清楚。1. 为什么需要 B 树磁盘/页是成本中心如果数据不在 CPU 缓存里真正贵的往往不是比较次数而是随机 IO 次数。二叉搜索树哪怕是红黑树在内存里很好但它的分支因子低高度相对更高落到磁盘就会带来更多“读节点页”的次数。B 树的核心思想一个节点里放很多 key多路把树高压到很低每次下探读取一个节点等价于读取一个页page于是一次查询变成很少的层数很少的随机 IO每层在节点内部做二分/顺序扫描CPU 成本相对便宜2. “阶m”到底是什么意思不同书/实现的定义略有差异但你需要掌握共同点B 树是一个m 路搜索树一个节点最多有m个孩子对应地一个节点最多容纳m-1个 key作为分隔并且为了保持平衡有“最小填充”约束除根之外内部节点至少有大约ceil(m/2)个孩子至少有大约ceil(m/2)-1个 key直觉节点不能太空否则高度会变高。3. B 树节点结构逻辑视角一个 B 树节点可以想象成有序的 key 数组k1 k2 ... kt指向孩子的指针数组p0, p1, ..., ptkey 把数轴切成区间p0指向 k1p1指向[k1, k2)…pt指向 kt注意在B 树中key 和记录或记录指针可以同时存在于内部节点。这点与 B 树是关键区别之一。4. B 树节点结构内部节点只做“路标”B 树的结构特点内部节点只存 key索引键不存完整记录所有记录都在叶子节点叶子节点之间通常有链表指针便于范围查询/顺序扫描你可以把内部节点理解成高速路指示牌只负责告诉你往哪走真正的数据都在“终点叶子”5. 查找两者的共性与差异5.1 共性逐层定位孩子指针每层在节点的 key 数组里找到落点区间选择对应孩子继续。时间复杂度按比较次数O(log_m N)m 越大树越矮。5.2 差异命中位置B 树可能在内部节点就命中内部节点可能携带记录B 树一定走到叶子命中记录只在叶子这会带来B 树查询路径更一致更容易做缓存/预取B 树范围查询更自然叶子链表顺扫6. 插入为什么会“分裂”插入流程高层概念先按查找流程定位到目标叶子插入 key保持节点内有序如果节点 key 数量超过上限触发分裂split分裂直觉一个页大小固定比如 16KB节点装不下了就必须拆成两个节点6.1 分裂时发生什么概念版选一个“中间 key”作为分隔左半部分留在原节点右半部分放到新节点把“分隔 key”向上插入到父节点如果父节点也满了会继续向上分裂可能一直到根。6.2 根分裂树高 1当根也满了新建一个根根指向两个分裂后的节点这时树高增加 1但这种情况很少发生因为 m 很大。7. 删除为什么会“借/合并”删除流程高层概念定位并删除 key如果节点 key 数量低于下限需要再平衡再平衡常见两招向兄弟借一个 keyredistribute/rotate兄弟够富挪一点过来与兄弟合并merge兄弟也不富那就合并并从父节点拉下分隔 key删除比插入难讲清但面试时把“低于下限 - 借/合并 - 可能向上递归”这条主线说清即可。8. B 树 vs B 树最重要的 4 个对比点数据存储位置B 树内部节点也可能存数据B 树数据只在叶子范围查询B 树要中序遍历跨节点跳转B 树叶子链表顺扫IO 友好树高与扇出B 树内部节点不存数据能塞更多 key扇出更大树更矮查询路径一致性B 树可能提前命中B 树必到叶子路径更稳定9. 常见坑与澄清“B 树一定比 B 树快吗”不绝对。单点查询 B 树可能更少一层命中但数据库综合需求范围、排序、IO让 B 树更合适。“B 树叶子存的是数据还是指针”取决于实现聚簇索引叶子存整行数据二级索引叶子存主键再回表10. 面试背诵稿45 秒B 树/B 树都是多路平衡搜索树核心目的是在磁盘场景降低树高从而减少随机 IO 次数。B 树节点里 key 有序并把区间分给多个孩子插入时如果节点满会分裂并把中间 key 上推删除时如果低于下限会向兄弟借或合并并可能向上递归。B 树的关键区别是内部节点只存 key 做路标数据全部在叶子且叶子间有链表因此扇出更大、树更矮范围查询和顺序扫描更友好所以数据库索引通常采用 B 树。