B-Tree and B+Tree Index Internals: Page Splits, Fill Factor, Fan-Out and Why Your Database Index Is Fast

A table with a billion rows can answer a primary-key lookup by reading four or five pages. Not four or five thousand. Four or five. That single fact explains why the b-tree index has survived more than fifty years of hardware change, from tape-era disks to NVMe flash and terabytes of RAM, and why every mainstream relational engine still uses it as the default access path.

It matters now because the workloads around the index changed faster than the index did. Random UUID primary keys, write-heavy event tables and cloud storage billed per I/O all punish an index in ways that are invisible until the bill or the p99 latency arrives. Most “how indexes work” articles stop at “it’s a balanced tree”. The engineering lives in the details: how many keys fit on a page, what happens when a page fills, and how much empty space you choose to leave.

You will leave with the height arithmetic you can do on a napkin, a mental model of page splits, a runnable mini B+tree in Python, and a clear rule for when a log-structured merge tree beats a B-tree.

What this covers: history and terminology, B+tree vs B-tree, fan-out and height math, page splits and fill factor, sequential vs random keys and UUIDv7, composite and covering indexes, bloat and REINDEX, latch coupling and B-link concurrency, and B-tree vs LSM-tree amplification.

Context and Background

Rudolf Bayer and Edward McCreight introduced the B-tree in “Organization and Maintenance of Large Ordered Indexes”, published in Acta Informatica in 1972. Their goal was explicit: keep an ordered index on a device where reading a block is expensive, and keep the cost of lookups, inserts and deletes logarithmic with a very large base. The tree stays balanced because it grows at the root, not at the leaves. Every leaf is always the same distance from the root.

Seven years later Douglas Comer’s survey “The Ubiquitous B-Tree” in ACM Computing Surveys (1979) could already call the structure the de facto standard for file organisation. Comer also popularised the distinction that matters most in practice: the B+tree variant, in which all records or record pointers live in the leaves, internal nodes hold only separator keys, and leaves are chained so a range scan walks sideways instead of climbing back up. When engineers say “B-tree” about a database today, they almost always mean a B+tree.

The modern incumbents all follow that pattern with their own twists. PostgreSQL’s nbtree access method implements the Lehman and Yao high-concurrency algorithm, with right-links between siblings, and points leaf entries at heap tuples. MySQL’s InnoDB stores the table itself as a clustered B+tree keyed on the primary key, with 16KB pages by default; secondary indexes store the primary key as their row locator. SQLite uses B+tree-style “table b-trees” for rowid tables, with all data in the leaves, and “index b-trees” for indexes and WITHOUT ROWID tables.

The main challenger is the log-structured merge tree, which trades read cost for cheaper writes. We cover LSM internals in depth in our guide to LSM-tree compaction and write amplification in RocksDB; this post stays on the B-tree side and compares the two only at the end.

The angle here is deliberately numeric. My thesis is that almost every B-tree performance problem in production is a page-occupancy problem, not an algorithmic one. Height is bounded by fan-out, fan-out is bounded by entry size and fill, and fill is controlled by your key choice, your fill factor and your maintenance discipline. If you can reason about bytes per page, you can predict most of what an index will do. The PostgreSQL B-tree implementation documentation is the best primary source for how one engine manages that occupancy.

How a B-Tree Index Works: Pages, Fan-Out and Height

A B-tree index is a balanced tree of fixed-size pages, typically 8KB in PostgreSQL and 16KB in InnoDB. Internal pages hold sorted separator keys and child pointers; leaf pages hold the indexed keys plus row locators and are chained to their siblings. Because each page holds hundreds of entries, even billions of rows need only three to five levels.

Figure 1: Anatomy of a B+tree index. Searches descend from the root through separator keys to one leaf; range scans then follow sibling links across leaves.

Figure 1 shows the shape every engine shares. A root page fans out to internal pages, each holding separator keys that partition the key space. Leaves contain the actual index entries in sorted order and link left and right to their siblings. In PostgreSQL each leaf entry points to a heap tuple by its physical address; in InnoDB the clustered index leaves are the rows themselves, and secondary index leaves carry the primary key.

B+tree vs B-tree: why the “plus” won

