想象你要在一家藏书千万册的巨型图书馆里找书。这家图书馆的设计很特别：大厅只挂一块总目录牌，上面只写“1~100 号在哪区、101~200 号在哪区”这样的大方向，目录牌本身不摆书；你顺着指引来到楼层，还有更细的指示牌；最后才走到真正放书的书架前。更妙的是，所有书架之间被一条走廊首尾相连——你找到第一本书后，不必回大厅，沿着走廊就能把同一区间的书依次取完。图书馆还有一群管理员，专门处理两件事：书架满了就从中间拆成两个，太空了就和旁边的合并，始终保持每本书到大厅的距离差不多。这套图书馆设计图纸，就是支撑现代数据库和分布式存储引擎的核心索引结构——B+Tree。读懂它，你就读懂了数据世界里“如何快速找到东西”的全部秘密。

岗位关联

对 AI 从业者而言，B+Tree 是理解数据库内核、大规模数据检索与分布式 KV 存储的必修课，也是从“调 API”走向“懂引擎”的分水岭。

目录
  1. 可视化演示
  2. 树形结构设计
  3. 查找算法
  4. 范围查询优化
  5. 插入与页分裂
  6. 删除与页合并
  7. 并发控制机制
  8. 存储引擎应用
  9. AI 应用场景
  10. Python 演示
  11. 常见误区
  12. 面试题

可视化演示

展示B+Tree层级结构、键值插入页分裂传播、叶链表范围查询顺序扫描三阶段交互探索。

本节配有交互动效（进入视口后自动加载，约 3KB）。

B+Tree结构：多路搜索树 根与内部节点存储路由键 叶节点存储数据与键值 叶链表连接支持顺序扫描 height = log_fanout(N) 大扇出低树高减少磁盘IO

树形结构设计

图书馆的秘诀在于“分工明确”：大厅总目录牌、楼层指示牌只负责指路，上面是编号区间，一本真书都不摆；真正的书籍只存放在最底层的书架上。这样做的好处是，一块标识牌可以指引很多个区域，整个建筑不必建得高耸入云。

在 B+Tree 里，这个“目录牌”就是内部节点（internal node），只存储键（key）用来路由；“书架”就是叶子节点（leaf node），存储键和对应的数据指针或记录本身。所有叶子节点严格位于同一层，保证从根到任意叶子的距离相等——这正是“平衡”的含义。一个节点能容纳的子节点数量称为扇出（fan-out），记作 m。

实战中一个页可以放下几百个键，因此 B+Tree 非常“矮胖”：即便存储千万条记录，树高也只有 3~4 层。而二叉树每层只能分两叉，同样数据要 20 多层。磁盘按“页”读取，每下探一层就是一次磁盘 IO，树高直接决定了查询的磁盘开销。

回到图书馆：无论藏书涨到多少，只要有足够宽的目录牌，读者走到书架的步数几乎不变。这就是 B+Tree 的第一印象——把“分叉多”与“层级少”融为一体。

h=⌈log⁡mN⌉\displaystyle h = \lceil \log_m N \rceil
树高约等于“以扇出 m 为底、记录总数 N 的对数”。只要扇出足够大，海量数据也只需极少的层级。
  1. N 表示记录总数叶子节点存放的全部数据量，对应图书馆的藏书总量。
    N\displaystyle N
  2. m 表示扇出每个内部节点最多拥有的子节点数，也就是一块指示牌最多能指出的方向数。
    m\displaystyle m
  3. log_m N 取对数每下探一层，候选范围缩小到原来的 m 分之一。
    log⁡mN=ln⁡Nln⁡m\displaystyle \log_m N = \frac{\ln N}{\ln m}
  4. ⌈ ⌉ 向上取整树高必须是整数，即使只超出一点也要多占一层书架。
    h=⌈log⁡mN⌉\displaystyle h = \left\lceil \log_m N \right\rceil

查找算法

读者找书有个诀窍：每块指示牌上都写着编号区间，他先比较目标编号落在哪一档，然后头也不回地走向对应方向。因为各方向的区间互不重叠，他只需要反复做“比大小”这一件事，绝不回头。

B+Tree 的查找正是如此。从根节点出发，在内部节点内用二分查找找到第一个不小于目标键的位置，沿对应子指针下探；重复直到叶子节点；最后在叶子的键数组中定位记录。整条路径由比较结果唯一确定，没有任何分支错误需要纠正。

