Organization and Maintenance of Large Ordered Indices

In one breath — the whole paper, compressed

Bayer and McCreight attack the problem of keeping an index for a dynamically changing random access file when the index is far too large for main store and must live on a disc or drum. Their answer is to make the unit of the tree equal to the unit of transfer: each node is a page holding between k and 2k index elements, so a node has between k+1 and 2k+1 sons and the tree is extremely shallow. The tree is kept perfectly balanced not by rotations but by growing from the bottom: a full page that receives one more entry splits at its median key, which is pushed into the father, and the only way the height ever increases is when the root itself splits. Deletion is the mirror image, using catenation of two adjacent brothers and, when they are too full to merge, an underflow that redistributes them evenly. Retrieval, insertion and deletion all cost a number of page accesses proportional to the height, which is bounded above by 1 + log base (k+1) of ((I+1)/2); storage utilization is at least 50% and, with the overflow optimization, measured at 86.7% on random insertions and over 99% on sequential ones.

Before this paper — the world it landed in

Before this paper, the balanced-tree literature the authors cite was about structures that live in core: Adelson-Velskii and Landis's AVL trees, Foster's AVL-based retrieval, Landauer's balanced tree, Sussenguth's tree structures for processing files. Those designs count node visits, which is the right cost model for core store and the wrong one for a moving-head disc, where a single access costs about 50 ms of wait time but the transfer that follows runs at roughly 90 microseconds per index element. A binary structure over a large index therefore pays tens of seeks for a single lookup, because each pointer chase is a separate device access. The competing practical answer was hash-coding, which the authors explicitly name: it is fast for point lookups but destroys the natural order of the keys and degrades badly when storage occupancy gets high. What was missing was an index that was cheap on a pseudo random access device, kept keys in order, and could absorb insertions and deletions indefinitely without a reorganization pass.

The problem — what was actually breaking

The index is so voluminous that only small parts of it fit in main store, so the bulk of it must live on a backup store whose access or wait time is long even though its data rate is high once transmission starts.
Because the underlying data file itself changes, the index must support economical insertion and deletion of index elements, not merely retrieval, and it must do so in place rather than by periodic rebuilding.
Structures that count individual node visits, like balanced binary trees, translate each level of the tree into a separate device access, which is exactly the operation that costs 50 ms and must therefore be minimized.
Hash-coded organizations give up the natural order of the keys, and that order is what makes finding predecessors and successors, sequential scans, and group retrievals of consecutive keys possible.
Storage must be requested and released as the file grows and contracts, with no congestion problem and no degradation of performance when occupancy of the backup store is very high.
The scheme must give bounds that hold at any time, not only on average after a rebuild, so that retrieval, insertion, and deletion each have a guaranteed cost proportional to the logarithm of the index size.

Core ideas — the contributions, and why they work

The page is the node

The index is stored in pages of fixed size capable of holding up to 2k index elements, and those pages are exactly the nodes of the tree. This single identification is the whole trick: the cost of visiting a node is one device access regardless of how many keys the node holds, so making the node as large as one transfer unit buys a fan-out of up to 2k+1 for the price of one seek. With k = 60, the value the authors chose, a tree of height 3 already indexes up to 1,771,560 keys, so a lookup in a very large index costs three page fetches. The structure is thus designed around a device parameter rather than around an abstract comparison count.

The B-tree class T(k,h)

A B-tree in the class T(k,h) is a directed tree in which every path from the root to any leaf has the same length h, every node except the root and the leaves has at least k+1 sons, the root is either a leaf or has at least two sons, and no node has more than 2k+1 sons. On top of this the index adds that every page holds between k and 2k keys, except the root which may hold between 1 and 2k, and that a non-leaf page with l keys has exactly l+1 sons. The invariant that all leaves sit at the same depth is what makes the cost of every retrieval identical, and the lower bound of k keys per page is what makes the height logarithmic and storage utilization at least 50%. The class is defined by inequalities, not by an exact shape, which is precisely why the structure can absorb arbitrary update sequences without ever being out of balance.

