前言

在现代互联网系统与数据库技术中，数据的高效查询与有序存储一直是核心目标。尤其在关系型数据库和文件系统中，B-Tree 是广泛使用的数据结构，它以平衡、有序、高效的方式组织大量数据，支撑着几乎所有数据库的索引系统。

定义

Wiki 定义如下：

A B-tree is a self-balancing tree data structure that maintains sorted data and allows searches, sequential access, insertions, and deletions in logarithmic time.

简单来说：B-Tree 是一种平衡的多路搜索树，适用于大规模数据的插入、查找和删除。

工作原理

一句话：通过多叉树的分支结构，使数据在磁盘中以较少的 IO 次数被访问到，保证高效的读写性能。

工作方式如下：

  1. 所有数据都按有序排列；
  2. 每个节点包含多个键值对，且具有多个子节点；
  3. 数据插入时，节点可分裂，确保树高平衡；
  4. 数据查找从根节点开始，依序在内部节点查找范围，直到叶节点；
  5. 删除操作同样保持树结构平衡。

属性与指标

关注的 B-Tree 属性与指标如下：

  1. 节点阶（Order） 决定每个节点最大/最小子节点数量。

  2. 树的高度（Tree Height） 越低越好，意味着更少的磁盘 IO。

  3. 键分布与排序 所有键全局有序，便于范围查询与二分查找。

  4. 磁盘友好性（Disk Optimization） 每个节点通常与磁盘块对应，减少磁盘访问次数。

  5. 插入删除复杂度 插入和删除操作时间复杂度为 O(log n)。

  6. 平衡性 所有叶节点在同一层，确保读写性能稳定。

类型

B-Tree 变种

  1. B+ Tree 所有数据存储于叶子节点，内部节点仅作索引；广泛用于数据库与文件系统。

  2. B Tree* B+ Tree 的优化版，提升空间利用率。

  3. B^ε Tree 针对写优化的 B-Tree 变体，适用于写入频繁的系统。

  4. Fractal Tree 进一步提升写性能，应用于写入密集型场景（如 TokuDB）。

存储类型

根据应用场景，B-Tree 常用于以下结构：

  1. 数据库索引（主键索引/二级索引）
  2. 文件系统元数据存储
  3. 排序数组或块索引
  4. 持久化 KV 存储引擎

B-Tree 与程序关系

B-Tree 既可以嵌入在数据库内部（内嵌引擎），也可以作为外部系统（如文件系统）的核心数据结构。

  1. In-Memory B-Tree：如 Java 的 TreeMap、C++ STL 的 map。
  2. Persistent B-Tree：如 MySQL InnoDB 索引、PostgreSQL 的 BTREE 索引。
  3. Hybrid 模型：如内存中部分节点缓存，磁盘上持久化其余结构。

常用产品实现

以下是常用采用 B-Tree 或其变种的系统：

  1. MySQL InnoDB – 使用 B+ Tree 作为主索引结构；
  2. PostgreSQL – 默认索引类型为 B-Tree；
  3. LevelDB / RocksDB – 内部跳表，但部分系统接入了 B-Tree for metadata；
  4. Lucene / Elasticsearch – 虽以倒排索引为主，但对段元数据管理常用 B-Tree；
  5. HFS+ / NTFS 文件系统 – 使用 B-Tree 存储目录项和元数据；
  6. Oracle Database – B-Tree 与 B-Tree Clustered Index 构成索引核心。