一、为什么需要 B+ 树
假设你在设计一个数据库，表里有 10 亿条记录，索引键是用户 ID。数据存在磁盘上，每次读取一个磁盘页大约 10ms。如果用二叉搜索树做索引，树高大约 30 层（log₂ 10⁹），一次查询需要 30 次磁盘读取，也就是 300ms——用户点一个搜索按钮要等半秒，不可接受。
红黑树或 AVL 树能保证平衡，但每个节点只存一个键和两个子指针，一个磁盘页（通常 4KB 或 8KB）只能装下一个节点，太浪费了。一次磁盘读取换来一个键的比较，性价比极低。
问题的核心是：磁盘 I/O 是按页计费的，不是按字节计费的。读取 1 字节和读取 4KB 花的时间几乎一样。所以你希望每次读一页，能比较尽可能多的键。这就是 B+ 树的设计动机——让每个节点装下几百个键，把树压扁，减少层数，从而减少磁盘读取次数。
二、现实类比
图书馆的卡片目录柜。顶层是一排大抽屉，每个抽屉上贴着一个范围标签：「A-Da」「Db-Ha」「Hb-Ma」。你根据标签找到对应的大抽屉，打开后发现里面不是书，而是更小的抽屉，每个小抽屉又贴着更细的范围：「A-An」「Ao-Da」。最后一层的小抽屉里才是真正的书卡——上面写着书名、作者和书架位置，而且这些书卡按字母顺序串在一起。
关键点：大抽屉和小抽屉只负责「指路」，不存放真正的书卡。只有最底层的抽屉才存放数据，并且相邻抽屉之间用链条串起来。这样，找一本书只需要开几个抽屉，而要找某个范围内的所有书，只需要在底层沿着链条顺序扫描。
三、核心思想
B+ 树是一种平衡多路搜索树。内部节点只存键和子指针，不存数据——纯路由角色。叶子节点存键值对，且所有叶子通过链表串联，支持高效的范围扫描。每个节点对应一个磁盘页，高扇出（fanout）让树变得很矮。
高扇出 = 矮树 = 少读磁盘。一个阶数（order）为 100 的 B+ 树，每个内部节点最多 100 个键、101 个子指针。3 层就能存 100 万个键（100 × 100 × 100），4 层存 1 亿，5 层存 100 亿。也就是说，在 10 亿条记录中查找，只需要 5 次磁盘读取——从 300ms 降到 50ms。
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| 点查询 | O(logₘ N) | M 为阶数，实际约 3-5 次磁盘 I/O |
| 范围查询 | O(logₘ N + K) | K 为结果数量，叶子链表顺序扫描 |
| 插入 | O(logₘ N) | 可能触发节点分裂，向上传播 |
| 删除 | O(logₘ N) | 可能触发节点合并或借用 |
四、变体与对比
| 结构 | 内部节点存数据 | 叶子链表 | 适合场景 |
|---|---|---|---|
| B+ 树 | 否（只存键） | 有 | 数据库索引、文件系统、范围查询 |
| B 树 | 是（键值都在节点） | 无 | 早期数据库、嵌入式存储 |
| LSM 树 | N/A（写内存，合并到磁盘） | N/A | 写多读少、追加写入 |
| 哈希索引 | N/A（O(1) 直接定位） | N/A | 纯等值查询、内存缓存 |
为什么数据库选 B+ 树而不是 B 树？两个核心原因：
- 扇出更高。B+ 树内部节点不存值，同样大小的磁盘页能放更多键，树更矮，磁盘 I/O 更少。
- 范围扫描更简单。B+ 树的叶子链表让范围查询变成链表的顺序遍历；B 树做范围查询需要反复回溯父节点，实现复杂且 I/O 多。
B 树的优势在哪？虽然 B+ 树是数据库索引的主流选择，B 树在特定场景下反而更优。B 树的关键区别在于每个节点都存储键值对——内部节点也不例外。这意味着点查询可能在中途就能命中数据返回，不必一路走到叶子，在某些情况下能减少 1 次磁盘 I/O。但代价也很明显：内部节点存了值，同样大小的磁盘页能放的键更少，扇出更低，树更高，范围查询也更麻烦。SQLite 是一个典型的例子——它的表数据用 B 树而非 B+ 树存储。原因在于 SQLite 的典型工作负载是嵌入式设备的点查询（比如手机上的通讯录查找），而不是服务端的大范围扫描。点查询场景下，B 树提前命中数据带来的 I/O 节省更有价值，而 B+ 树叶子链表对范围扫描的优势用不上。
B-link 树（PostgreSQL 使用的变体）：在每个节点增加指向右兄弟的链接。当节点分裂时，即使父节点还没更新，其他线程也能通过右兄弟链接找到正确位置，实现并发访问而不需要全局锁。这是 Lehman-Yao 算法的核心思路。
联合索引的最左前缀规则：索引 (status, region) 可以高效查询 status 或 status + region，但无法高效查询单独的 region——因为 B+ 树按左到右的列顺序组织键。
五、多语言实现
5.1 Go 实现——搜索与插入
package bplustree
import "sort"
// BPlusTree 的节点type Node struct { keys []int // 键列表 children []*Node // 子指针（内部节点用） values []string // 值列表（叶子节点用） next *Node // 叶子链表右指针 isLeaf bool}
type BPlusTree struct { root *Node order int // 每个节点最多 order 个键}
func New(order int) *BPlusTree { return &BPlusTree{ root: &Node{isLeaf: true}, order: order, }}
// Search 在树中查找 key 对应的值func (t *BPlusTree) Search(key int) (string, bool) { leaf := t.findLeaf(key) idx := sort.SearchInts(leaf.keys, key) if idx < len(leaf.keys) && leaf.keys[idx] == key { return leaf.values[idx], true } return "", false}
// findLeaf 沿内部节点一路向下，找到 key 所属的叶子func (t *BPlusTree) findLeaf(key int) *Node { node := t.root for !node.isLeaf { // 找到第一个大于 key 的位置，进入对应子树 idx := sort.SearchInts(node.keys, key) node = node.children[idx] } return node}
// Insert 插入键值对，必要时分裂节点func (t *BPlusTree) Insert(key int, value string) { leaf := t.findLeaf(key) t.insertIntoLeaf(leaf, key, value) // 键数超过上限，需要分裂 if len(leaf.keys) >= t.order { t.splitLeaf(leaf) }}
func (t *BPlusTree) insertIntoLeaf(leaf *Node, key int, value string) { idx := sort.SearchInts(leaf.keys, key) leaf.keys = append(leaf.keys, 0) leaf.values = append(leaf.values, "") // 向后移动腾出位置 copy(leaf.keys[idx+1:], leaf.keys[idx:]) copy(leaf.values[idx+1:], leaf.values[idx:]) leaf.keys[idx] = key leaf.values[idx] = value}
// splitLeaf 将叶子节点一分为二，把中间键提升到父节点func (t *BPlusTree) splitLeaf(leaf *Node) { mid := len(leaf.keys) / 2 newLeaf := &Node{ keys: append([]int{}, leaf.keys[mid:]...), values: append([]string{}, leaf.values[mid:]...), isLeaf: true, next: leaf.next, } leaf.keys = leaf.keys[:mid] leaf.values = leaf.values[:mid] leaf.next = newLeaf // 维护叶子链表
// 将新叶子的最小键提升到父节点 t.insertIntoParent(leaf, newLeaf.keys[0], newLeaf)}
// insertIntoParent 递归向上插入分裂产生的键和子节点func (t *BPlusTree) insertIntoParent(left *Node, key int, right *Node) { if left == t.root { // 根节点分裂，创建新根 t.root = &Node{ keys: []int{key}, children: []*Node{left, right}, } return } // 简化：实际需要回溯查找父节点并处理内部节点分裂 // 生产实现通常在搜索路径上保存父节点栈}Go 实现展示了 B+ 树的核心操作流程：搜索时沿内部节点逐层下降到叶子；插入时先在叶子中找到位置，键数超限则分裂，分裂后的中间键向上传播。
5.2 TypeScript 实现——搜索与范围查询
interface LeafNode { isLeaf: true; keys: number[]; values: string[]; next: LeafNode | null;}
interface InternalNode { isLeaf: false; keys: number[]; children: BPlusNode[];}
type BPlusNode = LeafNode | InternalNode;
class BPlusTree { root: BPlusNode; order: number;
constructor(order: number) { this.root = { isLeaf: true, keys: [], values: [], next: null }; this.order = order; }
// 点查询：沿内部节点下降到叶子 search(key: number): string | undefined { let node = this.root; while (!node.isLeaf) { let i = 0; // 找到第一个大于 key 的位置 while (i < node.keys.length && key >= node.keys[i]) i++; node = node.children[i]; } const idx = node.keys.indexOf(key); return idx !== -1 ? node.values[idx] : undefined; }
// 范围查询：找到起点后沿叶子链表顺序扫描 rangeSearch(start: number, end: number): Map<number, string> { const result = new Map<number, string>(); let node: BPlusNode = this.root;
// 先下降到起始叶子 while (!node.isLeaf) { let i = 0; while (i < node.keys.length && start >= node.keys[i]) i++; node = node.children[i]; }
// 沿叶子链表扫描直到超出范围 let leaf = node as LeafNode; while (leaf !== null) { for (let i = 0; i < leaf.keys.length; i++) { if (leaf.keys[i] > end) return result; // 超出上界，直接返回 if (leaf.keys[i] >= start) { result.set(leaf.keys[i], leaf.values[i]); } } leaf = leaf.next; } return result; }}TypeScript 实现重点展示了 B+ 树最独特的优势——范围查询。先定位到起始叶子，然后沿 next 指针顺序扫描，无需回溯父节点。这正是 B+ 树成为数据库索引标配的核心原因。
六、生产验证
PostgreSQL——nbtinsert.c——PostgreSQL 的 B+ 树索引（文档中称 B-tree，实际是 B-link 树/Lehman-Yao 变体）。文件头注释明确写明 “Item insertion in Lehman and Yao btrees”。每个节点带有右兄弟链接（right sibling link），分裂时无需全局锁，其他并发线程可以通过右链接继续搜索。_bt_stepright、_bt_split、_bt_insert_parent 等函数协同完成无锁并发插入。
SQLite——btreeInt.h——SQLite 中所有表和索引都由 B+ 树支撑。BtShared 结构体管理共享的页面缓存和 B+ 树元信息，pageSize、maxLocal/minLocal、maxLeaf/minLeaf 等字段控制每个页面的有效载荷上限，超过时溢出到溢出页。数据库文件就是一组磁盘页的集合，每个页是一棵 B+ 树的节点。
InnoDB（MySQL）——MySQL 的 InnoDB 存储引擎使用 B+ 树组织聚簇索引和二级索引。聚簇索引的叶子节点直接包含行数据，二级索引的叶子节点存主键值，查询时可能需要回表。page size 默认 16KB，非叶子页可容纳约 1170 个键，3 层 B+ 树可索引约 2000 万行。
七、小结
适合使用 B+ 树的场景：
- 数据库索引——点查和范围查都高效，几乎所有关系型数据库的默认选择
- 文件系统目录——NTFS、ext4、Btrfs 用 B+ 树管理文件名到磁盘块的映射
- 需要范围查询的有序数据——叶子链表让范围扫描变成顺序读取
- 磁盘存储——高扇出降低树高，把磁盘 I/O 次数压到个位数
不适合使用 B+ 树的场景：
- 小规模内存数据——数据能全部放内存时，哈希表或 BST 更简单，不需要考虑页对齐
- 写多读少——频繁插入导致页分裂，LSM 树（写内存、后台合并）更适合
- 纯等值查询——哈希索引 O(1) 比 B+ 树 O(log N) 快，且实现更轻
- 追加写入为主的场景——页分裂开销大，LSM 树或日志结构存储更合适
八、参考资料
- PostgreSQL nbtree 文档 - PostgreSQL B+ 树实现细节，包含 Lehman-Yao 并发控制机制
- SQLite 文件格式 - SQLite 数据库文件格式规范，B+ 树页面布局的权威参考
- B+ 树原始论文 - Douglas Comer, 1979, The Ubiquitous B-Tree
- Lehman-Yao 并发 B 树 - Lehman & Yao, 1981, 高并发 B 树的右链接方案
- MySQL InnoDB 存储引擎 - InnoDB 内部实现，B+ 树索引结构
支持与分享
如果这篇文章对你有帮助，欢迎支持作者或分享给更多人
部分信息可能已经过时