Growth from the leaves upward

Balance is maintained without any rotation or rebalancing walk. Splitting and catenation are initiated at the leaves only and propagate toward the root, and if the root node splits a new root is introduced, which is the only way the height of the tree can ever increase. Because a split adds a level at the top rather than lengthening one branch, every root-to-leaf path grows by exactly one at the same moment, so the same-height invariant is preserved for free. Contraction runs the same argument backwards, so the tree breathes in and out around the root instead of being reorganized.

Splitting at the median key

When an entry must go into a page that already holds 2k keys, the entry is inserted logically in main store to give a sequence of 2k+1 entries, the first k stay in the original page P, the last k go to a brand new brother page P', and the median entry x_(k+1) together with a pointer to P' is inserted into the father page Q. Splitting at the median is what guarantees both halves end up with exactly k keys, so the k-key floor is never violated by a split. The insertion into Q may cause Q to split too, and so on up the path, but each level is touched at most once. The authors note explicitly that this process maps B-trees with parameter k into B-trees with parameter k and preserves the key-ordering conditions.

Deletion by catenation and underflow

Deleting a key that sits on a leaf is direct; deleting one that sits in an interior page requires replacing it with the smallest key of the subtree to its right, found by walking the p_0 pointers down to a leaf and taking that leaf's first key, which is then deleted from the leaf. The leaf may now hold fewer than k keys, and the fix is chosen by counting: if the leaf and an adjacent brother together hold at most 2k keys they are catenated into one page and the separating key is pulled down out of the father, which may in turn leave the father short and propagate the process upward. If together they hold more than 2k keys, the two are merged in main store and split again in the middle, an operation the authors call an underflow, and the authors point out that underflows do not propagate because the father's key count is unchanged. Deletion is therefore the exact inverse of insertion, with the same locality and the same termination argument.

Overflow instead of splitting

In the basic scheme utilization can sink to 50% because every page may hold only k keys, so the paper adds a second-chance rule for insertions. If the page to be inserted into is full but an adjacent brother is not, the key is inserted into the sequence and an underflow-style redistribution is performed between the two pages, so no split occurs at all; a page is split only if both adjacent brothers are full. In an index without deletions this raises worst-case storage utilization from 50% to about 66%, at the price of worse cost bounds, since a maximal insertion now costs 3h-2 fetches instead of h. This is the idea that later became the B*-tree, and the authors already observe that one could widen the neighbourhood beyond adjacent brothers to push the minimum occupancy higher still.

Choosing k from the device

The paper does not leave the page size as taste. It models the time to fetch or write a page as alpha + beta(2k+1) + gamma ln(vk+1), where alpha is the fixed cost per page such as average disc seek time plus CPU overhead, beta is the transfer time per entry, gamma covers the in-page binary search, and v between 1 and 2 is the average page occupancy factor. Multiplying by the height, which is approximately log base (vk+1) of (I+1), gives total time per transaction and yields a closed-form condition on the optimal k. With alpha = 50 ms and beta = 90 microseconds measured on an IBM 2311 disc, the table in Figure 8 makes 64 to 128 an acceptable range for k, and the authors chose k = 60, a page of 120 index elements, for programming convenience.

How it works — the mechanism, concretely

Page layout and the ordering invariants

A page P contains its keys in increasing order x_1 through x_l with k <= l <= 2k (the root may have 1 <= l <= 2k), together with l+1 son pointers p_0 through p_l; on leaf pages the pointers are undefined. The triple (x_i, alpha_i, p_i), or the pair (x_i, p_i) with the associated information omitted, is called an entry. Writing K(p_i) for the set of all keys in the maximal subtree rooted at the page p_i points to, the structure maintains three conditions at all times: every key in K(p_0) is less than x_1, every key in K(p_i) lies strictly between x_i and x_(i+1) for i from 1 to l-1, and every key in K(p_l) is greater than x_l. These are the invariants every algorithm in the paper must preserve, and they are what makes an in-page search enough to pick the correct son.

