Update-in-Place
Think of a B-Tree like a library where every book is perfectly alphabetized on the shelf at all times. When you want to find a book, you check the card catalog (the index), walk to the exact aisle and shelf, and pick it up. Finding anything is fast and predictable.
Adding a new book is harder. If the "S" shelf is already full, you can't just stack the book on the floor — you have to rearrange the entire shelf to make room. In database terms, this is called a Page Split: when a 4 KB page fills up, the database splits it into two half-full pages and updates the parent node to point to both. This requires multiple random writes.
Structure and Mechanics
A B-Tree organizes data as a balanced tree of fixed-size pages (typically 4 KB or 8 KB). Each page contains sorted keys and either pointers to child pages (internal nodes) or actual row data (leaf nodes).
[Root Page]
/ | \
[Page A] [Page B] [Page C]
id: 1-33 id: 34-66 id: 67-99
/ \ / \ / \
[Leaf] [Leaf] [Leaf] [Leaf] [Leaf] [Leaf]
(rows) (rows) (rows) (rows) (rows) (rows)
To update a single row (e.g., change a user's email address):
- Traverse the tree from root to leaf — typically 3–4 page reads for a table with millions of rows.
- Read the specific 4 KB leaf page containing that row into memory (buffer pool).
- Modify the 10-byte email field in memory.
- Write the entire 4 KB page back to the exact same location on disk.
Step 4 is the critical one: the write must go to a specific disk address. This is random I/O. The disk cannot batch this with other writes — it must seek to that location immediately.
Write-Ahead Log (WAL)
B-Trees use a Write-Ahead Log (WAL) to survive crashes. Before modifying any page, the database appends the intended change to a sequential log file. If the system crashes mid-write, the WAL is replayed on restart to restore consistency. This means every B-Tree write actually touches disk twice: once to the WAL (sequential) and once to the data page (random). The WAL is fast; the page write is the bottleneck.
Interviewers often ask: "Why does PostgreSQL have both a WAL and heap files? Isn't that redundant?" The answer is that they serve different purposes. The WAL provides crash recovery and replication — it's a sequential, append-only record of intent. The heap files are the actual data pages, organized for fast reads. The WAL is discarded after checkpoints; the heap files are permanent. A follow-up question is often: "What happens if a crash occurs between the WAL write and the page write?" — the answer is that on restart, PostgreSQL replays the WAL to redo the page write, which is why WAL entries must be written before the page modification (the "write-ahead" guarantee).
Key Point: B-Trees are optimized for fast reads at the cost of slow, random writes. Their read performance is excellent because data is always sorted and located at a predictable address. Their write performance degrades under high-concurrency insert/update workloads because every write requires a random I/O to a specific page location, plus potential page splits that cascade up the tree.