几乎每个数据库都在用的那棵树，出自一家一年少了 46,000 名员工的飞机公司

B 树起源于波音科学研究实验室。封面插图，AI 生成（Illustration, AI-generated）。

今天各类主流数据库与文件系统中的索引，底层大多采用 B 树或其变体 B+ 树。这项在计算科学中被广泛引用的数据结构，最初并非诞生于贝尔实验室或大学计算机系，而是出自波音科学研究实验室（BSRL）。

1966 年，Rudolf Bayer 在伊利诺伊大学获得数学博士学位，随后加入波音。波音当时在组建计算机科学部门，据他回忆，他是部门第一个真正的计算机科学家；波音承诺协助他将 J1 学生签证转为绿卡，开出的薪水最高，而且实验室设在西雅图，那是他心中的梦想之城。

波音于 1958 年设立了波音科学研究实验室，公司年报写明其任务是在「可能扩展飞行领域知识的任何科学领域」开展基础研究。当时波音规模庞大，1969 年全公司平均雇员人数达 120,500 人。但到 1970 年，受航空业萧条与多重因素影响，波音在 12 个月内净减少了 46,000 名在册员工，年底全美在册员工为 62,700 人。

B 树的构想，正是在这次大收缩前夕诞生的。

一块黑板与一台 7.25 MB 的磁盘

1969 年秋天，30 岁的 Bayer 走进同事 Ed McCreight 的办公室，在黑板上勾勒出一个新型文件索引的构想。McCreight 当年刚从卡内基梅隆大学获得计算机科学博士学位。两人商定分工，Bayer 负责算法描述与复杂度分析，McCreight 负责工程实现并运行测试。

据 Bayer 事后回忆，激发这个题目的一个现实背景是波音 747 的制造管理。大量零部件及其制造履历，让当时的数据处理能力接近极限。两人当时还不清楚这个想法有多大分量，但立刻意识到这个题目很有价值。

他们使用的计算设备是一台 IBM System/360 Model 44 计算机，外接一台容量为 7.25 MB 的 IBM 2311 磁盘驱动器。这台计算机的主存上限为 256 KB。测试中实际处理的索引通常在 1 万条记录左右，而程序能分配给分页缓冲区的内存空间仅能容纳大约 1,250 条索引。

面对装不进内存的大规模有序数据，程序需要按需从磁盘读取索引，并利用内存缓冲区减少磁盘 I/O。

IBM 2311 磁盘驱动器（同型号设备）。Photo by ArnoldReinhold, CC BY-SA 3.0, via Wikimedia Commons.

IBM System/360 Model 44 计算机（同型号设备，主存上限 256 KB）。Photo by Living Computers Museum+Labs, CC BY-SA 4.0, via Wikimedia Commons.

磁盘访问与二叉树的瓶颈

在计算机内存中，平衡二叉搜索树（如 AVL 树）是一种常见的查找结构，每个节点存储一个键，并分别指向左子树和右子树。然而，移到机械磁盘上时，这种结构遇到了物理性能瓶颈。

根据 IBM 1969 年的手册，IBM 2311 磁盘驱动器的每秒连续数据传输速率为 156,000 字节。按一条索引 14 字节计算，连续传输一条数据理论上仅需 89.7 微秒。

机械磁盘最耗时的开销在于物理定位。磁头移动到指定柱面并等待盘面旋转到位。论文在其测试条件与分析中采用约 50 毫秒的平均访问机构延迟（即 50,000 微秒），是连续传输一条索引元素所需时间的 500 多倍。这是论文使用的参数，并非所有条件下的设备寻道规格。

如果用平衡二叉树管理 100 万条记录，查找路径大约有 20 层。假设每层节点都在不同的磁盘页上，且这些页都不在缓存中，一次查找就可能需要约 20 次物理读盘；按论文采用的平均访问延迟粗略估算，定位部分约需 1 秒。实际读盘次数取决于节点布局和缓存。

多路平衡与 K = 60 的工程取舍

Bayer 和 McCreight 的解决思路是把树压扁，从而大幅降低树的高度。

他们放弃了一节点一键的传统做法，把一个节点做成容纳多条有序记录的磁盘页。树不再是二叉树，而是拥有众多分支的多路平衡树。树的每个节点至多存放 2k 条记录，并引出多达 2k + 1 个指向子节点的指针。

查找时，程序将所需节点页读入内存；CPU 在页内查找目标键，或确定下一次访问的子页地址。算法同时严格保证所有叶子节点处于完全相同的深度，从而避免了传统树结构退化为倾斜树的问题。

多路分枝带来了显著的扇出效应。在论文给出的容量推演表中，当每个节点容纳 120 条记录（分支达 121 路）时，高度仅为 3 层的树在节点填满时足以容纳最多 1,771,560 条记录。对于这样一棵三层树，若查找一路走到叶节点，且路径上的页都不在缓存中，则需要读取三个索引页。实际树的高度和读盘次数取决于节点填充情况与缓存。

但磁盘页并非越大越好。当参数 k 过小时，节点容量有限，树的高度增加，可能需要更多次磁盘访问。而当 k 过大时，单页传输的数据量过大，程序需要花费更多时间将数据读入有限的内存。论文模型中的页容量取舍涉及固定访问开销 α（取约 50 毫秒）与每个索引元素的增量传输开销 β（取约 90 微秒）。

