Skip to content
Organization and Maintenance of Large Ordered Indices 4 min

Rudolf Bayer, Edward M. McCreight · Acta Informatica 1972

Organization and Maintenance of Large Ordered Indices

The 1970 paper that introduced the B-tree: wide pages, perfect balance, splits that push a key up. Insert keys and watch the pages split.

Read the original paper

Databases · Yellow Belt · Pro · 4 min read

Organization and Maintenance of Large Ordered Indices

Databases keep their data on disks, and disks are slow. A single read can cost as much as millions of ordinary computer steps. So a good index is not the one with the fewest comparisons. It is the one that touches the disk the fewest times.

In 1970 Rudolf Bayer and Edward McCreight, working at Boeing, described how to keep a large sorted index on a disk while keys are added and removed all the time. They named the structure a B-tree. More than fifty years later, the B-tree and its close relatives still sit under most relational databases and file systems.

A B-tree stores many keys in each page, so the tree is wide and very short. Pages are always at least half full, and every leaf is at the same depth. When a page overflows it splits in the middle and pushes one key up. So a search reads only a handful of pages, even for millions of keys.

A page is a block of the disk

A disk is read in blocks. Reading one key costs the same as reading a whole block, so the paper organizes the index into pages, one page per block. Each page holds many keys in sorted order, and a pointer sits between neighbors.

A B-tree page is one block read from disk. Its keys are in order, and a pointer sits on each side of every key. Following a pointer leads to the page that covers the keys in that gap.

The rules in the paper are short. A page holds between k and 2k keys, except the root, which may hold as few as one. A page that is not a leaf with j keys has j + 1 children. And every path from the root to a leaf has the same length. That last rule is the key one: the tree is always perfectly balanced.

Think of a dictionary's thumb tabs. You do not scan every word. You flip to the right letter, then the right page, then scan a short list. A B-tree is a thumb-tab index with the tabs themselves arranged in layers.

Keep reading with Pro

This paper is part of Pro. Pro and Architect open the full breakdown, with animated diagrams, interactive elements you can play with and a quiz. A few papers stay free to read in full.

Still to read

3 more sections, 2 more diagrams and 2 interactive elements to play with

  • Short because it is wide
  • Growing without losing balance
  • Why it is still everywhere

Found this breakdown useful?

Share it with someone else wrestling with this paper.

Discussion0

Join the Discussion

Sign in to leave comments, reply to others, or like insights.

Sign In to ScaleDojo

No comments yet. Be the first to start the thread!

Enjoyed this? Get more like it.

New paper breakdowns, levels, and one concept worth knowing, straight to your inbox.

No spam, ever. Unsubscribe in one click.

Enjoyed this content?

Your support keeps us creating free resources

We put a lot of hours into researching and writing these guides. If it helped you, consider buying us a coffee. Every bit goes toward keeping ScaleDojo's content free and growing.

$

One-time payment via Stripe. ScaleDojo account required.