什么是 B-tree 和 B+ tree，数据库为什么要使用它们？

Question

Accepted Answer

**B-tree** 是一种自平衡搜索树，其中每个节点持有**很多键**并且有**很多子节点**（高 *fanout*）。这样可以保持树的**深度较浅**，最小化**磁盘读取**的次数——这正是数据库和文件系统所需要的。 ## 为什么高 fanout 胜过二叉树 ```text Binary BST over 1,000,000 keys -> height ~20 (20 disk seeks) B-tree, 100 keys/node -> height ~3 (3 disk seeks) Each node = one disk block/page read. ``` ## 结构（B-tree 阶数 4） ```text [ 17 | 35 ] / | \ [4|9|12] [20|28] [40|50|60] each node packs many keys -> few levels ``` ## B+ tree 优化在 **B+ tree** 中，*所有值都存储在叶子节点*，而且叶子节点**相互链接**，因此范围扫描可以沿着叶子节点的链表行进——非常适合像 `WHERE age BETWEEN 20 AND 40` 这样的查询。 ```text internal nodes: keys only (routing) leaves: [..]<->[..]<->[..] <- linked for fast range scans ``` ## 复杂度 | Operation | Time | Disk I/O | |---|---|---| | search | O(log n) | O(height) | | insert / delete | O(log n) | O(height) | | range scan | O(log n + k) | sequential leaves | ## 为什么这很重要磁盘和 SSD 的访问速度比内存慢几个数量级，所以真正重要的指标是 **I/O 次数，而非比较次数**。高 fanout 通过保持树的深度只有几层来大幅减少 I/O。这就是为什么几乎所有关系数据库索引（以及许多文件系统）都采用 B+ tree 而非二叉搜索树。

Operation	Time	Disk I/O
search	O(log n)	O(height)
insert / delete	O(log n)	O(height)
range scan	O(log n + k)	sequential leaves