数据库索引底层：B+ 树不是面试背完就够，还要知道为什么
数据库索引底层：B+ 树不是面试背完就够，还要知道为什么
一、B+ 树为什么是数据库索引的"标准答案"
面试官问"MySQL 索引用什么数据结构"，几乎所有人都能脱口而出"B+ 树"。但如果追问一句"为什么是 B+ 树而不是红黑树或跳表"，能给出有说服力解释的人就少了很多。
要回答这个问题，必须先理解数据库索引面临的真实物理约束。数据库的数据存储在磁盘上，而磁盘的随机访问延迟大约是内存访问的十万倍。这意味着索引结构的设计目标不是"让单次查找更快"，而是"让一次磁盘 I/O 能读到更多有用数据"。
CPU 缓存行、内存页、磁盘块——这些硬件层面的读取单元决定了数据结构的上限。B+ 树的设计完美利用了这些特性：每个节点的大小恰好等于一个磁盘页（通常是 4KB 或 16KB），一次 I/O 就能加载一个完整节点，节点内可以进行高效的二分查找。
flowchart TB subgraph 内存中 A[二分查找 O(log n)] --> |"单次访问 1-10ns"| B[结果] end subgraph 磁盘上 C[B+ 树查找 O(log_B n)] --> |"每层一次 I/O ~10ms"| D[磁盘页] D --> |"页内二分查找"| E[结果] end F[索引选择标准] --> G[最小化 I/O 次数] G --> H[增大分支因子 B] H --> I[减小树高度] I --> J[B+ 树树高通常 2-4 层]二、从磁盘 I/O 模型理解 B+ 树的分支因子
B+ 树的核心参数是分支因子 B，即每个节点能容纳的子节点数。这个值不是随意设定的，而是由磁盘页大小和键的大小共同决定。
假设页大小为 16KB，每个键（索引列）占 8 字节，指针占 8 字节，那么一个内部节点大约可以容纳 16KB / 16B ≈ 1000 个键值对。这意味着 B = 1000，树的高度 log_1000(N)。对于 10 亿条记录，树高仅为 log_1000(10^9) ≈ 3 层。
这就是为什么 B+ 树能做到每次查找只需 2-4 次 I/O。而红黑树在最坏情况下高度可能达到 2 log_2(N)，对于 10 亿数据就是约 60 层——每次查找都落在不同页上就是 60 次 I/O，性能差距是数量级的。
更重要的是 B+ 树的叶子节点链表。所有实际数据存储在叶子节点上，叶子节点之间通过指针相连。这让范围查询（WHERE id BETWEEN 100 AND 200）变得高效：定位到起始叶子节点后，沿链表顺序读取即可，无需回到上层节点。
三、手工实现一个极简 B+ 树
""" 极简 B+ 树实现 说明：仅展示核心查找和插入逻辑， 省略删除和节点合并以保持代码清晰。 分支因子 = 4，仅为演示，实际中通常大于 100。 """ class BPlusTreeNode: """B+ 树节点基类""" def __init__(self, is_leaf: bool = False): self.is_leaf = is_leaf self.keys = [] # 键列表 self.children = [] # 子节点引用（内部节点用） self.next_leaf = None # 叶子节点链表（叶子节点用） self.values = [] # 数据指针（叶子节点用） class BPlusTree: """ B+ 树实现 为什么分支因子设为 4：便于演示和验证， 生产环境中应根据页大小设定为 100+。 """ def __init__(self, order: int = 4): self.order = order # 最大子节点数 = 分支因子 self.max_keys = order - 1 # 节点最多存 order-1 个键 self.min_keys = (order + 1) // 2 - 1 # 节点最少存 ceil(order/2)-1 个键 self.root = BPlusTreeNode(is_leaf=True) def search(self, key: int): """ 查找键值 总是从根节点开始，沿内部节点下降到叶子节点。 为什么在内部节点用二分查找：键有序排列， 二分查找将查找时间从 O(B) 降到 O(log B)。 """ node = self.root # 从根下降到叶子 while not node.is_leaf: # 在有序键列表中找到第一个大于等于 key 的位置 i = 0 while i < len(node.keys) and key >= node.keys[i]: i += 1 node = node.children[i] # 在叶子节点中查找 for i, k in enumerate(node.keys): if k == key: return node.values[i] return None # 未找到 def insert(self, key: int, value): """ 插入键值对 为什么需要分裂节点：保持 B+ 树的平衡性。 如果插入后节点键数超过 max_keys，将节点分裂为两个。 """ root = self.root # 根节点满了，需要提升高度 # 这是 B+ 树增高的唯一方式，保证所有叶子在同一深度 if len(root.keys) == self.max_keys: new_root = BPlusTreeNode(is_leaf=False) new_root.children.append(self.root) self._split_child(new_root, 0, self.root) self.root = new_root self._insert_non_full(self.root, key, value) def _insert_non_full(self, node: BPlusTreeNode, key: int, value): """向非满节点插入""" if node.is_leaf: # 插入到叶子节点的有序位置 # 为什么保持有序：方便查找和范围扫描 i = 0 while i < len(node.keys) and key > node.keys[i]: i += 1 node.keys.insert(i, key) node.values.insert(i, value) else: # 在内部节点中，找到下一步的子节点 i = len(node.keys) - 1 while i >= 0 and key < node.keys[i]: i -= 1 i += 1 # 子节点满了，先分裂再决定走哪个 if len(node.children[i].keys) == self.max_keys: self._split_child(node, i, node.children[i]) if key > node.keys[i]: i += 1 self._insert_non_full(node.children[i], key, value) def _split_child(self, parent: BPlusTreeNode, index: int, child: BPlusTreeNode): """分裂子节点""" mid = self.order // 2 new_node = BPlusTreeNode(is_leaf=child.is_leaf) # 将后半部分键移到新节点 new_node.keys = child.keys[mid:] child.keys = child.keys[:mid] if child.is_leaf: # 叶子节点：复制值，维护链表 new_node.values = child.values[mid:] child.values = child.values[:mid] new_node.next_leaf = child.next_leaf child.next_leaf = new_node else: # 内部节点：复制子节点引用 new_node.children = child.children[mid:] child.children = child.children[:mid] # 将中间键提升到父节点 # 为什么叶子节点保留中间键的副本： # B+ 树所有数据在叶子，内部节点仅做索引 promote_key = new_node.keys[0] if child.is_leaf else child.keys.pop() parent.keys.insert(index, promote_key) parent.children.insert(index + 1, new_node)四、B+ 树不是万能钥匙：适用边界与替代方案
B+ 树不适合的场景：
纯内存场景。当数据完全在内存中时，B+ 树的优势（减少磁盘 I/O）不复存在，跳表在内存中通常性能更好。
极高频写入。B+ 树在插入时可能触发节点分裂，产生写放大。LSM-Tree（Log-Structured Merge-Tree）将随机写转为顺序写，在写密集场景优于 B+ 树。这也是 RocksDB 等存储引擎选择 LSM-Tree 的原因。
固定前缀查询。如果需要大量 LIKE 'abc%' 查询，B+ 树虽然支持范围扫描，但 Trie 树（前缀树）的空间效率更高。
聚簇索引 vs 非聚簇索引的选择：
聚簇索引的叶子节点直接存储行数据，而非聚簇索引的叶子存储主键值。这意味着通过非聚簇索引查找后，还需要一次"回表"操作通过主键查找完整行。这就是为什么 MySQL 的覆盖索引（查询列完全在索引中）可以避免回表、大幅提升性能。
一个重要的权衡：索引不是越多越好。每个索引在插入和更新时都需要维护，写操作的开销随索引数量线性增长。在实践中，单表索引数量通常不超过 5 个，且需要根据慢查询日志持续调整。
五、总结
B+ 树的优势不在算法复杂度，而在对磁盘 I/O 模型的深刻适配。它的三大设计支柱——大分支因子（减少树高）、叶子链表（加速范围查询）、所有数据在叶子层（等深平衡）——每一项都对应着一个数据库查询的物理约束。
理解这一点后，面试时就不会只答"B+ 树"三个字。你能说清楚分支因子和磁盘页的关系、为什么范围查询是 B+ 树的优势场景、以及什么情况下应该换用 LSM-Tree。这才是从"背答案"到"真理解"的跨越。