B + 树是 B - 树的改进版本,作为一种多路平衡搜索树,它在 B - 树的基础上强化了对范围查询的支持和存储效率,成为数据库索引(如 MySQL InnoDB、PostgreSQL)和文件系统的核心数据结构。其设计充分适配磁盘 IO 特性,通过有序的叶子节点链表和集中存储的数据,实现高效的单点查询和范围查询。
B + 树的核心特点
m 阶 B + 树(m 为阶数,即节点最多的子节点数)具有以下关键特性:
节点结构:
每个非叶节点(索引节点)最多有m个子节点,存储m个关键字(用于索引子节点范围)。
非根节点的关键字数量k满足:⌈m/2⌉ ≤ k ≤ m(⌈m/2⌉为向上取整,保证节点不过于稀疏)。