The original 1972 design stored keys and their associated data in every node, internal or leaf. A lookup could stop early if it hit the key in an internal node. That sounds like an advantage, but it costs fan-out: every internal entry carries a payload, so fewer entries fit per page, so the tree gets taller for everyone.

The B+tree variant pushes all payloads to the leaves. Internal pages become pure routing tables that hold only separators and pointers, which raises fan-out dramatically. The leaf chain turns a range query into “descend once, then read sideways”, which is exactly what BETWEEN, ORDER BY ... LIMIT and merge joins need.

Property	Classic B-tree	B+tree
Where data or row pointers live	Every node	Leaves only
Internal page contents	Keys plus payloads plus children	Separator keys plus children
Fan-out at a given page size	Lower	Higher
Point lookup can stop early	Yes, at an internal match	No, always reaches a leaf
Range scan	In-order traversal, climbs back up	Leaf sibling chain
Typical use today	Textbooks, some in-memory structures	PostgreSQL nbtree, InnoDB, SQLite table b-trees

The early stop rarely matters, because the upper levels of a production index sit in memory anyway. Fan-out matters on every query, so the B+tree wins the b+tree vs b-tree argument in practice. One nuance: separators in a B+tree need not be real keys. They only have to divide the key space, which allows the suffix truncation trick discussed below.

Fan-out is a byte budget

Height is the number of pages a lookup must touch, and it depends almost entirely on fan-out, the number of children per internal page. Fan-out is arithmetic, not magic. Take PostgreSQL’s default 8KB page and work it through using the layout described in the source.

A page is 8,192 bytes. The page header takes 24 bytes and the B-tree “special space” at the end takes 16 bytes (left link, right link, level, flags and a cycle ID, per nbtree.h). That leaves about 8,152 usable bytes.
Every index tuple has an 8-byte header holding the 6-byte row pointer plus info bits, then the key, padded to an 8-byte boundary. Each tuple also needs a 4-byte line pointer in the page’s item array.
A bigint key therefore costs 8 + 8 = 16 bytes plus 4 for the line pointer: about 20 bytes per entry.

So a full leaf holds roughly 8,152 / 20 ≈ 407 bigint entries. A freshly built leaf filled to the default 90% fill factor holds about 366. Internal pages built by CREATE INDEX are packed to 70% (BTREE_NONLEAF_FILLFACTOR in the source), giving roughly 285 children each. These are estimates: the exact count shifts by a few entries because of the high key stored on every non-rightmost page.

Now index one billion rows:

Level	Pages (approx.)	Arithmetic
Leaves	2,732,000	1,000,000,000 / 366
Level 1 internal	9,590	2,732,000 / 285
Level 2 internal	34	9,590 / 285
Root	1	34 fits in one page

That is a four-level tree. The three upper levels total under 10,000 pages, about 75MB, which comfortably stays cached in shared buffers or the OS page cache. In steady state a point lookup costs one likely-uncached leaf read plus one heap read. The general formula is height ≈ 1 + ⌈log_F(N / L)⌉, where N is rows, L is entries per leaf and F is internal fan-out. Because log base 285 grows so slowly, a thousand-fold increase in rows adds only about one level.

Key width is the lever you actually control

Change the key and the arithmetic moves. A 16-byte uuid costs 8 + 16 + 4 = 28 bytes per entry, so a 90%-full leaf holds about 262 entries instead of 366. A 40-byte text key costs about 52 bytes and drops a leaf to roughly 140 entries. The tree may still be four levels deep, but the leaf level grows proportionally: about 40% more leaf pages for UUID than for bigint, and more than 2.5 times as many for the text key. Every extra leaf page is more cache pressure, more WAL during splits and more I/O for range scans.

PostgreSQL also caps the size of a single entry. The BTMaxItemSize macro reserves room for at least three items per page, which works out to 2,704 bytes on an 8KB page. Try to index a longer value and the insert fails. That is a hint that a hash or expression index on a digest is a better tool.

