> ## 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.

# The Tree Behind Nearly Every Database Came from Boeing as It Cut 46,000 Workers
- URL: https://huizhou92.com/b-tree-boeing-origin-en/
- Published: 2026-11-16T10:02:26.000Z
- Updated: 2026-11-16T10:02:26.000Z
- Description: In 1969, Rudolf Bayer and Edward McCreight created the B-tree at Boeing, balancing 50 ms disk seeks against 90 μs data streaming.
- Author: huizhou92
- Tags: #lang-en, Computer History, Software Engineering, Databases, Technology, Programming

*Early disk-based index concept in an aerospace laboratory. Illustration, AI-generated.*

The indexes powering modern databases and file systems almost universally rely on B-trees or their B+ tree variants. This cornerstone data structure of computer science did not emerge from Bell Labs or a university department. It came from the Boeing Scientific Research Laboratories (BSRL).

In 1966, Rudolf Bayer completed his doctorate in mathematics at the University of Illinois and joined Boeing. According to his [2014 memoir](https://db.in.tum.de/people/sites/bayer/Memoiren-Bayer.pdf?ref=huizhou92.com), the reasons were direct and practical. Boeing was establishing a dedicated computer science department, and Bayer became its first formally trained computer scientist. The company promised to help convert his J-1 student visa into a green card, offered the highest salary among competing offers, and placed the laboratory in Seattle, his dream city.

Boeing had founded BSRL in January 1958\. Its [1958 annual report](https://archive.org/details/boeingairplanecompanyannualreports) defined the lab's mission as conducting basic research across any scientific discipline that might "contribute to the extension of knowledge in the realm of flight." At the time, Boeing operated on an immense scale, employing an average of 120,500 people throughout 1969\. By 1970, hit by an aerospace recession and shifting contracts, the company shed **46,000 employees** from its payroll within twelve months, ending the year at 62,700.

The idea for the B-tree took shape on the eve of that historic retrenchment.

### A Blackboard and a 7.25 MB Disk Drive

In the autumn of 1969, thirty-year-old Bayer walked into the office of his colleague Edward McCreight and sketched an idea for a new file index on a blackboard. McCreight had recently earned his doctorate in computer science from Carnegie Mellon University. The two quickly divided the work: Bayer took charge of algorithm formalization and mathematical complexity analysis, while McCreight handled programming and benchmark measurements.

As Bayer later recalled, the practical backdrop prompting this problem was managing parts for the Boeing 747\. The sheer volume of manufacturing records and alloy specifications for thousands of components overwhelmed the computing machinery of the day. Neither researcher foresaw how far the idea would travel, but both immediately recognized its value.

Their testbed was an IBM System/360 Model 44 mainframe wired to an IBM 2311 removable disk drive with a capacity of 7.25 MB. The mainframe's core memory was capped at 256 KB. In typical benchmark runs handling around 10,000 index entries, the paging buffer inside core memory could hold only about 1,250 entries.

With large ordered indexes unable to fit into memory, every search had to pull repeatedly from spinning magnetic platters.

![IBM 2311 Disk Drive](https://upload.wikimedia.org/wikipedia/commons/thumb/f/ff/IBM_2311_Disk_Drive.agr.jpg/1280px-IBM_2311_Disk_Drive.agr.jpg)

*IBM 2311 disk drive (same model). 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)*.*

![IBM System/360 Model 44](https://upload.wikimedia.org/wikipedia/commons/thumb/1/1f/IBM_360-44.1.jpg/1280px-IBM_360-44.1.jpg)

*IBM System/360 Model 44 mainframe console (same model, maximum core memory 256 KB). Photo by Living Computers Museum+Labs, CC BY-SA 4.0, via* [*Wikimedia Commons*](https://commons.wikimedia.org/wiki/File:IBM%5F360-44.1.jpg?ref=huizhou92.com)*.*

### 50-Millisecond Seeks and the Binary Tree Bottleneck

In main memory, balanced binary search trees like AVL trees work well. Each node stores a key with two pointers branching left and right. Moved to rotating disk drives, however, this architecture crashed straight into physical reality.

According to IBM's [1969 system manual](https://bitsavers.org/pdf/ibm/360/GA22-6810-10%5F360%5FOverview%5FAug69.pdf?ref=huizhou92.com), the IBM 2311 streamed sequential data at 156,000 bytes per second. With each index entry occupying 14 bytes, transferring a single entry sequentially took a theoretical 89.7 microseconds.

The killer bottleneck lay in mechanical positioning. The drive arm had to seek the cylinder, and the head had to wait for the platter to rotate beneath it. Under the paper's benchmark parameters, the average access mechanism delay for an IBM 2311 was **50 milliseconds** (50,000 microseconds). Moving the physical arm once took over 500 times longer than streaming a record off the track.

If a binary tree organized one million entries, its depth stretched across 20 levels. If nodes scattered across different tracks, traversing each pointer meant triggering another mechanical seek. Looking up a single key demanded 20 separate disk reads—forcing the user to wait a full second just for physical arm positioning. On spinning rust governed by milliseconds, an index had to minimize disk trips at all costs.

### Multiway Branching and the Engineering Choice of K = 60

Bayer and McCreight tackled this by squashing the tree downward to flatten its height.

Instead of storing one key per node, they clustered multiple ordered entries into a single disk page. The structure became a multiway balanced tree rather than a binary one. Each node held up to $2k$ entries, branching out into as many as $2k + 1$ child pointers.

To search, the operating system performed a single seek to load an entire page into memory. The CPU then ran a fast binary search in core memory to determine which child page to read next. The algorithm strictly guaranteed every leaf node remained at the exact same depth, preventing the skew that plagued unbalanced trees.

This wide branching created immense fanout. According to the paper's capacity tables, when each page held 120 entries (branching 121 ways), a tree just 3 levels deep stored up to **1,771,560 entries**. A lookup that once required 20 mechanical seeks in a binary tree dropped to at most 3 disk reads, taking about 150 milliseconds.

Yet a disk page could not grow indefinitely. If $k$ was too small, the tree grew taller and paid repetitive 50-millisecond seek penalties. If $k$ grew too large, reading huge pages wasted time streaming bulk data into tight memory. Optimal page size hinged on balancing fixed seek overhead $\\alpha$ (about 50 ms) against incremental transfer cost $\\beta$ (about 90 $\\mu$s).

The authors provided two figures: an acceptable theoretical range of $64 < k < 128$ (corresponding to 128 to 256 entries per page), and an analytical prediction pointing to an optimal page around 120 entries ($k \\approx 60$). When coding their benchmark suite, the researchers settled on a clean integer, explaining their choice with complete pragmatism:

> "For reasons of programming convenience we chose k = 60 resulting in a page size of 120 entries."

Each index entry consumed 14 bytes. McCreight coded the benchmark suite and ran 10 measurement passes, evaluating configurations of 25, 120, and 250 entries per page. In July 1970, Boeing internal research report D1-82-0989 was officially complete.

### Publication, Journal Rejection, and the Boeing Bust

The research navigated internal circulation, conference presentation, and eventual journal publication. Following the July 1970 internal report, *Organization and Maintenance of Large Ordered Indices*, the authors presented their findings at the [ACM SIGFIDET Workshop](https://doi.org/10.1145/1734663.1734671?ref=huizhou92.com) at Rice University in Houston on November 15–16, 1970\. The paper appeared in the workshop proceedings, marking the public debut of B-trees outside Boeing. This conference debut explains why database literature often dates the invention to 1970.

Getting the work into a major journal proved harder. Bayer recalled when they submitted the manuscript to the *Communications of the ACM* (CACM), the referee rejected it. The reviewer argued similar techniques already existed and asserted hash tables were far superior. Bayer later reflected this was "probably one of the greatest misjudgments in computer science." Around the same time, Sperry Univac and Control Data Corporation were indeed independently developing comparable multiway tree structures. In September 1971, the authors sent the manuscript to the newly founded Springer journal [*Acta Informatica*](https://doi.org/10.1007/BF00288683?ref=huizhou92.com), where it was published in 1972 as the canonical archival reference.

As the paper circulated, Boeing sank into a profound crisis. Massive capital commitments to the 747 program, cancelled military contracts, and an airline downturn starved the company of cash. Near the Seattle-Tacoma airport, two real estate agents put up a billboard capturing the civic mood: "Will the last person leaving SEATTLE — Turn out the lights."

![1971 Seattle "Turn Out the Lights" Billboard](https://oohtoday.com/wp-content/uploads/2018/05/turn-off-lights-bothh-men-close-up.jpg)

*On April 16, 1971, real estate agents Bob McDonald and Jim Youngren put up their famous billboard near the Seattle-Tacoma airport. Photo courtesy of The Seattle Times / HistoryLink (Essay 1287), via* [*OOH Today*](https://oohtoday.com/1971-real-estate-agents-will-the-last-person/?ref=huizhou92.com)*.*

According to Boeing's [1970 annual report](https://archive.org/details/boeingairplanecompanyannualreports), company employment fell by **46,000 workers** across those twelve months, leaving 62,700 on the nationwide payroll by year's end. Facing severe cost pressures, management redirected the research laboratory toward short-term engineering support. Basic research lost its mandate.

The lab's researchers scattered. Bayer left in 1970 for a faculty appointment at Purdue University before moving to the Technical University of Munich in June 1972\. McCreight departed shortly after to join the Xerox Palo Alto Research Center (PARC).

### Naming Over Lunch and Half a Century of Echoes

In June 1979, Douglas Comer published his landmark survey, [*The Ubiquitous B-Tree*](https://doi.org/10.1145/356770.356776?ref=huizhou92.com), in *ACM Computing Surveys*. In the opening sentence, he observed the structure possessed a short but important history.

Rumors long circulated the "B" stood for Boeing, balanced, or Bayer himself. In 2012, [McCreight clarified](https://www.mccreight.com/?ref=huizhou92.com) the name crystallized during a lunchtime discussion. They wanted a title that was short, easy to type, and memorable. "B" offered a quiet nod to Boeing without requiring corporate clearance, hinted at balance, and honored Bayer as the senior investigator. For reasons plain to American English speakers, "BM Tree" was out of the question. McCreight noted he could not recall any single meaning prevailing that day, adding Bayer was fond of saying: the more one ponders what the B might mean, the better one understands B-trees, and that is a good thing.

Over half a century later, B-trees and their variants remain fundamental across storage engineering. From [SQLite](https://www.sqlite.org/fileformat2.html?ref=huizhou92.com) storing tables and indexes, to [PostgreSQL](https://www.postgresql.org/docs/16/btree.html?ref=huizhou92.com) using B-trees as its default index engine; from [MySQL InnoDB](https://dev.mysql.com/doc/refman/8.4/en/innodb-index-types.html?ref=huizhou92.com) structuring clustered and secondary indexes, to Linux [Btrfs](https://btrfs.readthedocs.io/?ref=huizhou92.com) and Apple [APFS](https://developer.apple.com/support/apple-file-system/?ref=huizhou92.com) organizing file metadata, mainstream systems continue to rely on this multiway architecture.

In that 1970 testbed, packing up to 120 index entries of 14 bytes each produced an effective payload of about 1,680 bytes per page. Today's database engines align their physical pages with modern storage blocks—commonly 4 KB, 8 KB, or 16 KB. Even as storage media evolved from disk drives moving 156 KB per second to solid-state drives moving gigabytes, the mechanical chasm between random seeks and sequential throughput endures. The multiway balanced layout sketched on that Seattle blackboard still dictates how software bridges the boundary between memory and disk.

### References

- Rudolf Bayer and 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\. [ACM Digital Library](https://doi.org/10.1145/1734663.1734671?ref=huizhou92.com)
- Rudolf Bayer and Edward M. McCreight, *Organization and Maintenance of Large Ordered Indexes*, *Acta Informatica* 1, 173–189 (1972). [Springer Link](https://doi.org/10.1007/BF00288683?ref=huizhou92.com)
- Rudolf Bayer, *Memoiren*, Technical University of Munich (TUM), 2014\. [TUM Archive PDF](https://db.in.tum.de/people/sites/bayer/Memoiren-Bayer.pdf?ref=huizhou92.com)
- Douglas Comer, *The Ubiquitous B-Tree*, ACM Computing Surveys 11(2), June 1979, pp. 121–137\. [ACM Digital Library](https://doi.org/10.1145/356770.356776?ref=huizhou92.com)
- Boeing Airplane Company Annual Reports (1958, 1968–1972). [Internet Archive](https://archive.org/details/boeingairplanecompanyannualreports)
- IBM Corporation, *IBM System/360 System Summary*, 11th Edition, August 1969 (GA22-6810-10). [Bitsavers Archive](https://bitsavers.org/pdf/ibm/360/GA22-6810-10%5F360%5FOverview%5FAug69.pdf?ref=huizhou92.com)
- 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](https://www.sqlite.org/fileformat2.html?ref=huizhou92.com)