复杂度上，层数是 O(log_m N)，每层节点内二分是 O(log m)，合起来是 O(log N)。但真正落盘的 IO 次数只有“层数”那么几次，因为根节点与高层节点通常被缓存——这才是工程上真正的胜负手。

图书馆的读者从不走回头路，路径在一次次的比大小中被唯一确定；B+Tree 的查询也一样——它牺牲了插入的随意性，换来了近乎确定的、极短的寻书路径。

Tlookup=O(log⁡mN)=O ⁣(ln⁡Nln⁡m)\displaystyle T_{\text{lookup}} = O(\log_m N) = O\!\left(\frac{\ln N}{\ln m}\right)
查找代价由树高决定。m 越大路径越短，但节点变大也会让单次比较略贵，所以 m 的选取本质是“页大小 ÷ 键大小”的工程权衡。
  1. O(log_m N) 路径长度从根到叶访问的节点页数，决定磁盘 IO 次数。
    O(log⁡mN)\displaystyle O(\log_m N)
  2. 节点内二分 O(log m)在单个节点的有序键里二分，找到下一步方向。
    O(log⁡m)\displaystyle O(\log m)
  3. 换底公式lnN/lnm 把扇出 m 的影响显式写出来，m 越大值越小。
    ln⁡Nln⁡m\displaystyle \frac{\ln N}{\ln m}
  4. 磁盘视角 IO≈h高层节点常驻内存，实际落盘次数约等于树高。
    IO≈⌈log⁡mN⌉\displaystyle \text{IO} \approx \lceil \log_m N \rceil

范围查询优化

图书馆最受欢迎的功能不是随便找一本，而是“把 60~100 号的书都借出来”。没有走廊的图书馆只能查完一本、回大厅、再走一遍；有走廊的图书馆，读者从第一本开始沿走廊一路向右，因为书架上的书本来就是按序排列的。

B+Tree 的叶子节点之间用指针构成一个有序链表。查询区间 [lo, hi] 时，先按查找算法定位第一个不小于 lo 的叶子，然后顺着 next 指针顺序扫描，不必回到父节点重新递归。这让区间统计、分页查询、排序输出变得极其自然。

这正是 B+Tree 相比 B-树（所有节点都存数据）的经典改进：B-树做范围查询要在节点间反复跳转，而叶子链表让顺序访问的成本从“随高度波动”降为“随结果量线性增长”。

走廊的宽度就是叶子链表的密度。正因为把“区间”变成了一条连续动线，数据库的 ORDER BY、范围过滤、批量拉取才能像逛书架一样轻松。

Trange=O(log⁡mN+k)\displaystyle T_{\text{range}} = O(\log_m N + k)
找起点花 log_m N，数结果只花 k。k 可以是很大的结果集，但它是“必须要读的页数”，没有任何多余开销。
  1. log_m N 定位起点先用查找算法找到第一个满足条件的叶子节点。
    O(log⁡mN)\displaystyle O(\log_m N)
  2. k 个结果沿叶子链表按序读出 k 条记录，每条成本 O(1)。
    O(k)\displaystyle O(k)
  3. 加法而非乘法定位与扫描是两段独立开销，互不放大地叠加。
    Trange=O(log⁡mN+k)\displaystyle T_{\text{range}} = O(\log_m N + k)
  4. 无回溯叶子链表保证扫描方向单调，不需要跳回上层节点。
    next leaf=leaf.next\displaystyle \text{next leaf} = \text{leaf.next}

插入与页分裂

图书馆不断进新书。管理员把书送到对应书架，按编号插进正确位置。但书架容量有限，满了怎么办？他的做法是：从中间均分，把新书架放在老书架右侧并接入走廊，然后把中间那本书的编号抄到楼层指示牌上——从此这个区域多了一个方向。

在 B+Tree 中，插入从叶子开始：定位目标叶子页，把键值对按序插入。若页内键数超过容量上限 m-1，就触发页分裂：将约一半键分到新页，中间键“上提”到父节点作为新的路由键。若父节点也因此溢出，分裂继续向上传播。

只有根节点分裂时，树高才增加 1——这是唯一增高途径。分裂时也会把兄弟叶子通过链表接在一起。实践中分裂点取 ⌈m/2⌉，保证两页都不低于“半满”，为以后的删除和插入留出缓冲。