InnoDB flips part of the picture because its clustered index stores full rows in the leaves. With 16KB pages and rows around 200 bytes including overhead, a leaf holds on the order of 70 rows (illustrative estimate; real counts depend on row format and variable-length columns). Internal pages hold only the primary key plus a child page number, so fan-out stays high, typically in the high hundreds for a BIGINT key. The consequence is that every InnoDB secondary index entry embeds the primary key, so a wide primary key inflates every secondary index on the table.

Page Splits, Fill Factor and Key Order: A Walk-Through

Fan-out explains why b-tree index lookups are cheap. Page splits explain why writes sometimes are not. This section walks through what an insert actually does, why key order decides how full your pages end up, and how the fill factor knob trades space for future insert headroom.

Anatomy of a page split

An insert descends to the correct leaf exactly like a lookup. If the leaf has free space, the engine writes the entry in sorted position, updates the item array and logs the change. If it does not, the leaf must split.

Figure 2: The sequence of a leaf page split. The new sibling is linked in first, then a separator is pushed into the parent, which may cascade upward.

Figure 2 traces the steps. The engine allocates a new page, chooses a split point, moves the upper portion of entries to the new page and fixes the sibling links. It then inserts a separator key and a downlink for the new page into the parent. If the parent is also full, the parent splits, and the cascade can reach the root. A root split is the only way a B-tree grows taller, which is why every leaf stays at the same depth.

A split is the most expensive routine event in a b-tree index, for three reasons. It writes at least three pages: the old leaf, the new leaf and the parent, plus the right sibling’s left-link in PostgreSQL. It generates write-ahead log (WAL) records for all of them, and with full-page writes enabled the first touch of each page after a checkpoint logs a full 8KB image. And it leaves two half-empty pages where there was one full page, which lowers average occupancy until later inserts refill them.

Where the split point goes

The split point is a policy decision, and it is where key order starts to matter. A naive implementation always splits 50/50. That is right for random inserts, because new keys are equally likely to land on either half. It is badly wrong for monotonically increasing keys: the left half will never receive another insert, so it stays half-empty forever.

Real engines special-case the rightmost page of a b-tree index. PostgreSQL’s documentation states that for B-trees, leaf pages are filled to the fillfactor percentage during initial index builds and also when extending the index at the right, that is, when adding new largest key values. So an append-only bigint or timestamp index ends up with leaves close to 90% full. InnoDB documents the same idea from the other direction: it tries to leave 1/16 of each page free, so sequentially inserted pages end up about 15/16 full, while pages filled in random order are “from 1/2 to 15/16 full”.

PostgreSQL goes further. Since version 12, nbtree treats the heap tuple identifier as a tiebreaker key column, chooses split points that minimise the size of the new separator, and applies suffix truncation, which the nbtree README says “makes pivot tuples smaller, which delays splits of internal pages”. It also has a special single-value fill strategy, BTREE_SINGLEVAL_FILLFACTOR of 96, for leaves full of one duplicated value.

Random keys versus sequential keys

Random insertion produces a well-known steady state. Classic analysis of random B-tree growth, going back to Andrew Yao’s 1978 work on 2-3 trees, predicts average node occupancy near ln 2, or about 69%. Each leaf fills from half to full, splits back to two halves, and the long-run average settles around two thirds. That 31% of empty space is not a bug; it is the headroom that makes random inserts cheap. But it costs cache, storage and scan I/O.

Figure 3: Sequential keys concentrate inserts on the rightmost leaf, keeping pages dense and the working set tiny. Random UUIDv4 keys scatter inserts across every leaf.

Figure 3 shows the second, larger cost: the working set. With sequential keys, all inserts touch the rightmost leaf and its ancestors, a handful of pages that stay hot in memory. With UUIDv4, each insert lands on an effectively random leaf. Once the index is larger than the buffer cache, almost every insert needs a random read before it can write, and every dirtied page must eventually be written back. Write throughput then degrades to the random I/O rate of your storage.

UUIDv7, standardised in RFC 9562 in May 2024, fixes most of this. It places a 48-bit Unix millisecond timestamp in the most significant bits, followed by random bits, so values generated close in time sort close together. Inserts concentrate near the right edge of the index, much like a sequence, while keeping global uniqueness without coordination. PostgreSQL 18, released on 25 September 2025, added a built-in uuidv7() function; the project’s press kit describes it as a database-friendly option for better indexing and read performance. Note that RFC 9562 leaves monotonicity within the same millisecond to the implementation, so strict ordering across many concurrent generators is not guaranteed. Near-sorted is enough for the B-tree, though.

