B树与B+树结构原理

可视化演示

展示B树多路平衡搜索树结构、B+树叶子链表范围查询优化、节点分裂操作与磁盘I/O效率的交互式动画。

多路平衡结构

想象图书馆的“图书总目录”不是一本薄薄的册子，而是一棵倒着长的“目录树”。它的特殊之处在于：每个“橱窗”（节点）不只放一个书名标签，而是能放一长排标签。这就是B树与普通二叉树最本质的区别——每个节点不再是“一夫一妻”只能生两个孩子，而是能同时“抚养”多个子树，像一个拥有多个抽屉的档案柜。

从专业角度说，B树是一棵多路平衡搜索树。所谓“多路”，是指每个节点最多可以拥有m个子树（m称为阶数）；“平衡”是指所有叶子节点都在同一层，这保证了从根到任意叶子的路径长度相同。为什么要这样设计？让我们回到图书馆的场景：如果目录册太厚，每次查询都要翻很多页；如果太薄，又需要太多册子。B树巧妙地让每个节点装下尽可能多的条目，从而压缩整棵树的高度。

一棵含有N个键的m阶B树，高度h满足：最坏情况下（每个节点只有最少的键数）高度约为$\displaystyle \log_{\lceil m/2 \rceil}\frac{N+1}{2}$。当m=1000时，即便是10亿条数据，树高也只需要4层左右。这意味着查找任何一个数据，最多只需读4个磁盘页。

回到图书馆的比喻：B树就像一位聪明的图书管理员，他不把整座图书馆的书名都列在一本册子里，而是分层管理——每层有多个“分目录册”，每册记录了下一层分册的位置。查找时，你只需要沿着正确的分册一路往下，而不是从头翻到尾。

节点阶数选择

让我们继续探讨“图书目录册”的设计细节。假设你是管理员，要决定每本分目录册能容纳多少条目。如果每册只能记2条，那册子会很多，查找时要换很多册；如果每册能记100条，册子变少，但每册变厚，翻页（读写）成本上升。这个“每册容量”就是B树的阶数（m）。

阶数m定义了一个节点中最多能有多少个孩子指针，因此最多有m-1个键值。更精确地说，一棵m阶B树满足以下约束：每个节点最多有m个孩子、m-1个键；除根节点外，每个节点至少有⌈m/2⌉个孩子、⌈m/2⌉-1个键；根节点至少有2个孩子（除非它是叶子）。这些数字不是随意定的，而是为了保证树不会退化成链表。

以m=5为例，一个内部节点最多持有4个键（记为k1<k2<k3<k4），这些键把数据范围分成5个区间，分别对应5个孩子指针。查找时，先与4个键比较，确定走哪个区间。这一设计让二叉树的“一次比较一分为二”升级为“一次比较多路分支”，效率倍增。

回到图书馆的比喻：阶数就是“分目录册”的页数。图书管理员会根据书架大小（页大小）和每本书标签的宽度（键大小），计算出每册目录恰好多大最划算。太大浪费纸张，太小增加翻册次数。

高效查找路径

现在，想象你拿着总目录在图书馆找一本《算法导论》。你不会从第一层书架开始逐一扫描，而是先看总目录册——哦，它在“计算机科学”区；再翻开该区的分目录册——哦，它在“算法”分区的第3排；最后到第3排直接抽出那本书。B树的查找算法就是这样一个层层缩小的过程。

从根节点开始，在当前节点的键值序列中顺序查找（或二分查找），找到目标键则返回；否则根据大小关系确定目标可能所在的子树区间，进入孩子节点继续同样的操作，直到叶子节点。由于B树的高度通常只有3-5层，这意味着单次查找最多需要3-5次磁盘I/O，每次I/O读取一个完整的节点（一个磁盘页）。

查找过程中，每深入一层，数据范围就缩小为当前的1/m左右。假设有N条数据，每层最多“分流”m路，层数为$\displaystyle \log_m N$。B树查找的时间复杂度为O(log_m N)，而磁盘I/O次数与树高成正比。这也是B树优于二叉搜索树的核心：同样的数据量，B树更“矮胖”，I/O次数更少。

回到图书馆的比喻：高效的查找路径就像经验丰富的管理员，他从不逐个书架地找，而是通过“总目录→分区目录→书架”层层定位。B树将这种分层检索固化在数据结构中，让每次查找都有明确的路径指引。

范围查询优化

假设读者想借“计算机”相关的全部书籍，从《计算机组成原理》到《计算机网络》。如果使用普通B树，你需要找到第一本书后，又得回到树的更高层重新定位下一本，就像在图书馆里从书架A跑到检索台再跑回书架B，来回折腾。而B+树完美解决了这个问题。