图书馆管理员从不拒绝新书，只会不断“扩层”：把满的书架一拆为二，在指示牌上多写一行。B+Tree 的插入也永远成功，代价只是偶尔分裂——这正是它适合高频写入的原因。

nkeys≤m−1,split at ⌈m2⌉\displaystyle n_{\text{keys}} \le m - 1, \qquad \text{split at } \left\lceil \frac{m}{2} \right\rceil
页的容量上限是 m-1 个键；满了就从中间一分为二，把中间的键上交给父节点当“分界路标”。
  1. 容量上限 m-1m 个子指针之间恰好夹着 m-1 个键，构成有序空间。
    nkeys≤m−1\displaystyle n_{\text{keys}} \le m - 1
  2. 分裂点 ⌈m/2⌉从中间偏上的位置切开，两侧尽量保持半满。
    ⌈m2⌉\displaystyle \left\lceil \frac{m}{2} \right\rceil
  3. 中间键上提分裂点对应的键被送到父节点，作为新的路由分隔。
    parent.keys←kmid\displaystyle \text{parent.keys} \gets k_{\text{mid}}
  4. 向上传播父节点若溢出，递归执行同一套分裂逻辑直至根。
    split(parent)⇒split(grandparent)⋯\displaystyle \text{split(parent)} \Rightarrow \text{split(grandparent)} \cdots

删除与页合并

旧书下架也有讲究。书架太空时，管理员先去瞧邻居：邻居书多就“借”一本过来，两边都过得去；邻居也稀稀拉拉，那就把两个书架合并，收掉一段走廊，并在楼层指示牌上删掉一个方向。

删除时先定位叶子并移除键值对，然后检查是否下溢（underflow）：键数低于下限 ⌊m/2⌋-1。下溢时优先向兄弟节点借键（rotation），父节点的路由键随之调整；兄弟也不够则合并两页，并删除父节点中对应的键——若父节点因此下溢，合并继续向上传播，根节点最终可能收缩，树高减 1。

借键与合并的共同目标，是维护“每页至少半满”的空间约束，避免索引页碎片化；同时保证树的平衡性不被破坏，让所有查找路径依然等长。

图书馆的走廊不会永远空下去。合并与借键让书架始终紧凑，也保证了查询时不必为了找一本书而扫过整排空架子。空间利用率与查询性能在这里达成了平衡。

nkeys≥⌊m2⌋−1\displaystyle n_{\text{keys}} \ge \left\lfloor \frac{m}{2} \right\rfloor - 1
这是节点健康的“最低体温”：低于它，要么向左邻右舍借键，要么合并。下界和上界 m-1 共同保证每页空间利用率不低于约 50%。
  1. 下界 ⌊m/2⌋-1非根节点最少键数的约定，低于它即视为下溢。
    ⌊m2⌋−1\displaystyle \left\lfloor \frac{m}{2} \right\rfloor - 1
  2. 借键从兄弟节点匀一个键过来，同时更新父节点路由键。
    borrow from sibling, update parent key\displaystyle \text{borrow from sibling, update parent key}
  3. 合并触发条件兄弟页也低于下界时，两页合并为一页。
    merge(L,R)⇒one page\displaystyle \text{merge}(L, R) \Rightarrow \text{one page}
  4. 删除父键并传播合并后父节点少一个孩子，可能继续下溢。
    delete key in parent, propagate up\displaystyle \text{delete key in parent, propagate up}

并发控制机制

图书馆人多就会冲突：你在 A 区查书时，管理员不能把 A 区整体封死。合理规则是——读者从大厅往下走，每到一层先“登记”（拿一张小票），确认下一层安全后才放手上一层的登记。这样同一时刻整条路上只有两层被占用，其它区域照常营业。

这就是锁耦合（lock coupling）。数据库引擎用 latch（闩锁）保护物理页的结构完整性，例如插入删除时防止两个线程同时改一个页；用 lock（锁）管理事务级的逻辑隔离。B+Tree 的经典做法是：从根到叶逐层加 latch，拿到子节点 latch 后立即释放父节点 latch，路径上同时持有的 latch 数最多 2。

其它策略包括：乐观并发控制（不加锁，提交时验证路径是否变化，冲突则重试）；写时复制（COW）——修改时复制路径上的页，新版本原子替换，旧版本读取不被阻塞，这是 Btrfs、LMDB 等系统的 MVCC 思路。方向不同，目的相同：在不牺牲并发度的前提下维持树的结构不变式。