A runnable mini B+tree

The following Python builds a small B+tree with an order of 64 entries per node, a rightmost-split fill factor of 0.9 and a 50/50 split everywhere else. It is a teaching model, not a storage engine: there are no pages, latches or WAL. It is enough to watch the occupancy effects described above.

import bisect, random, uuid

class Leaf:
    def __init__(self):
        self.keys, self.vals, self.next = [], [], None

class Inner:
    def __init__(self):
        self.keys, self.kids = [], []

class BPlusTree:
    def __init__(self, order=64, fill=1.0):
        self.order = order          # max entries per node
        self.fill = fill            # fraction kept on the left at a rightmost split
        self.root = Leaf()
        self.splits = 0

    def _find_leaf(self, key):
        node, path = self.root, []
        while isinstance(node, Inner):
            i = bisect.bisect_right(node.keys, key)
            path.append((node, i))
            node = node.kids[i]
        return node, path

    def search(self, key):
        leaf, _ = self._find_leaf(key)
        i = bisect.bisect_left(leaf.keys, key)
        if i < len(leaf.keys) and leaf.keys[i] == key:
            return leaf.vals[i]
        return None

    def range(self, lo, hi):
        leaf, _ = self._find_leaf(lo)
        i = bisect.bisect_left(leaf.keys, lo)
        while leaf:
            while i < len(leaf.keys):
                if leaf.keys[i] > hi:
                    return
                yield leaf.keys[i], leaf.vals[i]
                i += 1
            leaf, i = leaf.next, 0

    def insert(self, key, val):
        leaf, path = self._find_leaf(key)
        i = bisect.bisect_left(leaf.keys, key)
        leaf.keys.insert(i, key)
        leaf.vals.insert(i, val)
        if len(leaf.keys) <= self.order:
            return
        # rightmost leaf: pack left page to fill factor; otherwise 50/50
        rightmost = leaf.next is None and i == len(leaf.keys) - 1
        cut = int(self.order * self.fill) if rightmost else len(leaf.keys) // 2
        new = Leaf()
        new.keys, new.vals = leaf.keys[cut:], leaf.vals[cut:]
        leaf.keys, leaf.vals = leaf.keys[:cut], leaf.vals[:cut]
        new.next, leaf.next = leaf.next, new
        self.splits += 1
        self._push_up(path, new.keys[0], new)

    def _push_up(self, path, sep, right):
        while path:
            parent, i = path.pop()
            parent.keys.insert(i, sep)
            parent.kids.insert(i + 1, right)
            if len(parent.keys) <= self.order:
                return
            mid = len(parent.keys) // 2
            new = Inner()
            sep = parent.keys[mid]
            new.keys, new.kids = parent.keys[mid + 1:], parent.kids[mid + 1:]
            parent.keys, parent.kids = parent.keys[:mid], parent.kids[:mid + 1]
            right = new
            self.splits += 1
        root = Inner()
        root.keys, root.kids = [sep], [self.root, right]
        self.root = root

    def stats(self):
        h, node = 1, self.root
        while isinstance(node, Inner):
            node, h = node.kids[0], h + 1
        leaves, entries, leaf = 0, 0, node
        while leaf:
            leaves += 1
            entries += len(leaf.keys)
            leaf = leaf.next
        return {"height": h, "leaves": leaves,
                "avg_leaf_fill": round(entries / (leaves * self.order), 3),
                "splits": self.splits}

if __name__ == "__main__":
    N = 200_000
    random.seed(7)
    seq = BPlusTree(order=64, fill=0.9)
    for k in range(N):
        seq.insert(k, k)
    rnd = BPlusTree(order=64, fill=0.9)
    for k in random.sample(range(N), N):
        rnd.insert(k, k)
    u4 = BPlusTree(order=64, fill=0.9)
    for _ in range(N):
        u4.insert(uuid.uuid4().int, None)
    print("sequential keys :", seq.stats())
    print("random keys     :", rnd.stats())
    print("uuid4 keys      :", u4.stats())
    print("lookup 4242     :", seq.search(4242))
    print("range 10..14    :", list(seq.range(10, 14)))