B+树对B树做了关键改造：所有键值数据只存储在叶子节点，内部节点只存“路标”（键的副本）。更重要的是，所有叶子节点通过双向链表串联在一起。当你要查询某个范围内的所有数据时，先快速定位到范围起点所在的叶子节点，然后沿着链表的next指针一路向后扫，直到超出范围，整个过程无需再访问内部节点。

这一设计的精妙之处在于，范围查询的时间复杂度从B树的每查一条数据都要走一遍树（O(k log_m N)），降低为“一次定位+顺序遍历”（O(log_m N + k)）。其中k是返回的记录条数。这对数据库的"SELECT WHERE id BETWEEN……"类查询是革命性的优化。

回到图书馆的比喻：B+树给所有书架底层装了一条“传送带”，管理员找到第一本“计算机”主题的书后，只需站在传送带前一路接书，不用再跑回检索台。这就是为什么现代数据库几乎都采用B+树做索引。

分裂与合并

图书馆每天都有新书上架。当某本分目录册写满了条目（节点键数达到m-1），再要插入新条目怎么办？图书管理员的办法是：把这本册子从中间撕开，分成两本薄册子，中间的条目升级到上一层目录（父节点）。这就是B树的节点分裂。

分裂操作发生在插入路径上。当一个节点键数达到m-1，再插入第m个键时，取中间的键提升到父节点，左右两部分分别形成两个新节点。如果父节点也因此饱和，继续向上分裂，最坏情况一直分裂到根节点，树的高度随之增加1。分裂的方向是自底向上的。

删除操作则是分裂的逆过程——合并。当节点键数低于下限⌈m/2⌉-1时，先尝试从相邻兄弟节点“借”一个键（通过父节点中转）；如果兄弟也处于“半饥饿”状态，则将两个节点合并成一个，父节点相应减少一个键。如果父节点因此低于下限，合并继续向上传导。这一过程保证了B树在频繁增删后依然保持平衡。

回到图书馆的比喻：分裂就像书太多时把单册目录拆成两册，合并就像书被借走太多后把两册目录合成一册。这些操作确保了每本册子都保持“半满以上”的利用率，既不多占空间，也不浪费纸张。

磁盘I/O优化

为什么B树和B+树的“大节点”设计如此重要？让我们从物理存储的视角看。磁盘读写的最小单位是页（通常4KB或16KB），每次I/O都要经历“寻道+旋转+传输”的过程，其中寻道延迟高达数毫秒。相比之下，内存访问只需纳秒级——两者相差5个数量级。

B树的天才之处在于：让每个节点的大小恰好等于一个磁盘页。这样每次I/O读取一页，恰好得到一个完整的节点，物尽其用。而如果像二叉搜索树那样一个节点只存一个键，每次I/O只读到一个键，浪费了整页的空间。用图书馆的比喻说：你雇了一辆卡车去取一本书，但每次只取一本就回来——这是巨大的浪费。B树让每辆卡车都装得满满当当。

另一个关键概念是局部性原理：B树查找时，访问的节点在磁盘上往往相邻存放，尤其是叶子节点在B+树中是物理连续的。这使数据库可以预读相邻页，进一步减少I/O次数。MySQL InnoDB的页大小默认为16KB，索引节点充分填充，就是为了最大化单次I/O的信息量。

回到图书馆的比喻：图书管理员深知——从仓库调书（磁盘I/O）最耗时，所以他会精心设计每本册子恰好装满一辆推车，不多不少。页大小与节点大小的匹配，正是这种“一辆推车一车书”的智慧。

数据库索引应用

理解了B+树的原理后，让我们看看它在真实世界中的模样。MySQL的InnoDB存储引擎是B+树最著名的用户。InnoDB中的聚簇索引就是B+树：表数据本身以B+树的形式组织在磁盘上，叶子节点存储完整的行数据，主键作为键值。这意味着"SELECT * FROM user WHERE id=5"只需沿B+树走3-4层就能定位到完整的行。

InnoDB的二级索引（非聚簇索引）也是B+树，但叶子节点存储的是主键值而非完整行。当通过二级索引查找时，先找到主键，再回表查聚簇索引——这是“两棵树”的配合。MongoDB则使用B树的变种（WiredTiger存储引擎），因为MongoDB的文档模型更多是点查，且不需要大范围的范围查询。

为什么数据库如此青睐B+树？核心在于 I/O效率：B+树的内部节点不存数据，因此同样的页能存更多键，树更矮，I/O更少；叶子节点的链表让范围查询如鱼得水；加上聚簇索引让频繁查询的主键数据物理有序存放，更是锦上添花。

回到图书馆的比喻：聚簇索引就像把每本书直接按编号顺序放在书架上，找到编号就找到书；二级索引则像书名索引卡，先查到编号，再去书架取书。明白这层关系，你就能理解为什么“SELECT *“用辅助索引可能比主键索引慢——多了一次”从索引卡到书架”的往返。