图书馆的秩序来自“短暂登记、及时放手”。B+Tree 的并发控制遵循同样的哲学——锁不是越久越好，而是“够用就放”，让整棵树的吞吐量不被单一读者拖垮。

Lheld≤2\displaystyle L_{\text{held}} \le 2
锁耦合的精髓是“手里最多两把钥匙”：一把是当前楼层，一把是下一楼层。确认安全就放开上一把，让其它读者畅通无阻。
  1. 锁住父节点先持有当前节点锁，防止它发生分裂或合并。
    latch(parent)\displaystyle \text{latch(parent)}
  2. 锁住子节点下探前锁住子节点，形成“父子同持”的瞬间。
    latch(child)\displaystyle \text{latch(child)}
  3. 释放父锁确认子节点稳定后立即释放父节点锁。
    unlatch(parent)\displaystyle \text{unlatch(parent)}
  4. 同时最多两把路径上的持锁数不超过 2，并发度最大化。
    Lheld≤2\displaystyle L_{\text{held}} \le 2

存储引擎应用

这套图书馆设计已被推广到整个城市：传统图书馆用它管理书目卡片，跨城连锁馆用它登记“哪本书在哪个分馆”，而新兴的快递分拣仓（写多读少）则采用另一种流水线方案。B+Tree 不是万能的，但在“查得快、范围扫得顺”这件事上依然是最成熟的方案。

传统关系型数据库里，MySQL InnoDB 的聚簇索引就是 B+Tree：主键构成一棵树，叶子页存放整行记录；二级索引的叶子存主键值，需要时回表再查一次主键树。分布式存储引擎（TiKV、CockroachDB）也用 B+Tree 组织元数据与 Range 路由，或者直接以它作为 KV 的主结构。

与 LSM-Tree 相比：B+Tree 读放大低、范围查询稳定、空间利用率高；LSM 写放大低、顺序写友好，但读放大和空间放大明显。选型取决于 workload——读多写少、需要稳定延迟的在线业务倾向 B+Tree，写入密集的日志型业务倾向 LSM。

无论是单机数据库还是分布式存储，B+Tree 的图纸始终如一。理解它的取舍，你就掌握了“数据组织方式决定系统性能上限”这一核心洞察——这也是每一位存储引擎工程师的必修内功。

IO=⌈log⁡mN⌉≈3–4\displaystyle \text{IO} = \lceil \log_m N \rceil \approx 3\text{--}4
当 m 取几百、N 取千万级时，树高只有 3~4。一次点查询只需三四个磁盘页访问——这就是“数据库为什么这么快”的直接答案。
  1. N 千万级单表记录数，对应千万册藏书的规模。
    N≈107\displaystyle N \approx 10^7
  2. m 取几百一个 16KB 页可容纳数百个 8~16 字节的键。
    m≈200–500\displaystyle m \approx 200\text{--}500
  3. 树高 3~4代入公式后得到 3~4 层，点查询只需 3~4 次页访问。
    h=⌈log⁡300107⌉≈3\displaystyle h = \lceil \log_{300} 10^7 \rceil \approx 3
  4. 根页常驻内存根节点被缓存后，实际磁盘 IO 再减一次。
    disk IO≈h−1≤3\displaystyle \text{disk IO} \approx h - 1 \le 3

AI 应用场景

AI 训练样本的批量取数加速

阶段：数据准备与特征工程（存储与检索）

解决的问题：训练样本库动辄上亿行，按时间窗或 ID 区间批量拉取样本时，全表扫描耗时以分钟计，AI 工程师的取数速度直接拖慢实验迭代。B+Tree 的叶子链表让“区间取数”退化为顺序扫描，毫秒级响应。

具体案例：某推荐系统团队对 30 天用户行为数据做模型微调。在 user_behavior(user_id, ts, feature) 表上为 ts 建 B+Tree 二级索引后，暴力扫描 15 秒的查询降到 120ms，特征流水线迭代速度提升百倍。

分布式 KV 的 Range 路由与元数据管理

阶段：在线推理与模型服务的数据访问层

解决的问题：大模型与向量检索服务的特征库要求低延迟 KV 访问，同时要把数据分片到多台机器。B+Tree 常被用来维护“key 区间 → 数据分片”的映射，一次路由跳转只有 O(log_m N) 次。