Retrieval

Retrieval starts at a pointer r to the root, which is undefined if the tree is empty, and walks down. At each page the algorithm scans the keys of P(p) for the search key y; if y equals some x_i the search succeeds, otherwise the ordering conditions identify the unique son pointer to follow and the algorithm descends. The paper notes that although the algorithm is logically a linear scan, a real implementation would use an efficient technique such as a binary search within the page, since the page holds up to 2k keys. A side effect matters for the next algorithm: the variable s is left pointing at the last page scanned, so insertion can start from the leaf without descending again. At most h pages are scanned and therefore fetched, so f_min = 1, f_max = h, and no page is ever written.

Insertion

To insert key y, run the retrieval algorithm. If y is found, the index already contains it. If s is undefined the tree was empty and a root page is created holding y. Otherwise, if the leaf P(s) is not full the entry (y, u) is simply inserted into it and one page is written. If P(s) is full, the split routine runs: median promotion pushes an entry into the father, and the split may cascade up the retrieval path, possibly creating a new root. Because the retrieval path holds h pages, the worst case writes 2h+1 pages (each of h pages becoming two, plus a new root) while still fetching only h, giving f_max = h and w_max = 2h+1, where h is the height of the old tree.

Deletion

Locate y with the retrieval algorithm. If y is on a leaf, delete it there. If not, retrieve pages down to a leaf along p_0 pointers, replace y by the first key on that leaf page, and delete that first key from the leaf, which reduces the problem to a leaf deletion in all cases. Then, if the leaf now has fewer than k keys, perform a catenation with an adjacent brother when their combined key count is at most 2k, or an underflow when it exceeds 2k. A catenation removes an entry from the father and can therefore cascade upward all the way to the root, while an underflow modifies the father without changing its key count and so stops immediately. Best case is f = h and w = 1; if y was not on a leaf and nothing restructures, f = h and w = 2; the worst case, where all but the first two pages of the retrieval path catenate, the son of the root underflows and the root is modified, gives f = 2h-1 and w = h+1.

The cost model and the paging area

The analysis assumes that any page whose content is examined or modified during a single operation is fetched exactly once and paged out exactly once, and the paper observes that a paging area holding h+1 pages in main store is sufficient to make this true. Costs are then counted as f, the number of pages fetched, and w, the number of pages written, with minimum and maximum values derived for each operation. The authors deliberately do not analyze more powerful paging schemes, such as keeping the root page permanently locked in main store, even though they used such schemes in their experiments, so the published bounds are conservative. For a pure insertion process, the number of splits building an index of I keys is bounded by n(I)-1 where n(I) <= I/k + 1, and each split writes at most two extra pages, giving an average of f_a = h fetches and fewer than 1 + 2/k writes per insertion.

The experimental harness

The algorithms were programmed and measured on an IBM 360/44 with a 2311 disc unit, with index elements of 14 eight-bit characters and indices generally around 10,000 elements. The implementation added a simple demand paging scheme using about 1250 index elements' worth of core, which distinguishes a virtual disc read, meaning a request that a page be available in core, from a physical disc read, which happens only when no copy is already in the paging area. Ten experiments were run, each specified by whether overflow on insertion is permitted, the number of index elements per page, and a transaction sequence against an initially empty index; each experiment is divided into phases and performance variables are recorded at the end of each. The reported measures are percentage storage utilization, average virtual and physical disc reads per transaction, average virtual and physical disc writes per insertion or deletion, and average transactions per second.

What the paper showed — measurements and proofs

