---
title: "Organization and Maintenance of Large Ordered Indices"
description: "The original B-tree paper asks how an index can keep searches and updates cheap when it is too large for memory and every disk access is expensive. Read it to see why one page should hold many sorted separators, how a full page splits around its median, and how equal leaf depth keeps a changing index shallow."
canonical_url: "https://fanout.sh/daily/2026-09-08-btree-ordered-index"
md_url: "https://fanout.sh/daily/2026-09-08-btree-ordered-index.md"
last_updated: "2026-09-08"
access: "public"
---

# Organization and Maintenance of Large Ordered Indices

The original B-tree paper asks how an index can keep searches and updates cheap when it is too large for memory and every disk access is expensive. Read it to see why one page should hold many sorted separators, how a full page splits around its median, and how equal leaf depth keeps a changing index shallow.

## Paper details

- Authors: Rudolf Bayer and Edward M. McCreight

- Venue: Acta Informatica 1972

- Track: Systems

- Difficulty: Easy

- Reading time: 30 min

- Original paper: https://doi.org/10.1007/BF00288683

## What you will learn

- Why matching one tree node to one disk-transfer page turns many in-page comparisons into a single expensive storage access.

- How sorted separators route a search and how promoting the median of a full page creates two siblings without breaking order or balance.

- Which occupancy, height, device-cost, workload, concurrency, and recovery limits separate the 1972 result from a complete modern database index.

## Continue exploring

[Explore B-trees in Fanout](https://fanout.sh/system/archive/b-tree): Connect Bayer and McCreight's page-shaped balanced tree to Fanout's practical B-tree guide, database indexing, page splits, storage engines, and later B+ tree designs.

---
This representation contains public Fanout content only. Protected Pro lessons, account data, billing, checkout, and pricing are not included.

Browse the public content map: https://fanout.sh/sitemap.md