Running it with Python 3 on 200,000 keys printed this on my machine (UUID results vary slightly per run):

sequential keys : {'height': 4, 'leaves': 3509, 'avg_leaf_fill': 0.891, 'splits': 3615}
random keys     : {'height': 4, 'leaves': 4514, 'avg_leaf_fill': 0.692, 'splits': 4624}
uuid4 keys      : {'height': 4, 'leaves': 4511, 'avg_leaf_fill': 0.693, 'splits': 4630}
lookup 4242     : 4242
range 10..14    : [(10, 10), (11, 11), (12, 12), (13, 13), (14, 14)]

The toy reproduces both textbook results. Sequential inserts with a rightmost fill of 0.9 produce leaves about 89% full. Random integers and random UUIDs both settle at about 69%, the ln 2 prediction. The random trees need about 29% more leaf pages, and 28% more splits, to hold the same data. What the toy cannot show is the I/O effect, because everything is in memory. In a real engine, those extra pages are scattered writes against a cache that may not hold them.

Fill factor as a deliberate headroom budget

Fill factor is the percentage of each page an engine fills during a build, or on rightmost splits, before it starts a new page. In PostgreSQL the B-tree default is 90, and any value from 10 to 100 is accepted per the CREATE INDEX documentation. InnoDB exposes innodb_fill_factor for sorted index builds; at 100 it still leaves 1/16 of clustered index pages free.

The trade-off is simple to state. A lower fill factor leaves room for future inserts and updates into the middle of the key range, delaying the first wave of splits after a rebuild. A higher fill factor packs more entries per page, shrinking the index and improving cache hit rates and scan speed, at the cost of an immediate split storm if writes arrive in random positions.

Workload on the index	Suggested starting fill factor	Reasoning
Append-only, sequential key such as bigint identity or UUIDv7	100	No mid-range inserts; free space is wasted
Read-mostly reference table	100	Density helps scans; rare writes
Mixed, random-key inserts after a REINDEX	70 to 80	Absorb inserts before splits begin
Hot rows updated in place where the indexed column changes	70 to 90, then measure	Leaves room for new versions near old ones

Treat that table as starting points to measure, not rules. Random-key indexes converge to roughly 69% occupancy whatever you build them at; fill factor only changes how quickly and how violently they get there. For an index that will receive random inserts forever, a lower build fill factor mostly smooths the post-rebuild split burst.

Composite, Covering and Deduplicated Indexes

Database index internals are not only about single keys. Most production indexes are multi-column, and the way entries are ordered inside the leaves determines which queries they can serve.

Composite keys follow lexicographic order

A composite index on (tenant_id, created_at) sorts entries by tenant_id first and by created_at within each tenant. A query with tenant_id = 42 AND created_at > now() - interval '1 day' descends once to the first matching entry and then scans a contiguous run of leaves. That is the ideal shape: an equality prefix followed by one range.

Reverse the column order and the same query must visit every tenant’s slice of the last day. For years the practical rule was “the index is useless without the leading column”. PostgreSQL 18 softened that rule by adding skip scan for multicolumn B-tree indexes, which, per the release press kit, improves queries that omit an = condition on one or more prefix columns. Skip scan works well when the leading column has few distinct values, because the engine effectively runs one small descent per distinct value. With millions of distinct leading values it degenerates toward a full index scan, so column order still matters.

Covering indexes and index-only scans

A normal PostgreSQL b-tree index scan reads the leaf, then fetches the heap tuple to return columns and check visibility. An index-only scan skips the heap fetch when every needed column is in the index and the heap page is marked all-visible in the visibility map. The INCLUDE clause adds non-key payload columns to the leaf entries for exactly this purpose. The CREATE INDEX documentation says non-key columns cannot be used in search conditions but let index-only scans return them “without having to visit the index’s table”.

The cost is fan-out. Included columns widen every leaf entry, so leaves hold fewer entries and the index grows. Since they are non-key, PostgreSQL does not store them in internal pages, so internal fan-out is unaffected. Covering pays off for hot, narrow queries; it is a poor default for wide columns.