The height of a page tree holding I keys is bounded on both sides: h is at least log base (2k+1) of (I+1) and at most 1 + log base (k+1) of ((I+1)/2) for I >= 1, with h = 0 for the empty index; these bounds are called sharp, so retrieval cost is logarithmic by construction and not by assumption.
With the chosen k = 60 (120 entries per page), Figure 9 tabulates the reach of each height: height 1 holds 1 to 120 keys, height 2 holds 121 to 14,640, height 3 holds 7,441 to 1,771,560, and height 4 holds 453,961 to 214,358,880, so million-key indices are three or four page fetches deep.
Update costs are bounded per operation: insertion needs f_min = h fetches and w_min = 1 write, worst case f_max = h and w_max = 2h+1; deletion needs at best f = h and w = 1, worst case f_max = 2h-1 and w_max = h+1; for a pure insertion process the average is f_a = h with w_a < 1 + 2/k, and for a pure deletion process f_a < h + 1 + 1/k with w_a < 4 + 2/k.
Mixed workloads are shown to be genuinely worse: alternately deleting and inserting key 9 between the trees of Figures 2 and 5 forces the maximum cost on every single operation, yet the paper bounds this interference at a factor of at most 3 relative to pure insertion or pure deletion.
The overflow optimization is measured, not just argued: with 120 elements per page and 5,000 uniformly random insertions, storage utilization was 67.1% without overflow (E5) and 86.7% with it (E6); key-sequential insertion of 10,000 elements reached 99.2% (E2) and of 100,000 elements 99.8% (E10), settling to 82.1% after subsequent random insertions, deletions and retrievals.
End-to-end throughput on an IBM 360/44 with a 2311 disc (about 50 ms average access delay, about 90 microseconds transfer per index element): an index of 15,000 keys was maintained at an average of 9 retrievals, insertions and deletions per second and one of 100,000 keys at at least 4 per second, and the analysis projects at least 2 transactions per second for an index of 1,500,000 keys.

Limits and trade-offs — conceded and discovered

Conceded by the paper: the worst-case bounds on insertion and deletion are sharp but very far apart, and are assumed rarely except in pathological examples, so they are a poor guide to real cost. The authors retreat to average-case analysis, but only under the artificial assumptions of a pure insertion process or a pure deletion process.
Conceded by the paper: those averages stop holding once insertions and deletions are mixed, as the alternating key-9 example demonstrates, and the authors state plainly that it is an open question how important this interference is in any actual applications and how relevant their worst-case analysis is.
Conceded by the paper: overflow lifts worst-case storage utilization only to about 66%, and only for an index without deletions; once deletions occur, utilization may again be as low as 50%. Overflow also makes the derivable cost bounds worse, raising maximal insertion fetches from h to 3h-2, and it is easy to construct examples in which every insertion causes an overflow.
Not addressed at all: concurrency and recovery. The algorithms assume one transaction at a time, and a split propagating to the root would have to exclude every other reader; concurrent B-tree access was only solved later by Bayer and Schkolnick's locking protocols (1977) and Lehman and Yao's B-link trees (1981), which add right-links so a reader can follow a page that has just split.
Exposed by later work: this design stores associated information in interior pages as well as leaves, which reduces fan-out and makes an ordered scan hop between levels. The B+-tree variant, which pushes all index elements to the leaves and chains the leaves together, is what production systems actually implemented. Later still, the random-insert behaviour of B-trees, which leaves pages roughly half to two-thirds full and scattered across the device, motivated write-optimized alternatives such as the LSM-tree.

What it became — the systems that inherited it