具体案例：TiKV 用 B+Tree 组织 Region 元数据，定位某个 key 属于哪个 Region 只需常量级路径；向量数据库的标量预过滤（如“只查 status=active 的向量”）也依赖 B+Tree 先缩小候选集，再交给 ANN 索引。

训练日志与轨迹数据的时间序回溯

阶段：可观测性与训练复盘

解决的问题：大模型训练跨天甚至跨周，出问题时需要精确回溯“某一时间区间内 GPU 利用率、loss 曲线”。日志平台按时间戳建 B+Tree 索引，让区间查询稳定高效，避免全量扫描。

具体案例：某 LLM 训练平台将指标日志按 (training_id, ts) 建主键索引，复盘一次 7 天训练的指定时段指标，从 3 分钟降至 2 秒；运维人员能快速定位 OOM 的确切时间点。

Python 演示

python109 行
class Leaf:    def __init__(self, order):        self.order = order        self.keys = []        self.values = []        self.next = None        self.parent = None  class Internal:    def __init__(self, order):        self.order = order        self.keys = []        self.children = []        self.parent = None  class BPlusTree:    def __init__(self, order):        self.order = order        self.root = Leaf(order)     def insert(self, key, value):        leaf = self._find_leaf(key)        leaf.keys.append(key)        leaf.values.append(value)        i = len(leaf.keys) - 1        while i > 0 and leaf.keys[i] < leaf.keys[i - 1]:            leaf.keys[i], leaf.keys[i - 1] = leaf.keys[i - 1], leaf.keys[i]            leaf.values[i], leaf.values[i - 1] = leaf.values[i - 1], leaf.values[i]            i -= 1        if len(leaf.keys) > self.order - 1:            self._split_leaf(leaf)     def _find_leaf(self, key):        node = self.root        while not isinstance(node, Leaf):            i = 0            while i < len(node.keys) and key >= node.keys[i]:                i += 1            node = node.children[i]        return node     def _split_leaf(self, leaf):        mid = len(leaf.keys) // 2        new_leaf = Leaf(self.order)        new_leaf.keys = leaf.keys[mid:]        new_leaf.values = leaf.values[mid:]        leaf.keys = leaf.keys[:mid]        leaf.values = leaf.values[:mid]        new_leaf.next = leaf.next        leaf.next = new_leaf        self._insert_parent(leaf, new_leaf.keys[0], new_leaf)     def _insert_parent(self, left, key, right):        if left is self.root:            new_root = Internal(self.order)            new_root.keys = [key]            new_root.children = [left, right]            left.parent = new_root            right.parent = new_root            self.root = new_root            return        parent = left.parent        i = 0        while i < len(parent.keys) and parent.keys[i] < key:            i += 1        parent.keys.insert(i, key)        parent.children.insert(i + 1, right)        right.parent = parent        if len(parent.keys) > self.order - 1:            self._split_internal(parent)     def _split_internal(self, node):        mid = len(node.keys) // 2        up_key = node.keys[mid]        new_node = Internal(self.order)        new_node.keys = node.keys[mid + 1:]        new_node.children = node.children[mid + 1:]        node.keys = node.keys[:mid]        node.children = node.children[:mid + 1]        for child in new_node.children:            child.parent = new_node        self._insert_parent(node, up_key, new_node)     def range_query(self, lo, hi):        leaf = self._find_leaf(lo)        result = []        while leaf:            for i, k in enumerate(leaf.keys):                if k > hi:                    return result                if k >= lo:                    result.append((k, leaf.values[i]))            leaf = leaf.next        return result  if __name__ == "__main__":    tree = BPlusTree(order=4)    for n in range(1, 21):        tree.insert(n, "book-%d" % n)    print("range(3,18) =", tree.range_query(3, 18))    h = 1    node = tree.root    while not isinstance(node, Leaf):        h += 1        node = node.children[0]    print("height =", h, "root keys =", tree.root.keys)
目的：用约百行 Python 实现一个支持插入、页分裂与范围查询的 B+Tree 原型，并在主程序中插入 20 条记录、查询区间 [3,18] 并打印树高。
  1. if len(leaf.keys) > self.order - 1:键数超过 m-1 即触发页分裂，对应“书架满了就拆”。
  2. self._insert_parent(leaf, new_leaf.keys[0], new_leaf)把新叶子的首键上提给父节点当路由键。
  3. while i < len(node.keys) and key >= node.keys[i]:在内部节点里线性跳过所有不大于目标的键，决定下探方向。
  4. mid = len(node.keys) // 2分裂点取键数中点，保证两页半满。
  5. if left is self.root:根节点分裂时新建父节点，树高唯一增长点。
  6. while leaf:` 与 `leaf = leaf.next沿叶子链表顺序扫描，实现 O(log_m N + k) 的范围查询。
  7. leaf.values[i]键与值一一对应，找到了键就带出它背后的“书籍记录”。