InnoDB gets a form of covering for free: secondary index entries already contain the primary key, so a query that needs only the indexed columns plus the primary key never touches the clustered index. Everything else requires a second B-tree descent into the clustered index, which is why InnoDB range queries over secondary indexes can cost one extra tree lookup per row.

Deduplication: duplicates without the bloat

Low-cardinality b-tree index columns, such as a status column or a foreign key with many children per parent, used to store the same key value once per row. PostgreSQL 13 introduced B-tree deduplication, which merges runs of duplicate entries into a single posting list tuple: one copy of the key followed by a sorted array of row pointers. The documentation stresses that it happens lazily, only when an insert would otherwise force a split, and only after index tuple deletion fails to free enough space. It is on by default and controlled by the deduplicate_items storage parameter.

Deduplication is disabled for some types where equal values are not byte-identical, including numeric, jsonb, floating-point types and text with nondeterministic collations, and it is never used for indexes with INCLUDE columns. That last restriction matters: adding an INCLUDE column to a low-cardinality index can make it much larger than before.

Concurrency: Latch Coupling and the B-Link Tree

An index that is fast for one thread but serialises under concurrency is useless for a database. The classic problem is a reader descending the tree while a writer splits the page the reader is about to visit. The reader can arrive at a page whose keys have moved to a new sibling.

The textbook answer is latch coupling, sometimes called crabbing. A thread holds the latch on a parent until it has acquired the latch on the child, then releases the parent. Writers that might split hold latches on every ancestor that could be affected. This is correct but creates contention at the root, the one page every operation touches.

Philip Lehman and S. Bing Yao published the better answer in 1981 in ACM Transactions on Database Systems: the B-link tree. Each page gets a right-link to its sibling and a high key, an upper bound for keys on that page. If a reader lands on a page and finds its search key above the high key, it knows a concurrent split happened and simply follows the right-link. PostgreSQL’s nbtree README states that it implements this algorithm, noting that “if the search key is greater than the high key, the page must’ve been split concurrently”.

The practical effect is that readers of a PostgreSQL b-tree index hold a latch on only one page at a time during descent, and a split can complete in two steps: first create and link the new right sibling, then insert the downlink into the parent. Between those steps the tree is briefly in an “incomplete split” state that is still searchable through right-links. PostgreSQL deviates from the paper in places. The README notes that Lehman and Yao assumed no read locks on unshared in-memory page copies, while PostgreSQL takes page-level shared locks, and that during insertion ascent it conservatively couples parent and child locks. Page deletion follows a variant of Lanin and Shasha’s “drain technique”, moving the deleted page’s key space to its right sibling.

The lesson for operators is that B-tree contention in modern engines rarely comes from the algorithm. It comes from workloads that pile every writer onto the same leaf. A monotonic key concentrates all inserts on the rightmost page, which is perfect for cache locality but can become a latch hotspot at very high insert rates on many cores. That is the one place where a sequential key is worse than a scattered one, and it is why some systems hash or reverse a key, or partition the table, to spread the right edge.

B-Tree vs LSM-Tree: Read, Write and Space Amplification

The fair way to compare a B-tree with a log-structured merge tree is through the three amplification factors. Read amplification is how many pages or files a lookup touches. Write amplification is how many bytes hit storage per byte the application writes. Space amplification is how much storage is used relative to the live data.

Figure 4: B-tree vs LSM-tree write paths. The B-tree updates pages in place behind a WAL; the LSM-tree buffers writes in memory, flushes sorted runs and merges them later through compaction.

Figure 4 contrasts the two write paths. A B-tree writes the WAL record, then modifies the leaf page in place in the buffer pool, eventually writing back the whole page. Changing one 20-byte entry dirties an 8KB or 16KB page, so small random writes carry large page-level write amplification, especially when full-page images are logged after a checkpoint. An LSM-tree appends to a log and an in-memory memtable, flushes it as an immutable sorted file, and rewrites data repeatedly as compaction merges files across levels.