The B-tree became the default on-disc index structure of the entire industry, to the point that Comer's 1979 survey could simply title itself The Ubiquitous B-Tree. IBM's VSAM and System R, and after them DB2, Oracle, Informix and essentially every SQL engine, used B-tree family indexes as the primary access method; PostgreSQL's nbtree implements Lehman and Yao's concurrent B-link variant, MySQL InnoDB stores every table as a clustered B+-tree, and SQLite, Berkeley DB and LMDB are B-tree engines end to end. File systems inherited it just as thoroughly: NTFS, HFS+, XFS, ext4's HTree directories, Btrfs and ReiserFS all index with B-tree variants. Two refinements in this very paper became named structures of their own, with the overflow rule turning into Knuth's B*-tree and the leaf-only, leaf-chained arrangement into the B+-tree that almost everyone means when they say B-tree today. The cost model here, in which the node is sized to the device's transfer unit and the metric is device accesses rather than comparisons, is the template for every later external-memory index, from cache-oblivious B-trees to the write-optimized B-epsilon trees behind TokuDB. Its main modern rival, the LSM-tree of O'Neil et al. (1996) and its descendants LevelDB, RocksDB and Cassandra, is best understood as the deliberate inverse trade: sacrificing the B-tree's in-place update and read simplicity to buy sequential write throughput.

In the paper’s words — verbatim

“Storage utilization is at least 50% but generally much higher. The pages of the index are organized in a special data-structure, so-called B-trees.”

Abstract

“The splitting and catenation processes are initiated at the leaves only and propagate toward the root. If the root node splits, a new root must be introduced, and this is the only way in which the height of the tree can increase.”

§1

“Thus a page will be split only if both adjacent brothers are full, otherwise an overflow occurs.”

§8

Vocabulary — as this paper uses it

Index element: A pair (x, alpha) of fixed-size, physically adjacent data items: a key x that identifies a unique element in the index, and associated information alpha, typically a pointer to a record or collection of records in the random access file. The paper treats alpha as opaque.
Page: A fixed-size block capable of holding up to 2k keys, which is simultaneously the unit of information transferred between main store and backup store and a node of the tree. Pages need only be partially filled, and every page except the root holds at least k keys.
Pseudo random access device: The class of backup stores the paper targets: fixed and moving head discs, drums, and data cells, which have a rather long access or wait time, as opposed to a true random access device like core store, but a rather high data rate once transmission of physically sequential data has begun.
B-tree, class T(k,h): A directed tree that is either empty (h = 0) or satisfies three conditions: every path from root to leaf has the same length h, every node other than the root and leaves has at least k+1 sons, the root is a leaf or has at least two sons, and no node has more than 2k+1 sons. The classes for different parameters need not be disjoint.
Entry: The triple (x_i, alpha_i, p_i) stored inside a page, or the pair (x_i, p_i) when the associated information is omitted. It couples a key with the pointer to the son whose subtree holds exactly the keys lying between x_i and x_(i+1).
Splitting: The operation applied when an entry must be inserted into a page that already holds 2k keys: the 2k+1 entries are divided so the first k stay in P and the last k move to a new brother page P', and the median entry with a pointer to P' is inserted into the father. Splitting is initiated at leaves and may propagate up to the root.
Catenation: The merging of two adjacent brothers, meaning two pages with the same father pointed to by adjacent pointers in it, when together they hold no more than 2k keys. The separating key in the father is pulled down into the merged page, which may leave the father with fewer than k keys and propagate the process toward the root.
Underflow: The alternative to catenation when two adjacent brothers together hold more than 2k keys: the pages are catenated in main store into one oversized page and then split in the middle, so the keys are equally distributed. Underflows do not propagate, because the father is modified but its key count is unchanged.
Overflow: The insertion-time counterpart of underflow: if a key must go into a full page but an adjacent brother is not full, the key is inserted and the two pages are redistributed instead of split. A page is therefore split only if both adjacent brothers are full, which raises worst-case utilization in an insertion-only index to about 66%.

On the timeline — where this sits in the story

Year1970–1972

MilestoneB-tree

Problem solvedSequential and hash-based indexes could not support efficient range queries, ordered traversals, and dynamic insertions on disk storage.

How it solved itB-trees organized keys in balanced, fan-out-optimized tree nodes that minimized disk seeks for point lookups and range scans.

Why it matteredBecame the dominant on-disk index structure for nearly every relational database, file system, and storage engine for decades.

DDIACh. 4: Storage & Retrieval

View on the timeline