> ## Content Index
> Fetch the complete content index at: https://huizhou92.com/llms.txt
> Use this file to discover other available public pages before exploring further.

# 波音关闭实验室后，他转身去施乐 PARC，为个人电脑装上了硬盘
- URL: https://huizhou92.com/edward-mccreight-b-tree-xerox-alto/
- Published: 2026-11-05T12:00:53.000Z
- Updated: 2026-11-05T12:00:53.000Z
- Description: 1970 年波音因经营收缩削减基础科研，刚刚在黑板上推导出 B 树的年轻博士 Edward McCreight 告别西雅图，南下加入施乐 PARC。在个人计算原型 Xerox Alto 面对旋转磁介质的物理约束时，他与 Butler Lampson 联手，用单板 55 块芯片、150 条微指令与防御性标签校验，为现代个人计算机打造了软硬协同的本地磁盘系统。本文紧密承接 11/01 B 树母题，拆解同一位工程师在算法与体系结构两端对磁盘瓶颈的硬核求解。
- Author: huizhou92
- Tags: #lang-zh-cn

*封面插图：1973 年施乐 PARC 实验室里的 Xerox Alto 个人工作站与 Diablo 磁盘系统。AI 生成（Illustration, AI-generated）。*

在上一篇关于 B 树起源的文章（《[几乎每个数据库都在用的那棵树，出自一家一年少了 46,000 名员工的飞机公司](https://huizhou92.com/ji-hu-mei-ge-shu-ju-ku-du-zai-yong-de-na-ke-shu-chu-zi-yi-jia-yi-nian-shao-liao-46-000-ming-yuan-gong-de-fei-ji-gong-si/)》）里，我们讲到了 1970 年西雅图那个骤然收缩的飞机制造帝国，以及波音科学研究实验室（BSRL）里的年轻人。

那篇文章的结尾留下了一段走向：随着波音经营收缩、基础研究实验室转向应用开发，研发人员各奔东西。资历更深的 Rudolf Bayer 远赴高校任教，而负责工程实现的 24 岁博士 Edward McCreight，则离开西雅图南下加州，跨进了刚刚成立的施乐帕洛阿尔托研究中心（Xerox PARC）。

这位刚在西雅图黑板上用代码跑通 B 树的年轻工程师，到了硅谷之后并没有留在纯软件的世界里。

进入 1970 年代初，他与 Butler Lampson 联手，为现代个人计算机的原型 Xerox Alto 打造了一套塞进桌下机箱的本地磁盘系统。

从西雅图的算法黑板，到帕洛阿尔托的微码机箱，McCreight 在短短几年内两度面对旋转磁介质。这是计算机历史上极具戏剧性的一段接力：同一位系统工程师，面对同一种物理介质在不同层级呈现的瓶颈，给出了两次截然相反的工程解决方案。

### 西雅图的上一局：机械臂太慢，怎么少读几次盘？

回到 1969 年秋天波音西雅图实验室的那块黑板。

Bayer 在自己的办公室黑板上勾勒出新型文件索引的构想；两人分工明确：Bayer 负责算法描述与数学分析，McCreight 负责编写代码并在 IBM System/360 Model 44 计算机上进行实测验证。

当时外接的存储设备是容量 7.25 MB 的 IBM 2311 活动磁头磁盘驱动器。

![IBM 2311 磁盘驱动器](https://upload.wikimedia.org/wikipedia/commons/thumb/f/ff/IBM_2311_Disk_Drive.agr.jpg/1280px-IBM_2311_Disk_Drive.agr.jpg)

*IBM 2311 活动磁头磁盘驱动器（同型号设备，容量 7.25 MB，Bayer 与 McCreight 在波音测试 B 树时采用的外存设备型号）。Photo by ArnoldReinhold, CC BY-SA 3.0, via* [*Wikimedia Commons*](https://commons.wikimedia.org/wiki/File:IBM%5F2311%5FDisk%5FDrive.agr.jpg?ref=huizhou92.com)*.*

这台设备暴露了一个残酷的物理现实：**机械等待远比连续数据传输昂贵**。连续读取一条 14 字节的索引元素大约只需 90 微秒；但要把磁头移动到指定柱面并等待盘面旋转到位，平均访问机构延迟高达约 50 毫秒，相差五百倍以上。

如果在磁盘上直接套用内存中常见的二叉查找树，随着数据量膨胀，查找路径会变得很深。每一次向下查找都可能触发一次物理读盘，系统大部分时间只能在机械等待中空转。

Bayer 与 McCreight 的思路是把节点大小精确对齐到磁盘页，在一个节点内装入尽可能多的有序键，从而大幅提高分支因子。这就是 B 树。

树的高度被多路分支迅速压平。在原论文给出的推演中（第 186 页 Fig. 9），当每个节点可容纳 120 条记录时，一棵仅有 3 层的树在满载时就足以容纳约 **177 万个键**。这意味着检索数据时最多只需读取 3 个页面，从而极大减少了外存 I/O 的调用频次。

1970 年，波音削减基础科研，并将实验室转向应用开发。Bayer 于当年离开波音前往普渡大学，后于 1972 年赴慕尼黑工业大学任教；McCreight 随后告别西雅图，加入刚刚组建的施乐 PARC 计算机科学实验室。

在波音，McCreight 与 Bayer 的任务是**通过纯算法把树压扁，减少硬盘机械臂的移动次数**。

### 帕洛阿尔托的新局：磁盘转得飞快，怎么在桌下接住它？

当 McCreight 走进施乐 PARC 时，摆在他面前的，却是一道方向完全相反的磁盘难题。

在帕洛阿尔托，团队试图摆脱大型机分时共享终端，为每位研究人员配备一台拥有独立屏幕与算力的个人工作站。Butler Lampson 在 1972 年 12 月撰写的内部备忘录《Why Alto?》中论证，必须制造数十台真实的机器构建分布式网络，才能检验这套个人计算系统。

要让单台工作站独立运行软件并存放文件，本地持久化存储不可或缺。

![Xerox Alto 工作站与桌下机箱](https://upload.wikimedia.org/wikipedia/commons/thumb/5/5e/Xerox_Alto_mit_Rechner.JPG/1280px-Xerox_Alto_mit_Rechner.JPG)

*Xerox Alto 个人工作站全套设备与桌下机箱。机箱上方舱门即为 Diablo 磁盘驱动器插槽。Photo by Joho345, Public Domain, via* [*Wikimedia Commons*](https://commons.wikimedia.org/wiki/File:Xerox%5FAlto%5Fmit%5FRechner.JPG?ref=huizhou92.com)*.*

团队选用了加州 Diablo Systems 公司生产的 Series 30 Model 31 单盘盒式硬盘机（容量 2.5 MB）。这种驱动器体积小，能直接塞入实验桌下的机箱，但它本身是一台纯粹的机械读写装置：**驱动器机身内部没有任何板载扇区数据缓存（RAM）**。

![IBM 2315 盒式单盘盒](https://upload.wikimedia.org/wikipedia/commons/thumb/0/03/IBM_2315_disk_cartridge.agr.jpg/1280px-IBM_2315_disk_cartridge.agr.jpg)

*IBM 2315 单盘盒式磁盘（Diablo Series 30 Model 31 采用同规格 14 英寸单盘盒，容量约 2.5 MB）。Photo by ArnoldReinhold, CC BY-SA 3.0, via* [*Wikimedia Commons*](https://commons.wikimedia.org/wiki/File:IBM%5F2315%5Fdisk%5Fcartridge.agr.jpg?ref=huizhou92.com)*.*

在波音，问题是机械臂太慢；而在 Alto 面前，问题变成了**旋转的磁盘转得飞快，数据流正汹涌扑来**。

Diablo 磁盘以恒定速率将数据位流送入总线，而控制器硬件只有一个**单字缓冲区（Single-word buffer）**。

约每 10 微秒，就会有一个 16 位字涌入缓冲区。如果计算机在接下来的 10 微秒内没有把这个字取走，下一个字就会直接冲垮缓冲区，导致整个扇区数据报废。

在传统大型机上，解决这种时序问题通常依靠包含数百块芯片、造价昂贵的独立硬件控制器与专用 DMA 通道。但 Alto 作为摆放在桌下的个人机器，机箱空间与制造成本都不允许塞进这样一台庞然大物。

McCreight 与 Lampson 采取了软硬协同的设计路线：**尽量省去专用硬件电路，把控制状态机交给中央处理器（Micromachine）通过微码执行**。

![Butler Lampson](https://upload.wikimedia.org/wikipedia/commons/thumb/7/77/Professional_Developers_Conference_2009_Technical_Leaders_Panel_6_%28cropped%29.jpg/1280px-Professional_Developers_Conference_2009_Technical_Leaders_Panel_6_%28cropped%29.jpg)

*Butler Lampson（1992 年图灵奖得主）。在施乐 PARC，他与 Edward McCreight 共同完成了 Alto 磁盘控制器微码与文件系统的软硬件协同设计。Photo by Microsoft PDC, CC BY 2.0, via* [*Wikimedia Commons*](https://commons.wikimedia.org/wiki/File:Professional%5FDevelopers%5FConference%5F2009%5FTechnical%5FLeaders%5FPanel%5F6%5F%28cropped%29.jpg?ref=huizhou92.com)*.*

最终实现的 Alto 磁盘控制器专用硬件极其精简，整块电路板仅使用了**约 55 块中规模集成（MSI）TTL 芯片**与 4 个专用寄存器；而控制状态机的大部分工作，由控制存储器中约 150 条微指令组成的两个微码任务分担：

- **数据任务（Disk Data Task）**：分配最高固定优先级。在连续数据传输期间，数据任务约每 10 微秒被硬件唤醒一次；它在最多 1.7 微秒内将一个字在主存与单字缓冲之间搬运完毕，随后撤销本次请求并让出处理器，让显示、网络或普通仿真任务继续运行。
- **扇区任务（Disk Sector Task）**：分配较低优先级。仅在磁头经过扇区物理缝隙（每隔约 3 毫秒）时执行一次，负责检查设备状态、发起寻道指令，并为下一个扇区的数据任务准备参数。

### 搬得及时，还要写对位置

把数据在 10 微秒内传输完，还只解决了问题的一半。在个人工作站上，硬件还必须面对另一个隐患：**如何防止错误写入破坏磁盘数据？**

盒式磁盘驱动器的机械寻道存在物理偏差，程序跑飞也可能给出错误地址。在没有防范机制的情况下，错误的磁头定位会引发“野写”（Wild Write），直接覆盖其他无辜文件的扇区。

McCreight 与 Lampson 在控制器硬件与文件系统之间设计了一套防御性标签机制。他们把每个物理扇区划分为三个独立的记录段：

1. **Header（头标）**：记录柱面号、磁道号与扇区编号；
2. **Label（标签）**：记录文件唯一 ID、页码，以及指向前后两页的双向物理指针；
3. **Data（数据）**：256 个 16 位字的数据载荷。

控制器硬件支持对各段独立执行读、写或比较操作。**软件在写入数据前，通常会请求控制器先对 Header 和 Label 进行比较校验**。只有当硬件确认磁头确实停留在预期的物理柱面，且目标扇区的文件 ID 与页码完全吻合时，微码才允许进入数据写入阶段；一旦比对不符，写入立即中止。

这套扇区 Label 结构构成了 Alto 文件系统的容错基础。即使顶层目录遭到破坏，系统恢复工具 Scavenger 也能全盘扫描各扇区中尚完好的 Label 链表，尝试拼合各文件的数据页并重建目录拓扑。

这套用微码替代专用芯片的方案带来了显著的硬件成本节省，但也伴随着明确的性能代价。施乐 PARC 报告 CSL-79-11 明确记录：**在磁盘连续数据传输期间，最多占用约 20% 的微处理器时间**。Alto 用五分之一的处理器算力，换取了桌下控制器硬件的极度精简。

### 两种截然不同的工程取舍

从西雅图到帕洛阿尔托，Edward McCreight 的两段经历展示了系统工程师面对同一种旋转磁介质时的不同解题路径。

两项工作没有直接的设计衍生关系，而是分别针对不同层级的物理瓶颈给出的工程折衷：

在波音的算法层，约束是机械臂数十毫秒的寻道开销，解题的重点在于**通过多路平衡树减少需要读取的页面数量**，把机械等待降到最低；

在施乐 PARC 的系统层，约束包括单字缓冲每 10 微秒的数据流时限与机械漂移风险；解题的重点在于**用处理器时间换取更少的控制电路**，并通过扇区校验筑牢防野写的可靠性防线。

当物理世界对计算机施加限制时，真正的系统工程师并不受限于“纯软件”或“纯硬件”的专业分工，而是在最恰当的抽象层次上，给出兼顾性能、成本与可靠性的务实答案。

### 参考文献：

- Rudolf Bayer, Edward M. McCreight, *Organization and Maintenance of Large Ordered Indices*, *Acta Informatica* 1, 173–189 (1972).
- Rudolf Bayer, *Memoiren*, Technical University of Munich (TUM), 2014.
- C. P. Thacker, E. M. McCreight, B. W. Lampson, R. F. Sproull, D. R. Boggs, *Alto: A Personal Computer*, Technical Report CSL-79-11, Xerox PARC, Aug 7, 1979.
- Diana Merry, Ed McCreight, Bob Sproull, *Alto: A Personal Computer System Hardware Manual*, Xerox PARC, Aug 1976 revision.
- Butler W. Lampson, *Why Alto?*, Xerox PARC Internal Memo, Dec 1972.
- Computer History Museum, Accession 102739347-05-0001-acc.
- 前篇回顾：《[几乎每个数据库都在用的那棵树，出自一家一年少了 46,000 名员工的飞机公司](https://huizhou92.com/ji-hu-mei-ge-shu-ju-ku-du-zai-yong-de-na-ke-shu-chu-zi-yi-jia-yi-nian-shao-liao-46-000-ming-yuan-gong-de-fei-ji-gong-si/)》（[微信公众号版](https://mp.weixin.qq.com/s/pf0Wczd%5Fz3ImhNRnKcsvPA?ref=huizhou92.com) / [Ghost 博客版](https://huizhou92.com/ji-hu-mei-ge-shu-ju-ku-du-zai-yong-de-na-ke-shu-chu-zi-yi-jia-yi-nian-shao-liao-46-000-ming-yuan-gong-de-fei-ji-gong-si/)）