Dimension	B-tree index	LSM-tree
Point read amplification	Low: one root-to-leaf path, upper levels cached	Higher: may check memtable plus several levels, mitigated by Bloom filters
Range scan	Excellent: one descent then a sequential leaf walk	Good but must merge iterators across levels
Write amplification	Page-granular: a small change rewrites a whole page, plus WAL and full-page images	Compaction rewrites data multiple times across levels; depends heavily on compaction style
Random-key insert I/O	Random reads and writes once the index exceeds cache	Sequential writes; random keys are cheap to ingest
Space amplification	Free space from fill factor and splits, roughly 10% to 30%, plus bloat	Obsolete versions awaiting compaction; tunable
Predictability	Stable read latency, write cost spikes at splits and checkpoints	Fast writes, background compaction can cause latency spikes and stalls
Typical engines	PostgreSQL, InnoDB, SQLite, SQL Server, Oracle	RocksDB, Cassandra, ScyllaDB, LevelDB

The space range for B-trees in that table is derived from the occupancy arithmetic above: a random-insert index at about 69% occupancy carries about 31% free space, and a 90% fill factor index carries 10%. Exact LSM figures depend on compaction strategy, so I have deliberately not invented numbers; the RocksDB compaction guide works through them.

The decision is workload-shaped. If the dominant cost is ingesting high volumes of keys in random order, especially on storage where random writes are expensive, the b-tree vs lsm-tree choice tilts toward LSM. If the dominant cost is low-latency point reads and range scans over data that fits mostly in memory, a B-tree is hard to beat. Most OLTP systems are read-heavy enough that the B-tree’s predictability wins, and a time-ordered key removes most of its write penalty.

Trade-offs, Gotchas, and What Goes Wrong

The B-tree is robust, but it fails in recognisable ways. Most are occupancy failures, consistent with the thesis of this post.

Bloat from MVCC. In PostgreSQL, an UPDATE creates a new row version, and unless it qualifies as a heap-only tuple (HOT) update, every index gets a new entry too. Dead entries stay until cleaned. PostgreSQL 14 added bottom-up index deletion, which the documentation describes as page-local passes triggered in anticipation of a “version churn page split”. It helps a lot, but it does not replace VACUUM. If long-running transactions hold back the cleanup horizon, indexes keep growing. Our post on MVCC, snapshot isolation and write skew explains why old snapshots block cleanup.

Pages never shrink by themselves. Deleting most of a key range leaves sparse pages. PostgreSQL only recycles completely empty leaf pages; half-empty pages stay half-empty until new inserts land there. InnoDB tries to merge pages that fall below MERGE_THRESHOLD, 50% by default. A “delete the oldest 90%” retention job can leave a large, sparse index that scans slowly. REINDEX CONCURRENTLY rebuilds it without blocking writes, at the cost of building a full second copy first. For table-level rebuild options, see our comparison of Postgres 19 REPACK, pg_repack and VACUUM FULL.

Random primary keys in clustered engines. In InnoDB, a UUIDv4 primary key scatters inserts across the table itself, not just an index, and every secondary index carries the 16-byte key. That is a double penalty compared with PostgreSQL’s heap.

Over-indexing. Every extra b-tree index multiplies write cost and WAL volume, and in PostgreSQL extra indexes on updated columns also disable HOT updates. An unused index is pure overhead; check usage statistics before adding another.

Low-selectivity indexes. A B-tree descent is cheap, but following thousands of row pointers in random heap order is not. Above a selectivity threshold the planner correctly prefers a sequential scan, and forcing the index makes things slower.

Fill factor folklore. Setting fill factor to 50 “for write performance” doubles the index size, halves cache efficiency and buys headroom that random inserts would have created anyway. Change it only with a measured reason.

Hot right edge. As noted earlier, a monotonic key can make the rightmost leaf a contention point at extreme insert rates. This is rare, but partitioning or hash-prefixed keys are the usual escape hatches.

Practical Recommendations

Start from bytes. Before creating a b-tree index, estimate entry width, entries per page and expected occupancy. That five-minute calculation predicts index size, cache footprint and height better than any rule of thumb, and it exposes wide keys or unnecessary INCLUDE columns before they ship.

Choose keys for locality. A bigint identity or a UUIDv7 primary key keeps inserts on the right edge, keeps leaves near the fill factor and keeps the write working set tiny. Use UUIDv4 only where unguessability across the whole value matters more than insert locality, and remember that UUIDv7 exposes creation time.

