B / B+ 树B-tree family

在一个节点内保存多个键，降低树高和访问次数。

常见操作#

n 为记录数，B 为节点可容纳记录数的量级，k 为结果数；区分块 I/O 与 CPU 工作。

操作	时间复杂度	条件与说明
B / B+ 树：按键查找	$O(\log_{B} n)$ 次块访问	节点占一个存储块且维持填充率；节点内二分查找累计 $O(\log n)$ 次比较。
B / B+ 树：插入 / 删除	$O(\log_{B} n)$ 次块访问	包含分裂、借位与合并；CPU 上移动节点内元素的成本另计。
B+ 树：范围扫描	$O\left(\log_B n+\frac{k}{B}\right)$ 次块访问	叶子按键顺序相连、记录稠密存于叶子；另有 $O(k)$ 输出工作。
B 树：有序遍历	$O(n)$	记录可在内部节点，需按树的中序规则访问，不能直接套 B+ 树的叶子链实现。
有序数据批量装载	$O(n)$	顺序填充叶层再构建上层的 B+ 树实现；输入若无序，排序成本另计。

B 不能被隐藏成固定常数后又用于解释 I/O 优势；缓存、页分裂、MVCC 与 WAL 会改变实际成本。

1 个案例 · 附源码

SQLite·数据库文件与页version-3.46.0

SQLite 将表和索引组织成数据库页上的 B-tree，用一个节点容纳多个键，支持有序定位与范围遍历。

附源码片段 · 存储与数据放置

基础原理参考资料

Open Data Structures · B-Trees外存模型、节点容量及查找和更新的块访问界。

PostgreSQL 17 · B-Tree implementation真实索引的叶子、内部页、同层双向链接和页分裂。

CMU 15-445 · Tree indexesB+ 树范围扫描与有序输入的批量装载。