常见误区

误区我以为是像 B-树那样，内部节点也可以放记录，每个节点都是一个“数据的家”。

正解B+Tree 内部节点只存路由键和子指针，真正的键值对全部在叶子节点。这正是它“矮胖”和“叶子链表”两大特性的前提。图书馆里目录牌只写方向和范围，从来不放真书；书都在书架上。

为何常见：B-树先入为主，很多教材把 B-Tree / B+Tree 混着讲，初学者容易把多路树的几个变体记成同一种。

误区不就是二叉树每个节点多存几个键吗？平衡树我都懂，换个名字而已。

正解多路与二叉的本质差别在“一层能排除多少候选”。二叉树一层排除 1/2，千万级数据要 20 多层；B+Tree 一层排除 1/m（m 常为数百），千万级只有 3~4 层。磁盘上少 20 次 IO 是数量级差距，不是“换名字”。

为何常见：课程先讲二叉查找树，惯性思维让人把一切树的复杂度都套成 log₂N，忽略了“页”和“扇出”在磁盘场景的分量。

误区页满了就分裂，分裂一次树高 +1？那插入 20 条记录树不得 20 层？

正解叶子分裂只会在同一层多出一个兄弟页，树高完全不变；只有当根节点也满了、需要为它造一个新父亲时，树才长高一层。这是整个分裂过程唯一增高的情况，所以插入再频繁，树高也几乎稳定。

为何常见：看到“分裂向上传播”的字样，容易把“传播”误当成“长高”，其实传播到根是罕见事件。

误区键数小于 ⌊m/2⌋-1 就要合并，不然树就“不平衡”了。

正解下溢后第一步是“借键”：从兄弟节点匀一个键过来，两边都恢复正常，父节点只改一下路由键，成本极低。强行合并会引入父节点键删除、可能向上连锁传播，是最后手段。图书馆书架太空时，管理员总是先找邻居匀书，两家都空才并架。

为何常见：教材先讲分裂（上溢）再讲合并（下溢），容易把合并当成下溢的必然结局，忽略了“借键”这个更常见的中间手段。

误区RocksDB、HBase 都用 LSM-Tree，B+Tree 是不是过时了？

正解两者服务不同 workload：LSM 把随机写变顺序写，写放大低，但读放大、空间放大高；B+Tree 读路径短、范围查询稳定、空间利用率高。在线交易、元数据路由、低延迟点查场景，B+Tree 依旧是绝对主流。

为何常见：只看到 LSM 在日志型写入场景的胜利，忽略了两类引擎在读写放大上的不同取舍——图书馆“查得快”的场景，档案馆方案依然最优。

面试题

Q1. 在 B+Tree 中，内部节点与叶子节点的核心区别是什么？

单选题 · easy

  • A.内部节点存储实际的数据记录
  • B.内部节点只存键做路由指示← 正确答案
  • C.叶子节点不保存任何数据信息
  • D.内部与叶子节点完全没有区别

答案：B。B+Tree 的核心分工是“内部节点只指路、叶子节点存数据”。A 把 B-树的特征安到了 B+Tree 上；C 完全说反，叶子不存数据 B+Tree 就失去意义；D 显然不成立。如同图书馆里目录牌与书架职责不同：目录牌上永远没有真书。

Q2. B+Tree 范围查询高效的最主要原因是什么？

单选题 · easy

  • A.叶子节点之间用链表指针相连← 正确答案
  • B.内部节点支持二分查找策略
  • C.根节点常驻内存缓存之中
  • D.每个数据会被重复存储多次

答案：A。范围查询快的核心是叶子链表：找到起点后顺着 next 指针顺序扫，不需要回溯父节点。二分查找、根缓存只能加速单点定位，不能把“反复回溯”变成“线性推进”。走廊能顺路走到底，靠的是书架之间的直接通道。

Q3. 一棵扇出 m=100 的 B+Tree 存储 100 万条记录，高度最接近多少？