Design composite indexes around the query’s equality prefix and single range column, then test whether a covering INCLUDE actually produces index-only scans. In PostgreSQL that also depends on the visibility map, so a table that is never vacuumed gets few true index-only scans.

Monitor occupancy, not just size. In PostgreSQL the pgstattuple extension’s pgstatindex() reports average leaf density and leaf fragmentation; in InnoDB, INFORMATION_SCHEMA and innodb_metrics expose split and merge counters. Rebuild when density is low and scans matter, not on a calendar.

Checklist:

[ ] Compute entry width and entries per page for every new index.
[ ] Prefer sequential or UUIDv7 keys for high-insert tables.
[ ] Put equality columns first and one range column last in composite indexes.
[ ] Add INCLUDE columns only for proven hot queries, and check deduplication impact.
[ ] Leave fill factor at the default unless measurement says otherwise; use 100 for append-only indexes.
[ ] Track leaf density and bloat; use REINDEX CONCURRENTLY for sparse, scan-heavy indexes.
[ ] Drop indexes that usage statistics show are never scanned.
[ ] Consider an LSM engine only when random-key ingest dominates and reads can tolerate it.

Frequently Asked Questions

What is the difference between a B-tree and a B+tree?

A classic B-tree stores keys and their data in every node, so a lookup can stop at an internal node. A B+tree stores all data or row pointers in the leaves, keeps only separator keys in internal pages and links leaves together. That raises fan-out, makes the tree shallower and turns range scans into sequential leaf walks. Nearly every database “B-tree index”, including PostgreSQL nbtree, InnoDB and SQLite table b-trees, is structurally a B+tree, even when the documentation just says B-tree.

How many levels does a B-tree index have for a billion rows?

Usually three to five. With PostgreSQL’s 8KB pages and a bigint key, a leaf holds roughly 366 entries at the default 90% fill factor and internal pages fan out to a few hundred children. One billion rows then need about 2.7 million leaves and a four-level tree. The upper three levels total under 10,000 pages, so they stay cached, and a lookup typically costs one uncached leaf read plus the table row. Wider keys add leaf pages but rarely add a level.

Why are random UUID primary keys slow in a B-tree index?

UUIDv4 values are uniformly random, so each insert lands on an arbitrary leaf. Leaves settle near 69% occupancy after repeated 50/50 splits, making the index larger. More importantly, once the index exceeds memory, nearly every insert needs a random read and later a random write-back, so throughput falls to the storage’s random I/O rate. Sequential keys touch only the rightmost leaf. In InnoDB the penalty is doubled because the table itself is the clustered primary-key index.

Is UUIDv7 better than UUIDv4 for database indexes?

For insert locality, yes. UUIDv7, defined in RFC 9562, puts a 48-bit millisecond timestamp in the leading bits, so new values sort near each other and inserts concentrate at the right edge of the index, much like an auto-increment column. That keeps pages dense and the working set small while preserving decentralised generation. The trade-offs are that it reveals creation time and is not strictly monotonic across generators. PostgreSQL 18 provides a native uuidv7() function.

What fill factor should I use for a B-tree index?

Start with the default, which is 90 for PostgreSQL B-trees. Use 100 for append-only indexes on sequential keys, since the free space would never be used. Consider 70 to 80 only for indexes that receive heavy random inserts or updates right after a rebuild, to soften the initial split burst. Random-insert indexes converge to about two-thirds occupancy regardless of build fill factor, so very low values mostly waste space. Measure leaf density with pgstatindex() before and after changing it.

When should I choose an LSM-tree over a B-tree?

Choose an LSM-tree when write throughput dominates, keys arrive in random order and the dataset is far larger than memory, such as large event or key-value stores. LSM engines turn random writes into sequential flushes and compaction, at the cost of higher read amplification and background compaction spikes. Choose a B-tree when point reads, range scans and predictable latency matter most, which describes most OLTP workloads. A time-ordered key often removes the B-tree’s main write penalty without changing engines.

B-Tree and B+Tree Index Internals: Page Splits, Fill Factor, Fan-Out and Why Your Database Index Is Fast (2026)