AI 应用场景

Python 演示

class BPlusTreeNode:    """B+树节点: keys存储键, children存储子节点(仅内部节点),     next_node指向下一个叶子节点(仅叶子节点)"""    def __init__(self, is_leaf=False):        self.is_leaf = is_leaf        self.keys = []        self.children = []        self.next_node = None  # 叶子节点的链表指针  class BPlusTree:    def __init__(self, order=4):        self.root = BPlusTreeNode(is_leaf=True)        self.order = order  # 阶数, 类比图书馆分目录册的容量     def find_leaf(self, key):        """从根到叶子查找路径, 返回目标所在的叶子节点"""        node = self.root        while not node.is_leaf:            idx = 0            while idx < len(node.keys) and key >= node.keys[idx]:                idx += 1            node = node.children[idx]        return node     def insert(self, key):        """插入键到B+树"""        leaf = self.find_leaf(key)        pos = 0        while pos < len(leaf.keys) and leaf.keys[pos] < key:            pos += 1        leaf.keys.insert(pos, key)        if len(leaf.keys) <= self.order - 1:            return        # 分裂叶子节点        mid = len(leaf.keys) // 2        new_leaf = BPlusTreeNode(is_leaf=True)        new_leaf.keys = leaf.keys[mid:]        leaf.keys = leaf.keys[:mid]        new_leaf.next_node = leaf.next_node        leaf.next_node = new_leaf        # 将分裂后的中间键提升到父节点        self._insert_into_parent(leaf, new_leaf.keys[0], new_leaf)     def _insert_into_parent(self, left, key, right):        """将中间键提升到父节点"""        if left is self.root:            new_root = BPlusTreeNode()            new_root.keys = [key]            new_root.children = [left, right]            self.root = new_root            return        parent = self._find_parent(self.root, left)        idx = 0        while idx < len(parent.keys) and parent.keys[idx] < key:            idx += 1        parent.keys.insert(idx, key)        parent.children.insert(idx + 1, right)        if len(parent.keys) <= self.order - 1:            return        # 分裂内部节点        mid = len(parent.keys) // 2        mid_key = parent.keys[mid]        new_internal = BPlusTreeNode()        new_internal.keys = parent.keys[mid + 1:]        new_internal.children = parent.children[mid + 1:]        parent.keys = parent.keys[:mid]        parent.children = parent.children[:mid + 1]        self._insert_into_parent(parent, mid_key, new_internal)     def range_query(self, start, end):        """范围查询: 先定位起点, 再沿链表顺序扫描"""        leaf = self.find_leaf(start)        result = []        while leaf:            for k in leaf.keys:                if start <= k <= end:                    result.append(k)                elif k > end:                    return result            leaf = leaf.next_node        return result     def _find_parent(self, node, child):        """找到child节点的父节点"""        if node.is_leaf:            return None        for i, c in enumerate(node.children):            if c is child:                return node            if not c.is_leaf:                result = self._find_parent(c, child)                if result:                    return result        return None  # 演示代码if __name__ == "__main__":    tree = BPlusTree(order=4)    keys = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 25, 35, 45, 55]    for k in keys:        tree.insert(k)    print("插入完成, 范围查询 [25, 60] 的结果:")    print(tree.range_query(25, 60))    print("预期输出: [25, 30, 35, 40, 45, 50, 55, 60]")

1. class BPlusTreeNode:定义节点结构。keys存键，children存子节点指针，next_node是叶子节点的链表指针，对应B+树“叶子串联”的核心特征。
2. def find_leaf(self, key):查找路径的核心方法。从根节点逐层向下，根据键值大小选择正确分支，直到叶子节点。这就是“图书管理员层层翻目录”的过程。
3. while not node.is_leaf:只要当前节点不是叶子，就继续向下层走。内部节点起“路标”作用，不含实际数据。
4. idx += 1在节点内顺序比较键值，找到正确的子节点指针位置。这就是为什么B+树每个内部节点的孩子数比键数多1。
5. if len(leaf.keys) <= self.order - 1: return插入后检查是否超容。键数不超过m-1则无事发生，否则需要分裂。
6. mid = len(leaf.keys) // 2分裂时找到中间位置，将键一分为二。这是“分目录册从中间撕开”的代码体现。
7. new_leaf.next_node = leaf.next_node; leaf.next_node = new_leaf维护链表的连接关系。分裂后新旧叶子要正确链接，否则范围查询会断链。
8. def range_query(self, start, end):范围查询的核心。先定位到起点，然后沿next_node依次遍历，直到超过范围上界。
9. while leaf:沿链表遍历的循环。每个叶子节点检查完所有键，再跳到下一个叶子。这就是B+树范围查询不需要回溯的原因。

常见误区

面试题