论文给出了两组数据，一是查表得出的可接受区间 64 < k < 128（对应每页 128 到 256 条记录）；二是基于测试参数的最优页预测约为 120 条记录（对应 k ≈ 60）。在编写测试程序时，作者在论文中写明，出于编程方便的考虑选择 k = 60，对应每页 120 条记录。

「For reasons of programming convenience we chose k = 60 resulting in a page size of 120 entries.」 （出于编程方便的考量，我们选择了 k = 60，对应每页 120 条记录。）

测试中每条索引占用 14 字节。McCreight 编写了代码并在机器上运行了 10 组测量，分别测试了每页 25、120 和 250 个元素的配置。1970 年 7 月，波音内部技术报告 D1-82-0989 正式完成。

论文发表、顶刊退稿与波音大收缩

这项成果随后经历了内部报告、学术会议与期刊发表的流转。1970 年 7 月，两人先完成了波音内部技术报告《大型有序索引的组织与维护》（编号 D1-82-0989）。同年 11 月 15 日至 16 日，论文在休斯敦举行的 ACM SIGFIDET 研讨会上宣读，全文收录于会议论文集。这项成果由此通过会议论文集进入学术交流。

但据 Bayer 回忆，在投向计算机科学旗舰期刊 CACM（Communications of the ACM）时，论文曾被退稿。审稿人认为类似做法已经存在，而且断言哈希做得更好。Bayer 在回忆录中感叹，这「大概是计算机科学最大的误判之一」。同一时期，Sperry Univac 与 CDC 确实也在独立研发类似的多路树索引结构。《Acta Informatica》于 1971 年 9 月 29 日收到这篇论文，并于 1972 年正式刊出。

论文面世的同时，波音遭遇了严重的经营危机。747 项目的前期巨额投入、军工订单缩减以及民航市场萧条叠加，导致公司现金流极度紧张。1971 年 4 月，西雅图附近还出现了那块著名的标语牌：「最后一个离开西雅图的人，请把灯关掉。」

1971 年 4 月 16 日，西雅图塔科马机场附近立起的「请把灯关掉」标语牌，下方为发起人 Bob McDonald 与 Jim Youngren。Photo courtesy of The Seattle Times / HistoryLink (Essay 1287), via OOH Today.

根据波音公司 1970 年年报，全公司在册员工在这一年内净减少了 46,000 人，年底全美在册员工降至 62,700 人。波音需要全力节约开支，据 Bayer 回忆，研究所转向更偏应用的工作，基础研究不再受到重视。

实验室的研究人员陆续离开。Bayer 于 1970 年离开波音前往普渡大学任教，1972 年 6 月赴慕尼黑工业大学任教；McCreight 随后也离开波音，加入施乐帕洛阿尔托研究中心（Xerox PARC）。

午餐定名与半个世纪的回响

1979 年 6 月，Douglas Comer 在 ACM Computing Surveys 发表了经典综述《无处不在的 B 树》，开篇写道，这种数据结构拥有短暂但重要的历史。

关于 B 树名字的来源，坊间曾猜测代表波音（Boeing）、平衡（Balance）或是 Bayer 本人的姓氏。McCreight 后来在 2012 年回忆，这个命名源于一次午餐时的讨论。他们希望名字短、好打、好记；B 可以向波音致意，用 B 又不必向公司专门请示；B 可以暗示平衡，Bayer 也是两人中资历更深的那位；出于美式英语使用者都明白的原因，BM Tree 不能用。McCreight 写道，他不记得那天哪个含义压过了其他几个；而 Bayer 后来总爱说，越琢磨 B 可能代表什么，就越了解 B 树，这是好事。

半个世纪过去，B 树及其变体已成为现代存储系统中最基础的数据结构之一。从 SQLite 的表与索引，到 PostgreSQL 的默认 B-tree；从 MySQL InnoDB 的聚簇索引与二级索引，再到 Linux Btrfs 与苹果 APFS 的元数据管理，主流系统至今仍依赖这种结构来组织磁盘数据。

在 1970 年的测试中，当每页最多选定 120 个元素（每条 14 字节）时，满页的索引元素合计约为 1,680 字节，不包括页的其他结构。现代数据库则根据现代存储硬件的块大小设定物理页大小（例如 4 KB、8 KB、16 KB）。存储介质从机械磁盘发展到固态硬盘，随机访问与连续传输的性能特征也随之变化。当年在西雅图黑板上勾勒的多路平衡结构，至今仍在影响数据在外存与内存之间的组织方式。

参考文献与一手档案

• Rudolf Bayer, Edward M. McCreight, Organization and Maintenance of Large Ordered Indices, Proceedings of the 1970 ACM SIGFIDET Workshop on Data Description, Access and Control, Nov 15-16, 1970, Houston, Texas, pp. 107-141.
• Rudolf Bayer, Edward M. McCreight, Organization and Maintenance of Large Ordered Indexes, Acta Informatica 1, 173-189 (1972).
• Rudolf Bayer, Memoiren, Technical University of Munich (TUM), 2014.
• Douglas Comer, The Ubiquitous B-Tree, ACM Computing Surveys 11(2), June 1979, pp. 121-137.
• Boeing Airplane Company Annual Reports (1958, 1968-1972), Internet Archive.
• IBM Corporation, IBM System/360 System Summary, 11th Edition, August 1969 (GA22-6810-10).
• Edward M. McCreight, Origin of the B-Tree Name, personal website notes (2012).
• SQLite Consortium, SQLite Database File Format §1.5, B-tree Pages, sqlite.org.