单选题 · mid

  • A.约三层左右← 正确答案
  • B.约十层左右
  • C.约二十层左右
  • D.约一百层左右

答案：A。h=⌈log₁₀₀ 10⁶⌉=⌈3⌉=3。扇出越大树越矮，这就是“目录牌足够宽、楼层不必高”的直观例证。若换成二叉树需要约 20 层，两者的磁盘 IO 差距接近一个数量级。

Q4. 插入导致叶子页满时，B+Tree 的正确处理方式是？

单选题 · mid

  • A.立即报错并回滚整个事务
  • B.从兄弟节点借一个空闲键
  • C.均分分裂并把中间键上提← 正确答案
  • D.覆盖最旧的数值记录数据

答案：C。页满 → 均分分裂并上提中间键，这是 B+Tree 插入的固定动作。借键是删除侧的手段；报错或覆盖都不符合“插入永远可成功”的设计目标。就像书架满了就一分为二，而不是拒绝收书。

Q5. 删除后叶子页出现下溢，第一步应优先如何处理？

单选题 · mid

  • A.立即执行与兄弟页的合并
  • B.尝试向右或左兄弟借键← 正确答案
  • C.直接把父节点中的键删除
  • D.重建整棵索引树的结构

答案：B。下溢先借键，借不到才合并。合并会让父节点少一个键，可能连锁传播，因此是最后手段。图书馆书架太空时，管理员先找邻居匀书，两家都实在空才考虑并架。

Q6. 关于锁耦合（lock coupling）的表述，正确的是？

单选题 · hard

  • A.一次把整棵树的所有节点锁住
  • B.拿到子节点锁后立即释放父锁← 正确答案
  • C.完全不用锁只依赖数据复制
  • D.只对叶子节点加锁进行保护

答案：B。锁耦合 = 沿路径逐层加锁，拿到子节点锁就放父节点锁，整条路径同时最多两把锁。A 全树锁死吞吐全无；C 对应的是乐观并发或写时复制思路；D 忽略了路由过程同样需要保护。

Q7. 相比二叉树，B+Tree 在磁盘存储场景中的核心优势是？

单选题 · mid

  • A.扇出更大树高更矮 IO 更少← 正确答案
  • B.实现代码相对更简单易维护
  • C.插入删除不需要维护平衡性
  • D.占用的内存空间明显更小

答案：A。磁盘 IO 次数约等于树高，B+Tree 靠高扇出把树高压到 3~4 层。B 错了，多路树实现比二叉树复杂；C 错了，平衡维护正是 B+Tree 的工作；D 也未必，页内数组可能占用更多缓存。

Q8. 下列哪些是 B+Tree 的典型应用场景？

多选题 · easy

  • A.MySQL InnoDB 的主键索引← 正确答案
  • B.分布式 KV 的元数据路由← 正确答案
  • C.Redis 字符串缓存的数据
  • D.日志时间序区间范围检索← 正确答案

答案：ABD。InnoDB 主键索引、TiKV 的 Region 元数据路由、日志平台的时间序区间检索，都是 B+Tree 的主场；Redis 字符串缓存是内存哈希表，与 B+Tree 无关。B+Tree 擅长的是“有序、区间、低延迟读”。

Q9. 关于 B+Tree 页分裂与页合并，正确的说法有？

多选题 · mid

  • A.只有根节点分裂才增加树高← 正确答案
  • B.分裂后中间键上提到父节点← 正确答案
  • C.下溢时必须要立刻进行合并
  • D.合并传播可能降低整树高度← 正确答案

答案：ABD。只有根分裂才加层，中间键上提是分裂的标准动作，合并向上传播到根时可能让根收缩、树高减一。C 是常见误解：下溢时先借键，合并是实在借不到才做的最后手段。

Q10. 关于 B+Tree 并发控制机制，理解正确的有？

多选题 · hard

  • A.latch 保护物理页的短期结构操作← 正确答案
  • B.lock 管理事务级别的逻辑隔离← 正确答案
  • C.锁耦合同时最多持有两把锁← 正确答案
  • D.写时复制策略需要全局加锁

答案：ABC。latch 管物理页、lock 管事务逻辑，这是两类锁的基本分工；锁耦合“拿到子锁即放父锁”，同时最多两把。写时复制恰恰是为了免加锁而让读写并行，D 说反了。