B+树的概念

B+树的概念

B+树（B+ Tree） 是一种多路平衡搜索树，也是 B树（B-Tree）的变体。它最大的特点是所有数据都存储在叶子节点，非叶子节点仅用于索引。这种结构使其在数据库和文件系统等需要大量磁盘 I/O 的场景中表现极其优异，是 MySQL InnoDB 等主流关系型数据库的默认索引结构。

核心特性

  1. 数据全在叶子节点：非叶子节点只存储索引键（Key）和指向子节点的指针，不存储实际数据（Data/Record）。
  2. 叶子节点形成链表：所有叶子节点通过指针（通常是双向链表）连接在一起，极大地优化了范围查询和排序操作。
  3. 高度平衡：从根节点到每个叶子节点的路径长度相同，保证了查询的时间复杂度稳定为 O(logN) 。
  4. 高扇出（High Fan-out）：非叶子节点可以包含成百上千个子节点指针，这使得 B+树非常“矮胖”。例如，一个 3 层的 B+树就能索引上千万条数据。

B+树 vs B树：为什么数据库偏爱 B+树？

表格
 
特性B树 (B-Tree)B+树 (B+ Tree)B+树的优势
数据存储位置 所有节点都存数据 仅叶子节点存数据 非叶子节点能容纳更多索引，树更矮，减少磁盘 I/O 次数。
范围查询 需要中序遍历整棵树 只需遍历叶子节点的链表 范围查询效率极高，无需回溯父节点。
查询稳定性 最好查根节点，最差查叶子 每次都必须查到叶子节点 查询性能极其稳定，没有忽快忽慢的情况。
磁盘预读与局部性 数据分散在各层 连续数据集中在叶子层 完美契合操作系统的页缓存（Page Cache）和磁盘顺序读取机制。

时间复杂度

  • 查找、插入、删除：O(logN)
  • 范围查询： O(logN+M)  ，其中 M 是结果集大小。由于叶子节点是链表，找到起点后直接顺序扫描即可。

实际应用场景

  1. 关系型数据库索引：MySQL (InnoDB), PostgreSQL, Oracle 等底层几乎全部使用 B+树。
    • 聚簇索引：叶子节点直接存放完整的行数据。
    • 非聚簇索引（二级索引）：叶子节点存放主键值，查询需要“回表”。
  2. 文件系统：NTFS, ext4, ZFS 等使用 B+树或其变体来管理文件目录和元数据。
  3. NoSQL 数据库：MongoDB, Cassandra 等也广泛采用类似结构。

一个简单的 B+树示意 (阶数 m=3)

  
            [ 10 | 20 ]                <-- 根节点 (仅索引)/      |      \[5|8]    [12|15]    [22|25]      <-- 内部节点 (仅索引)/ | \    / | \      / | \[5][8] [12][15] ... [22][25]       <-- 叶子节点 (存真实数据)\_____/   \_____/    \_____/<->        <->        <->      <-- 双向链表连接