B-Tree/B+Tree Storage: Read Locality, In-Place Updates, and Page Management

Learning outcomes

AtlasMart's order index must answer point lookups and ordered date/customer ranges while updates arrive continuously. A B+Tree-like engine stores ordered keys in fixed-size pages; the performance story therefore depends on page occupancy, traversal depth, caching, splits, and physical write behavior rather than the abstract statement “B-trees are good for reads.”

1. B-tree versus B+Tree: keep the abstraction precise

A B-tree is a balanced multiway search tree designed to keep height small by storing many keys/pointers per node. A B+Tree variant typically keeps record pointers/values in leaves and uses internal nodes primarily for routing; leaf pages are linked or otherwise traversable in key order. Database implementations differ in page layout, prefix compression, concurrency control, logging, vacuuming, and split policy, so this lesson uses a B+Tree-like mental model rather than asserting one universal page format.

Fan-out is the number of child pointers an internal page can address. Larger pages and compact separator keys can increase fan-out and reduce height, but page size also affects cache footprint and I/O granularity.

2. Ordered leaves create range locality

Suppose order IDs 10–80 live in three leaf pages. A point lookup descends through internal separators to one leaf. A range query 25..65 finds the starting leaf and then walks adjacent leaves until the upper bound is exceeded. That locality is fundamentally different from a hash partition/index where adjacent logical keys need not be physically or topologically adjacent.

3. Page splits are correctness-preserving structural work

When a target page lacks space, the engine may split it into two pages and update parent routing metadata. A split can turn one logical row insertion into several physical page writes plus WAL. This is one source of write amplification: physical bytes written divided by logical data changed. The exact ratio depends on page size, WAL format, copy-on-write/in-place behavior, indexes, checksums, and background maintenance.

Fill factor broadly means leaving free space so future inserts/updates have room. Its controls and semantics are product-specific. Lower occupancy can reduce some splits but increases space footprint and may reduce cache density. There is no portable “best 70%” value.

4. Wrong approach: optimize for 100% occupancy and ignore the insertion pattern

A static bulk load that packs every leaf may look space-efficient. If the next workload inserts inside those ranges, pages immediately split and write amplification spikes. Conversely, monotonic identifiers can concentrate structural change at the right edge even if distribution elsewhere is quiet. The failure is not corruption; it is an operational hot path—extra WAL/page writes, cache churn, and p99 latency.

Repair by measuring split rate, page density, hot ranges, write latency distributions, and range-query locality. If the product exposes fill-factor or key-layout controls, change them only with workload evidence and rollback criteria.

5. AtlasMart lab — leaf pages, separators, splits, and range scans

This simulator intentionally models only ordered leaf pages and root separators. It does not implement concurrency, WAL, sibling pointers, or a production B+Tree. The purpose is to make page-level consequences observable.

from bisect import insort

class LeafPages:
    def __init__(self, capacity=4):
        self.capacity = capacity
        self.pages = [[]]
        self.splits = 0
        self.page_rewrites = 0

    def locate(self, key):
        for i, page in enumerate(self.pages):
            if not page or key <= page[-1] or i == len(self.pages) - 1:
                return i
        return len(self.pages) - 1

    def insert(self, key):
        i = self.locate(key)
        insort(self.pages[i], key)
        self.page_rewrites += 1
        if len(self.pages[i]) > self.capacity:
            page = self.pages[i]
            mid = len(page) // 2
            left, right = page[:mid], page[mid:]
            self.pages[i:i+1] = [left, right]
            self.splits += 1
            self.page_rewrites += 2

    def separators(self):
        return [p[0] for p in self.pages[1:]]

    def range_scan(self, lo, hi):
        touched, rows = [], []
        for idx, page in enumerate(self.pages):
            if page and page[-1] >= lo and page[0] <= hi:
                touched.append(idx)
                rows.extend(k for k in page if lo <= k <= hi)
        return touched, rows

idx = LeafPages(capacity=4)
for key in [10, 20, 30, 40, 25, 50, 60, 70, 80]:
    idx.insert(key)
print("leaf pages:", idx.pages)
print("root separators:", idx.separators())
print("splits:", idx.splits, "page_rewrites:", idx.page_rewrites)
print("range 25..65:", idx.range_scan(25, 65))

right_edge = LeafPages(capacity=4)
for key in range(1, 17):
    right_edge.insert(key)
print("monotonic inserts -> pages:", right_edge.pages)
print("monotonic splits:", right_edge.splits)

# Illustrative spare-space example: three keys fit before the next insert.
spare = LeafPages(capacity=4)
for key in [10, 20, 30]:
    spare.insert(key)
spare.insert(25)
print("spare-capacity insert split?", spare.splits > 0, "pages:", spare.pages)

leaf pages: [[10, 20], [25, 30], [40, 50], [60, 70, 80]]
root separators: [25, 40, 60]
splits: 3 page_rewrites: 15
range 25..65: ([1, 2, 3], [25, 30, 40, 50, 60])
monotonic inserts -> pages: [[1, 2], [3, 4], [5, 6], [7, 8], [9, 10], [11, 12], [13, 14, 15, 16]]
monotonic splits: 6
spare-capacity insert split? False pages: [[10, 20, 25, 30]]

What the evidence shows

The 25..65 range touches only overlapping ordered pages; a split increases the page-rewrite counter; monotonic insertion repeatedly pressures the right edge; and spare capacity can absorb an insertion without splitting. The output does not prove the same split count or page layout for PostgreSQL, SQLite, InnoDB, SQL Server, or any other engine.

6. Production judgment

B/B+Tree families are attractive when ordered point/range access, mature transactional page management, and update-in-place semantics align with the workload. They can also perform extremely well on SSDs. But selection must include update/delete rates, secondary-index count, key distribution, cache size, page-split behavior, checkpoint/background-write patterns, and recovery semantics.

Bridge to Lesson 3: B+Trees repeatedly update page structures. Log-Structured Merge (LSM) designs take a different route: batch writes in memory, flush immutable sorted files, and move reorganization into background compaction.

Authoritative references

• PostgreSQL 18 — B-Tree indexes — current official example of B-tree index behavior and operator ordering
• SQLite — B-tree module — implementation-oriented B-tree documentation; SQLite-specific
• The Ubiquitous B-Tree — classic survey by Douglas Comer