How to Build a B+Tree Index in Python and Measure Why Random Inserts Leave Pages About 70 Percent Full

Every time a database finds one row among millions without reading the whole table, a tree is doing the work. SQLite’s file format document says SQLite uses two variants of b-trees, and PostgreSQL’s documentation says it includes an implementation of “the standard btree (multi-way balanced tree) index data structure”. In this tutorial you will build the common core of both in Python, one small step at a time, and then use your own tree to measure things that documentation usually only states.

By the end you will have a B+tree that stores 64-bit integer keys and values in fixed 4,096-byte pages inside a file, with lookups, inserts, range scans and deletes. You will have a test suite that you have watched catch twelve deliberately planted bugs. And you will have three measurements of your own: how few pages a lookup touches, how full the pages get under different insert patterns, and how many pages reach the file when the cache is small. You will finish by reading the pages of a real SQLite database file with a short script and comparing its numbers with yours.

No database knowledge is assumed. If you can read a Python class and a short recursive function, you can follow along. Every step gives you the code, the output to expect, and a plain explanation of what the code does and why it is written that way. Everything runs on your own machine with the standard library plus one testing package.

The ideas you need before you write any code

A handful of small ideas carry the whole tutorial, so it is worth defining them now.

A page is a fixed-size block of a file that a program reads or writes in one piece. SQLite’s file format document says it plainly: “All reads from and writes to the main database file begin at a page boundary and all writes are an integer number of pages in size.” We will use 4,096-byte pages, which is also the default page size of the SQLite build that ships with the Python I used.

An index maps a key, the thing you search by such as an order number, to a value, such as the location of the row. Halving a sorted list works well in memory, but on disk every halving step can land on a different page, so the cost that matters is the number of pages touched, not the number of comparisons. A tree fixes this by making every node as big as a whole page. One page read then narrows the search by a factor of a couple of hundred instead of a factor of two.

A B+tree is such a tree with two kinds of pages. Leaf pages hold the actual key and value pairs in sorted order and are chained from left to right. Internal pages hold only separator keys and child page numbers, and an internal page with K separators has K plus 1 children. That is how SQLite describes its interior pages: “An interior page contains K keys together with K+1 pointers to child b-tree pages.” SQLite’s table b-trees “use a 64-bit signed integer key and store all data in the leaves”, which is the same shape we are about to build.

Three more words will come up all the time. The fan-out is the number of children an internal page has. The height is the number of levels from the root page down to a leaf, and it is also the number of pages a lookup must read. A split is what happens when a page overflows: it is cut in two and the parent gets one more separator. Here is the smallest interesting tree, drawn as text:

internal page   ( 10  20 )                    below 10 go left, 10 to 19 go middle, 20 and up go right
leaf pages      [5 8]  ->  [10 12 15]  ->  [20 25]    the leaves are chained from left to right

To look up 12, you read the internal page, see that 12 lies between the separators 10 and 20, follow the middle child, and find 12 in the leaf. That is two pages, whatever the size of the table. To read every key from 10 to 20 in order, you find the leaf for 10 and then follow the chain to the right, which is why a B+tree is good at range queries as well as single lookups.

Prerequisites

• Operating system: I ran everything on Windows 11. The code uses only portable standard-library calls, so macOS and Linux should work too; only the command that activates the virtual environment differs.
• Python: I used Python 3.13.14. The B+tree itself needs nothing but the standard library. I did not test other Python versions.
• Test package: pytest, for Step 7 only. I used pytest 9.1.1.
• Time and disk: about an hour to type and read. The slowest script takes about ten seconds on my machine, and the demos use well under 100 megabytes of temporary disk space, which they delete when they finish.
• Knowledge: Python lists, functions, classes and simple recursion. No database knowledge is needed.

Step 0: Set up the project

Create a folder, a virtual environment and install pytest. The last command prints the Python and SQLite versions your lab will use, so you can compare them with mine.

mkdir bplus
cd bplus
python -m venv .venv
.venv\Scripts\activate
python -m pip install pytest
python -c "import sys, sqlite3; print(sys.version.split()[0], sqlite3.sqlite_version)"

On macOS or Linux, activate the environment with source .venv/bin/activate instead. On my machine the last command printed 3.13.14 3.50.4. Your numbers may differ, and that is fine: only Step 10 cares about the SQLite version. By the end the folder will hold btree.py (the tree), test_btree.py, mutants.py, sqlite_pages.py and eleven small demo scripts named step01_codec.py to step11_writes.py. Each script is short, and each one prints the output shown under it, so you always know whether your copy matches.

Step 1: Decide what a page looks like

Before any tree logic we need to answer a plain question: which bytes make up one node? Create btree.py and start it with the constants and the Node class below.

"""btree.py: a disk-backed B+tree that maps 64-bit integer keys to 64-bit integer values."""
import bisect
import os
import struct
from collections import Counter, OrderedDict

PAGE_SIZE = 4096
LEAF, INTERNAL = 1, 2
HEADER = struct.Struct("<BxHQ4x")   # kind, padding, number of keys, next leaf, padding: 16 bytes
META = struct.Struct("<8sIQIIQ")    # magic, page size, root page, max leaf, max keys, page count
MAGIC = b"BPTREE01"


class Node:
    """One page worth of tree. A leaf holds keys and values; an internal node holds keys and child page numbers."""

    def __init__(self, page_no, kind):
        self.page_no = page_no
        self.kind = kind
        self.keys = []
        self.vals = []   # leaf only: vals[i] belongs to keys[i]
        self.kids = []   # internal only: always one more child than keys
        self.nxt = 0     # leaf only: page number of the next leaf to the right, 0 for none

    @property
    def is_leaf(self):
        return self.kind == LEAF

    def encode(self, page_size):
        n = len(self.keys)
        if self.is_leaf:
            body = struct.pack(f"<{2 * n}Q", *self.keys, *self.vals)
        else:
            body = struct.pack(f"<{2 * n + 1}Q", *self.keys, *self.kids)
        page = HEADER.pack(self.kind, n, self.nxt) + body
        if len(page) > page_size:
            raise ValueError(f"page {self.page_no} needs {len(page)} bytes but a page holds {page_size}")
        return page.ljust(page_size, b"\0")

    @classmethod
    def decode(cls, page_no, page):
        kind, n, nxt = HEADER.unpack_from(page)
        node = cls(page_no, kind)
        if kind == LEAF:
            numbers = struct.unpack_from(f"<{2 * n}Q", page, HEADER.size)
            node.keys, node.vals, node.nxt = list(numbers[:n]), list(numbers[n:]), nxt
        elif kind == INTERNAL:
            numbers = struct.unpack_from(f"<{2 * n + 1}Q", page, HEADER.size)
            node.keys, node.kids = list(numbers[:n]), list(numbers[n:])
        else:
            raise ValueError(f"page {page_no} has an unknown kind: {kind}")
        return node

What the code does

A node is either a leaf (kind 1) or an internal page (kind 2). A leaf keeps two parallel lists, keys and vals, plus nxt, the page number of the next leaf to the right. The number 0 means there is none, which works because page 0 is reserved for a meta page in Step 2. An internal page keeps keys and kids, the child page numbers, and there is always one more child than there are keys.

The first 16 bytes of every page are a header described by struct.Struct("<BxHQ4x"). Read the format string from left to right. The < means little-endian with no alignment padding (the Python documentation has a byte order table), B is one byte for the kind, x is a padding byte, H is a two-byte count of keys, Q is an eight-byte number for nxt, and 4x is four more padding bytes. Everything after the header is 8-byte unsigned integers. A leaf stores all its keys and then all its values; an internal page stores its keys and then its child page numbers.

encode refuses to produce a page longer than page_size and pads the rest with zero bytes, so every page has exactly the same length. That fixed length is the point: page number N always starts at byte N times the page size, so finding a page never needs a search.

Run it

Save this script as step01_codec.py next to btree.py and run python step01_codec.py.

"""step01_codec.py: look at the bytes of one encoded leaf page and prove they decode back."""
from btree import LEAF, Node

leaf = Node(1, LEAF)
leaf.keys, leaf.vals, leaf.nxt = [10, 20, 30], [100, 200, 300], 7
page = leaf.encode(4096)
print("page length:", len(page))
print("header (16 bytes):", page[:16].hex(" "))
print("keys:  ", [int.from_bytes(page[start:start + 8], "little") for start in range(16, 40, 8)])
print("values:", [int.from_bytes(page[start:start + 8], "little") for start in range(40, 64, 8)])
print("unused tail is zeros:", set(page[64:]) == {0})
back = Node.decode(1, page)
print("round trip:", back.keys == leaf.keys and back.vals == leaf.vals and back.nxt == leaf.nxt)

leaf.keys, leaf.vals = list(range(255)), list(range(255))
print("255 entries fit:", len(leaf.encode(4096)) == 4096)
leaf.keys, leaf.vals = list(range(256)), list(range(256))
try:
    leaf.encode(4096)
except ValueError as error:
    print("256 entries:", error)

page length: 4096
header (16 bytes): 01 00 03 00 07 00 00 00 00 00 00 00 00 00 00 00
keys:   [10, 20, 30]
values: [100, 200, 300]
unused tail is zeros: True
round trip: True
255 entries fit: True
256 entries: page 1 needs 4112 bytes but a page holds 4096

The header line is the 16 bytes we designed: 01 is the kind (a leaf), 00 is padding, 03 00 is three keys, and 07 00 00 00 00 00 00 00 is the next-leaf page number 7. The script then decodes the keys and values straight from the raw bytes, so you can see the layout really is what we claimed, and shows that the unused tail is zeros and that decoding returns the same node. The last two lines are how you find a page’s capacity. A leaf needs 16 header bytes plus 16 bytes per entry (8 for the key and 8 for the value), so (4,096 minus 16) divided by 16 gives 255 entries, and a 256th entry makes the page 4,112 bytes. An internal page needs 8 bytes per key and 8 per child, with one extra child, so it holds 254 keys and 255 children. Step 2 prints both numbers so you do not have to trust my arithmetic.

Common mistake: skipping the size check

Without the length check in encode, a 256th entry would quietly produce a 4,112-byte page. Writing it at its offset would overwrite the first 16 bytes of the next page, and you would see corruption far from the cause. Raising an error at the moment of encoding keeps the failure next to the bug.

Step 2: Build the pager that reads, writes and caches pages

The tree should not care whether a page comes from memory or from the file. The pager is the only part of the program that touches the file. Add this class to btree.py, below Node. The first line of the block is a comment that marks where it belongs; you can leave it out.

# btree.py (continued)
class Pager:
    """Reads and writes the fixed-size pages of one file and keeps recently used nodes in a small cache."""

    def __init__(self, path, page_size=PAGE_SIZE, cache_pages=256):
        self.page_size, self.cache_pages = page_size, cache_pages
        self.fresh = not os.path.exists(path) or os.path.getsize(path) == 0
        self.file = open(path, "w+b" if self.fresh else "r+b")
        self.cache = OrderedDict()   # page number -> Node, least recently used first
        self.dirty = set()           # pages changed since they were last written
        self.free_list = []          # pages released by merges, handed out again by allocate()
        self.gets = self.reads = self.writes = 0
        if self.fresh:
            self.n_pages, self.meta = 1, b""   # page 0 is reserved for the meta page
        else:
            self.meta = self.file.read(page_size)
            self.n_pages = META.unpack_from(self.meta)[5]

    def allocate(self, kind):
        if self.free_list:
            page_no = self.free_list.pop()
        else:
            page_no, self.n_pages = self.n_pages, self.n_pages + 1
        node = Node(page_no, kind)
        self.cache[page_no] = node
        self.dirty.add(page_no)
        return node

    def get(self, page_no):
        self.gets += 1                       # a logical read: the tree asked for this page
        node = self.cache.get(page_no)
        if node is None:
            self.file.seek(page_no * self.page_size)
            node = Node.decode(page_no, self.file.read(self.page_size))
            self.cache[page_no] = node
            self.reads += 1                  # a physical read: the page came from the file
        else:
            self.cache.move_to_end(page_no)
        return node

    def mark(self, node):
        self.dirty.add(node.page_no)

    def free(self, node):
        self.cache.pop(node.page_no, None)
        self.dirty.discard(node.page_no)
        self.free_list.append(node.page_no)

    def _write(self, node):
        self.file.seek(node.page_no * self.page_size)
        self.file.write(node.encode(self.page_size))
        self.writes += 1
        self.dirty.discard(node.page_no)

    def settle(self):
        """Call between operations: evict the least recently used nodes down to the cache size, writing dirty ones."""
        while len(self.cache) > self.cache_pages:
            page_no, node = self.cache.popitem(last=False)
            if page_no in self.dirty:
                self._write(node)

    def flush(self):
        for page_no in sorted(self.dirty):
            self._write(self.cache[page_no])
        self.file.seek(0)
        self.file.write(self.meta.ljust(self.page_size, b"\0"))
        self.file.flush()

What the code does

The pager keeps a cache of decoded nodes in an OrderedDict, ordered from least to most recently used: a cache hit moves the node to the end, and eviction takes from the front. It counts two things. gets is a logical read: the tree asked for a page. reads is a physical read: the page had to come from the file. Every measurement later in this tutorial is a ratio of these counters, so the difference matters.

The dirty set holds the numbers of pages changed since they were last written. mark adds to it, allocate hands out the next free page number (or reuses one from free_list, which merges will fill in Step 6), and free returns a page. Page 0 is never handed out, because flush uses it as a meta page that records where the root is.

The important rule is in settle. The tree calls it once at the end of each operation, and it evicts the least recently used nodes until the cache is back to cache_pages, writing the dirty ones first. Evicting only between operations is deliberate. While an insert is running, the tree holds several nodes in local variables and changes them. If the pager wrote one out and dropped it halfway through, a later change to the same object would be lost, or a half-changed page would reach the file. flush writes every dirty node plus the meta page. We never call fsync, so this pager is not crash-safe; the write-ahead log tutorial shows how real systems fix that.

Run it

"""step02_pager.py: store two nodes in a file, read them back, and watch the counters."""
import os
import tempfile

from btree import HEADER, LEAF, PAGE_SIZE, Pager

print("header bytes:", HEADER.size)
print("leaf capacity:", (PAGE_SIZE - HEADER.size) // 16, "entries")
keys = (PAGE_SIZE - HEADER.size - 8) // 16
print("internal capacity:", keys, "keys,", keys + 1, "children")

with tempfile.TemporaryDirectory(ignore_cleanup_errors=True) as folder:
    path = os.path.join(folder, "demo.db")
    pager = Pager(path, cache_pages=1)
    first = pager.allocate(LEAF)
    first.keys, first.vals = [10, 20, 30], [1, 2, 3]
    second = pager.allocate(LEAF)
    second.keys, second.vals = [40, 50], [4, 5]
    print("pages allocated:", pager.n_pages, "(page 0 is reserved for the meta page)")
    print("before settle: cached", sorted(pager.cache), "dirty", sorted(pager.dirty), "page writes", pager.writes)
    pager.settle()
    print("after settle:  cached", sorted(pager.cache), "dirty", sorted(pager.dirty), "page writes", pager.writes)
    pager.file.flush()
    print("file size:", os.path.getsize(path), "bytes =", os.path.getsize(path) // PAGE_SIZE, "pages")
    again = pager.get(first.page_no)
    print("page", again.page_no, "keys", again.keys, "| logical reads", pager.gets, "physical reads", pager.reads)
    pager.get(first.page_no)
    print("same page again: logical reads", pager.gets, "physical reads", pager.reads)
    pager.file.close()

header bytes: 16
leaf capacity: 255 entries
internal capacity: 254 keys, 255 children
pages allocated: 3 (page 0 is reserved for the meta page)
before settle: cached [1, 2] dirty [1, 2] page writes 0
after settle:  cached [2] dirty [2] page writes 1
file size: 8192 bytes = 2 pages
page 1 keys [10, 20, 30] | logical reads 1 physical reads 1
same page again: logical reads 2 physical reads 1

Follow the counters. Two pages were allocated, so n_pages is 3 (page 0 is the reserved meta page). With a cache of one page, settle evicted page 1, which was dirty, so it was written: the page-write counter went from 0 to 1 and only page 2 stays cached. The file is 8,192 bytes, two pages long, because page 1 sits at offset 4,096 and page 0 has not been written yet. Asking for page 1 again costs one logical and one physical read, and asking a second time costs one more logical read and no physical read. Internal capacity is printed too: 254 keys and 255 children.

Step 3: Search from the root to a leaf

Now the tree itself. Add the BTree class below the pager, with its constructor and the two methods that look keys up.

# btree.py (continued)
class BTree:
    def __init__(self, pager, max_leaf=None, max_keys=None, append_fill=None):
        self.pager = pager
        self.append_fill = append_fill   # None: always split in half; 0.9: pack the left page to 90% when appending at the right edge
        self.events = Counter()          # how often each kind of restructuring happened
        leaf_cap = (pager.page_size - HEADER.size) // 16          # 8-byte key + 8-byte value
        key_cap = (pager.page_size - HEADER.size - 8) // 16       # 8-byte key + 8-byte child, plus one extra child
        if pager.fresh:
            self.max_leaf = min(max_leaf or leaf_cap, leaf_cap)
            self.max_keys = min(max_keys or key_cap, key_cap)
            self.root = pager.allocate(LEAF).page_no
        else:
            magic, _, self.root, self.max_leaf, self.max_keys, _ = META.unpack_from(pager.meta)
            if magic != MAGIC:
                raise ValueError("this file is not a B+tree")
        self.min_leaf = (self.max_leaf + 1) // 2   # fewest entries a non-root leaf may keep
        self.min_keys = self.max_keys // 2         # fewest keys a non-root internal node may keep

    def flush(self):
        size = self.pager.page_size
        self.pager.meta = META.pack(MAGIC, size, self.root, self.max_leaf, self.max_keys, self.pager.n_pages)
        self.pager.flush()

    def _leaf_for(self, key):
        node = self.pager.get(self.root)
        while not node.is_leaf:
            node = self.pager.get(node.kids[bisect.bisect_right(node.keys, key)])
        return node

    def get(self, key, default=None):
        leaf = self._leaf_for(key)
        i = bisect.bisect_left(leaf.keys, key)
        value = leaf.vals[i] if i < len(leaf.keys) and leaf.keys[i] == key else default
        self.pager.settle()
        return value

What the code does

The constructor either creates a fresh tree, which is one empty leaf that is also the root, or reads the meta page of an existing file. max_leaf and max_keys default to what fits in a page, 255 and 254. You can pass smaller values to build tiny trees that fit on a screen, which is how the demos in Steps 4 to 6 work. min_leaf and min_keys are the fewest entries a non-root page may keep; deleting uses them in Step 6. events is a counter of restructuring operations that the tests will read later.

The heart of the search is _leaf_for. At each internal page it picks a child with bisect.bisect_right(node.keys, key). The rule is that child number i holds keys from separator i minus 1 up to, but not including, separator i. A key equal to a separator therefore belongs to the child on its right, and bisect_right does exactly that. The bisect documentation describes the two variants: for bisect_left, “If x is already present in a, the insertion point will be before (to the left of) any existing entries.” Inside a leaf we want the position of the exact key, so get uses bisect_left and then checks that the key at that position really is the one we asked for.

Run it

We have no insert yet, so this demo assembles a tiny tree by hand: three leaves chained together under one internal page with the separators 10 and 20.

"""step03_search.py: assemble a three-leaf tree by hand and look keys up in it."""
import bisect
import os
import tempfile

from btree import INTERNAL, LEAF, BTree, Pager

with tempfile.TemporaryDirectory(ignore_cleanup_errors=True) as folder:
    pager = Pager(os.path.join(folder, "hand.db"))
    tree = BTree(pager)                        # a new tree is one empty leaf, which is also the root
    leaves = [pager.get(tree.root), pager.allocate(LEAF), pager.allocate(LEAF)]
    for leaf, keys in zip(leaves, ([5, 8], [10, 12, 15], [20, 25])):
        leaf.keys, leaf.vals = keys, [k * 100 for k in keys]
    for left, right in zip(leaves, leaves[1:]):
        left.nxt = right.page_no                # the leaf chain: p1 -> p2 -> p3
    root = pager.allocate(INTERNAL)
    root.keys, root.kids = [10, 20], [leaf.page_no for leaf in leaves]
    tree.root = root.page_no
    print("root keys", root.keys, "children", root.kids)
    for key in (5, 10, 12, 20, 21, 99):
        pager.gets = 0
        value = tree.get(key, "missing")
        child = bisect.bisect_right(root.keys, key)
        print(f"get({key:>2}) -> {value!s:>7} | child index {child} | pages touched {pager.gets}")
    pager.file.close()

root keys [10, 20] children [1, 2, 3]
get( 5) ->     500 | child index 0 | pages touched 2
get(10) ->    1000 | child index 1 | pages touched 2
get(12) ->    1200 | child index 1 | pages touched 2
get(20) ->    2000 | child index 2 | pages touched 2
get(21) -> missing | child index 2 | pages touched 2
get(99) -> missing | child index 2 | pages touched 2

Look at the lookup for 10. It equals the first separator, so the child index is 1 and the search goes to the middle leaf, where 10 lives. The lookups for 21 and 99 go to the last leaf and report missing. Every lookup touched exactly two pages, the root and one leaf, which is the height of this tree. That is the property the rest of the tutorial keeps coming back to: a lookup costs one page per level.

Common mistake: choosing the child with bisect_left

With bisect_left a key equal to a separator would go left, to a leaf that does not contain it, and every lookup of a separator key would return “not found”. It is a one-word bug that survives simple tests, and it is the first planted bug in Step 7.

Step 4: Insert keys and split pages that overflow

Inserting is where the tree earns its keep. Add these methods inside the BTree class, keeping the four-space indentation. (The comment line at the top of each continuation block is only a marker.)

# btree.py (continued)
    def put(self, key, value):
        """Store value under key. Returns True if the key is new and False if it replaced an old value."""
        if not (0 <= key < 1 << 64 and 0 <= value < 1 << 64):
            raise ValueError("keys and values are unsigned 64-bit integers")
        root = self.pager.get(self.root)
        is_new, split = self._put(root, key, value)
        if split is not None:                      # the root itself split, so the tree grows one level at the top
            separator, right_no = split
            new_root = self.pager.allocate(INTERNAL)
            new_root.keys, new_root.kids = [separator], [root.page_no, right_no]
            self.root = new_root.page_no
            self.events["new_root"] += 1
        self.pager.settle()
        return is_new

    def _put(self, node, key, value):
        """Insert below node. Returns (is_new, split) where split is None or (separator, new right page number)."""
        if node.is_leaf:
            i = bisect.bisect_left(node.keys, key)
            if i < len(node.keys) and node.keys[i] == key:
                node.vals[i] = value
                self.pager.mark(node)
                return False, None
            node.keys.insert(i, key)
            node.vals.insert(i, value)
            self.pager.mark(node)
            return True, (self._split_leaf(node, i) if len(node.keys) > self.max_leaf else None)
        i = bisect.bisect_right(node.keys, key)
        is_new, split = self._put(self.pager.get(node.kids[i]), key, value)
        if split is None:
            return is_new, None
        separator, right_no = split
        node.keys.insert(i, separator)
        node.kids.insert(i + 1, right_no)
        self.pager.mark(node)
        return is_new, (self._split_internal(node) if len(node.keys) > self.max_keys else None)

    def _split_leaf(self, leaf, index):
        count = len(leaf.keys)
        if self.append_fill and leaf.nxt == 0 and index == count - 1:
            cut = max(1, min(count - 1, round(self.max_leaf * self.append_fill)))   # appending at the right edge
        else:
            cut = (count + 1) // 2
        right = self.pager.allocate(LEAF)
        right.keys, leaf.keys = leaf.keys[cut:], leaf.keys[:cut]
        right.vals, leaf.vals = leaf.vals[cut:], leaf.vals[:cut]
        right.nxt, leaf.nxt = leaf.nxt, right.page_no
        self.pager.mark(leaf)
        self.events["split_leaf"] += 1
        return right.keys[0], right.page_no        # the separator is COPIED up: the leaf still holds that key

    def _split_internal(self, node):
        mid = len(node.keys) // 2
        separator = node.keys[mid]                 # this key is MOVED up to the parent and kept in neither half
        right = self.pager.allocate(INTERNAL)
        right.keys, node.keys = node.keys[mid + 1:], node.keys[:mid]
        right.kids, node.kids = node.kids[mid + 1:], node.kids[:mid + 1]
        self.pager.mark(node)
        self.events["split_internal"] += 1
        return separator, right.page_no

    def dump(self):
        """The tree as indented text: (keys) for internal nodes, [keys] for leaves, with page numbers."""
        lines = []

        def show(page_no, depth):
            node = self.pager.get(page_no)
            keys, pad = " ".join(map(str, node.keys)), "    " * depth
            if node.is_leaf:
                link = f" -> p{node.nxt}" if node.nxt else ""
                lines.append(f"{pad}[{keys}]  p{page_no}{link}")
            else:
                lines.append(f"{pad}({keys})  p{page_no}")
                for kid in node.kids:
                    show(kid, depth + 1)

        show(self.root, 0)
        return "\n".join(lines)

What the code does

put validates the numbers (they must fit in 8 bytes) and calls the recursive _put. _put returns two things: whether the key is new, and a split, which is either None or a pair of a separator key and the page number of a new right-hand page that the parent must now adopt. In a leaf, bisect_left finds the position. If the key exists, its value is replaced. Otherwise the key and value are inserted, and if the leaf now holds more than max_leaf entries it is split. In an internal page, we pick the child, recurse, and if the child reported a split we insert the new separator and child pointer. The internal page may then overflow and split in turn, so a split can ripple upward through the recursion.

The two split methods differ in one important detail, which the comments mark. A leaf split copies the separator up: the first key of the new right leaf becomes the separator, and the leaf still contains it, because leaves must keep every key. An internal split moves the middle key up: it appears in the parent and in neither half, because internal keys are only signposts. Both cut the page roughly in half. When the root itself splits, put allocates a new root with one separator and two children, and the height grows by one. The tree grows only at the top, never at the bottom, so every leaf is always at the same depth. That is the “balanced” in balanced tree. dump prints a tree as indented text for the demos, and append_fill is an option we will use in Step 9.

Run it

This demo inserts the keys 1 to 30 in order into a tree whose pages hold at most three entries, and prints the tree whenever its height changes.

"""step04_insert.py: insert keys in order into a tree with tiny nodes and print it whenever its shape changes."""
import os
import tempfile

from btree import BTree, Pager

with tempfile.TemporaryDirectory(ignore_cleanup_errors=True) as folder:
    tree = BTree(Pager(os.path.join(folder, "tiny.db"), cache_pages=100), max_leaf=3, max_keys=3)
    height = 1
    for key in range(1, 31):
        tree.put(key, key * 10)
        new_height = tree.check()["height"]
        if key in (3, 4) or new_height != height:
            print(f"--- after inserting {key}: {new_height} level(s)")
            if new_height <= 3:
                print(tree.dump())
            height = new_height
    stats = tree.check()
    print("--- after inserting 30 keys")
    print("leaves:", stats["leaves"], "| internal pages:", stats["internals"], "| entries:", stats["entries"])
    print("events:", dict(tree.events))
    tree.pager.file.close()

--- after inserting 3: 1 level(s)
[1 2 3]  p1
--- after inserting 4: 2 level(s)
(3)  p3
    [1 2]  p1 -> p2
    [3 4]  p2
--- after inserting 10: 3 level(s)
(7)  p8
    (3 5)  p3
        [1 2]  p1 -> p2
        [3 4]  p2 -> p4
        [5 6]  p4 -> p5
    (9)  p7
        [7 8]  p5 -> p6
        [9 10]  p6
--- after inserting 28: 4 level(s)
--- after inserting 30 keys
leaves: 15 | internal pages: 8 | entries: 30
events: {'split_leaf': 14, 'new_root': 3, 'split_internal': 5}

In the dump, round brackets are internal pages and square brackets are leaves; p3 is the page number and -> p4 is the next-leaf link. After inserting 3 there is one leaf. The 4th key overflows it: [1 2 3 4] is cut into [1 2] and [3 4], the separator 3 is copied up, and a new root is created, so the height becomes 2. After inserting 10 the height becomes 3. The root held the separators 3, 5, 7 and 9, which is one more than three keys allow, so it was split and the middle key, 7, moved up into a new root. Notice that 7 still exists as a key in a leaf, but the root’s 7 is only a signpost. At the end the counters say the tree performed 14 leaf splits, 5 internal splits and 3 root splits to hold 30 entries.

Common mistake: moving the key up from a leaf

If a leaf split moved its separator up instead of copying it, the key would vanish from the leaf and a later lookup would fail. The reverse mistake, copying up from an internal page, leaves the key in both halves and the parent. Step 7 plants the second of these bugs and the checker catches it.

Step 5: Scan a range by following the leaf chain

Because the leaves are chained, reading keys in order is cheap. Add items to the class.

# btree.py (continued)
    def items(self, low=0, high=None):
        """Yield (key, value) pairs with low <= key < high in key order by following the leaf links."""
        leaf = self._leaf_for(low)
        i = bisect.bisect_left(leaf.keys, low)
        while True:
            while i < len(leaf.keys):
                if high is not None and leaf.keys[i] >= high:
                    self.pager.settle()
                    return
                yield leaf.keys[i], leaf.vals[i]
                i += 1
            if leaf.nxt == 0:
                break
            leaf = self.pager.get(leaf.nxt)
            self.pager.settle()
            i = 0
        self.pager.settle()

items is a generator. It finds the leaf for low with the same descent as a lookup, yields entries until a key reaches high (which is excluded), and moves to the next leaf by following nxt. It calls settle as it moves so a long scan cannot fill the cache. It must not be used while the tree is being modified.

Run it

"""step05_range.py: a range scan walks the leaf chain instead of searching from the root for every key."""
import os
import random
import tempfile

from btree import BTree, Pager

rng = random.Random(5)
keys = rng.sample(range(1 << 40), 100_000)
with tempfile.TemporaryDirectory(ignore_cleanup_errors=True) as folder:
    tree = BTree(Pager(os.path.join(folder, "range.db"), cache_pages=10**6))
    for key in keys:
        tree.put(key, key % 1000)
    stats = tree.check()
    ordered = sorted(keys)
    low, high = ordered[50_000], ordered[51_000]       # exactly 1,000 keys lie in [low, high)
    pager = tree.pager
    pager.gets = 0
    found = list(tree.items(low, high))
    print(f"range scan: {len(found)} keys, sorted: {found == sorted(found)}, pages touched: {pager.gets}")
    pager.gets = 0
    for key in ordered[50_000:51_000]:
        tree.get(key)
    print(f"1,000 separate lookups: {pager.gets} pages touched")
    print(f"the tree has {stats['height']} levels and {stats['leaves']} leaves; {stats['entries']:,} entries")
    pager.file.close()

range scan: 1000 keys, sorted: True, pages touched: 9
1,000 separate lookups: 3000 pages touched
the tree has 3 levels and 562 leaves; 100,000 entries

Reading 1,000 consecutive keys touched 9 pages: three levels to find the first leaf, then the few leaves that hold the range. Looking the same 1,000 keys up one at a time touched 3,000 pages, three per lookup. The range scan also returned the keys already sorted, with no sorting step, because the leaf order is the key order. Notice the leaf count as well: 100,000 entries fit in 562 leaves, about 178 entries per leaf, which hints at something we will measure properly in Step 9.

Step 6: Delete keys by borrowing and merging

Deleting is the hard part, because a page that loses entries can become too empty. The rule we enforce is that every page except the root must stay at least about half full. When a page drops below the minimum, the tree repairs it in one of two ways: borrow an entry from a neighbouring page that has one to spare, or merge with a neighbour when neither has spare entries. A merge removes a separator from the parent, so the parent may become too empty and need the same repair, and the repair can climb all the way to the root. If the root ends up with no separators and one child, that child becomes the new root and the tree shrinks by one level. Add these methods to the class.

# btree.py (continued)
    def delete(self, key):
        """Remove key. Returns True if it was there."""
        root = self.pager.get(self.root)
        found = self._delete(root, key)
        if not root.is_leaf and not root.keys:     # the root lost its last separator, so its only child becomes the root
            self.root = root.kids[0]
            self.pager.free(root)
            self.events["root_collapse"] += 1
        self.pager.settle()
        return found

    def _underfull(self, node):
        return len(node.keys) < (self.min_leaf if node.is_leaf else self.min_keys)

    def _delete(self, node, key):
        if node.is_leaf:
            i = bisect.bisect_left(node.keys, key)
            if i == len(node.keys) or node.keys[i] != key:
                return False
            del node.keys[i]
            del node.vals[i]
            self.pager.mark(node)
            return True
        i = bisect.bisect_right(node.keys, key)
        child = self.pager.get(node.kids[i])
        found = self._delete(child, key)
        if found and self._underfull(child):
            self._rebalance(node, i)
        return found

    def _rebalance(self, parent, i):
        child = self.pager.get(parent.kids[i])
        left = self.pager.get(parent.kids[i - 1]) if i > 0 else None
        right = self.pager.get(parent.kids[i + 1]) if i + 1 < len(parent.kids) else None
        minimum = self.min_leaf if child.is_leaf else self.min_keys   # a sibling may only lend what it can spare
        if left is not None and len(left.keys) > minimum:
            self._borrow_from_left(parent, i, left, child)
        elif right is not None and len(right.keys) > minimum:
            self._borrow_from_right(parent, i, child, right)
        elif left is not None:
            self._merge(parent, i - 1, left, child)
        else:
            self._merge(parent, i, child, right)

    def _borrow_from_left(self, parent, i, left, child):
        if child.is_leaf:
            child.keys.insert(0, left.keys.pop())
            child.vals.insert(0, left.vals.pop())
            parent.keys[i - 1] = child.keys[0]
        else:                                      # rotate through the parent
            child.keys.insert(0, parent.keys[i - 1])
            child.kids.insert(0, left.kids.pop())
            parent.keys[i - 1] = left.keys.pop()
        for node in (parent, left, child):
            self.pager.mark(node)
        self.events["borrow_left"] += 1

    def _borrow_from_right(self, parent, i, child, right):
        if child.is_leaf:
            child.keys.append(right.keys.pop(0))
            child.vals.append(right.vals.pop(0))
            parent.keys[i] = right.keys[0]
        else:
            child.keys.append(parent.keys[i])
            child.kids.append(right.kids.pop(0))
            parent.keys[i] = right.keys.pop(0)
        for node in (parent, right, child):
            self.pager.mark(node)
        self.events["borrow_right"] += 1

    def _merge(self, parent, j, left, right):
        """Fold the right child of separator j into its left neighbour and release the right page."""
        if left.is_leaf:
            left.keys += right.keys
            left.vals += right.vals
            left.nxt = right.nxt
        else:
            left.keys += [parent.keys[j]] + right.keys
            left.kids += right.kids
        del parent.keys[j]
        del parent.kids[j + 1]
        self.pager.free(right)
        self.pager.mark(left)
        self.pager.mark(parent)
        self.events["merge"] += 1

What the code does

_delete descends like a lookup, removes the key from the leaf, and then, on the way back up, asks _underfull whether the child it just changed fell below the minimum. If so, _rebalance looks at the left and right neighbours under the same parent. It prefers to borrow from the left, then from the right, and merges only when neither can lend. Borrowing from a leaf is a plain move plus a corrected separator in the parent. Borrowing between internal pages is a rotation: the parent’s separator moves down into the page that needs it, and the neighbour’s end key moves up to become the new separator. A merge folds the right page into the left one, removes the separator and child pointer from the parent, hands the emptied page back to the pager, and, for leaves, copies over the next-leaf link so the chain stays unbroken.

Run it

This demo builds a tree of 12 keys with three-entry pages, then deletes the keys in a shuffled but fixed order, and prints the tree before and after the first time each kind of repair happens. It uses a small helper that draws one line per level.

"""step06_delete.py: delete keys from a tiny tree and show the first time each kind of repair happens."""
import os
import random
import tempfile
from collections import Counter

from btree import BTree, Pager


def levels(tree):
    """One line per level: (keys) for internal nodes, [keys] for leaves."""
    rows, page_nos = [], [tree.root]
    while page_nos:
        nodes = [tree.pager.get(page_no) for page_no in page_nos]
        shown = []
        for node in nodes:
            text = " ".join(map(str, node.keys))
            shown.append(f"[{text}]" if node.is_leaf else f"({text})")
        rows.append("  ".join(shown))
        page_nos = [kid for node in nodes for kid in node.kids]
    return "\n".join(rows)


with tempfile.TemporaryDirectory(ignore_cleanup_errors=True) as folder:
    tree = BTree(Pager(os.path.join(folder, "del.db"), cache_pages=100), max_leaf=3, max_keys=3)
    for key in range(1, 13):
        tree.put(key, key)
    print("start:")
    print(levels(tree))
    order = list(range(1, 13))
    random.Random(18).shuffle(order)
    print("deleting in this order:", order)
    seen = set()
    for key in order:
        before, picture = Counter(tree.events), levels(tree)
        tree.delete(key)
        repairs = tree.events - before                 # Counter subtraction keeps only what grew
        if set(repairs) - seen:
            seen.update(repairs)
            print(f"=== delete {key}: " + ", ".join(f"{name} x{count}" if count > 1 else name for name, count in repairs.items()))
            print(picture)
            print("  becomes")
            print(levels(tree))
    print("events:", dict(tree.events))
    print("check():", tree.check())
    tree.pager.file.close()

start:
(7)
(3 5)  (9 11)
[1 2]  [3 4]  [5 6]  [7 8]  [9 10]  [11 12]
deleting in this order: [1, 12, 5, 7, 9, 10, 11, 4, 6, 8, 2, 3]
=== delete 1: merge
(7)
(3 5)  (9 11)
[1 2]  [3 4]  [5 6]  [7 8]  [9 10]  [11 12]
  becomes
(7)
(5)  (9 11)
[2 3 4]  [5 6]  [7 8]  [9 10]  [11 12]
=== delete 5: borrow_left
(7)
(5)  (9)
[2 3 4]  [5 6]  [7 8]  [9 10 11]
  becomes
(7)
(4)  (9)
[2 3]  [4 6]  [7 8]  [9 10 11]
=== delete 7: borrow_right
(7)
(4)  (9)
[2 3]  [4 6]  [7 8]  [9 10 11]
  becomes
(7)
(4)  (10)
[2 3]  [4 6]  [8 9]  [10 11]
=== delete 9: merge x2, root_collapse
(7)
(4)  (10)
[2 3]  [4 6]  [8 9]  [10 11]
  becomes
(4 7)
[2 3]  [4 6]  [8 10 11]
events: {'split_leaf': 5, 'new_root': 2, 'split_internal': 1, 'merge': 6, 'borrow_left': 1, 'borrow_right': 1, 'root_collapse': 2}
check(): {'height': 1, 'leaves': 1, 'internals': 0, 'entries': 0, 'leaf_fill': 0.0}

Read the pictures one repair at a time. Deleting 1 leaves the leaf [2] with one entry, below the minimum of two, and its only neighbour [3 4] has nothing to spare, so the two merge into [2 3 4] and the separator 3 disappears from the parent. Deleting 5 shrinks [5 6] to [6], and the left neighbour [2 3 4] can spare its largest key, so 4 is borrowed across and the separator in the parent changes from 5 to 4. Deleting 7 does the mirror image: [7 8] becomes [8], the right neighbour [9 10 11] lends its smallest key, and the separator becomes 10. Deleting 9 is the big one: two merges ripple upward until the root has no separators left, and the root is replaced by its only child, so the tree goes from three levels to two (root_collapse). At the end the tree is empty, one leaf, height 1.

Not every production tree merges: PostgreSQL does not

What we just wrote is the textbook algorithm, and PostgreSQL does not use it for partly-full pages. Its source tree documents the choice in the README of its btree code: “We consider deleting an entire page from the btree only when it’s become completely empty of items.” The reason given is concurrency: “Merging partly-full pages would allow better space reuse, but it seems impractical to move existing data items left or right to make this happen”, because a scan moving in the opposite direction could miss the items. Our tree has no concurrent readers, so it can afford the textbook rule.

Step 7: Prove that the tree works

A tree that returns the right answer for the keys you happened to try is not necessarily correct. We will check it in three layers: an invariant checker, a test suite that compares the tree with a Python dictionary, and a deliberate attack on the test suite.

Layer 1: an invariant checker

Add check to the class. It walks the whole tree and asserts every rule a valid B+tree must obey, then returns simple statistics that we will reuse in the measurements.

# btree.py (continued)
    def check(self):
        """Walk the whole tree, assert every rule, and return simple statistics."""
        pager, seen, leaves, depths = self.pager, set(), [], set()
        internals = 0

        def walk(page_no, low, high, depth, right_edge):
            nonlocal internals
            assert page_no not in seen, f"page {page_no} is reachable twice"
            seen.add(page_no)
            node = pager.get(page_no)
            keys, is_root = node.keys, page_no == self.root
            assert all(a < b for a, b in zip(keys, keys[1:])), f"page {page_no}: keys are not strictly increasing"
            assert all((low is None or k >= low) and (high is None or k < high) for k in keys), \
                f"page {page_no}: a key lies outside the range its parent promises"
            if node.is_leaf:
                assert len(node.vals) == len(keys), f"page {page_no}: keys and values differ in length"
                assert len(keys) <= self.max_leaf, f"page {page_no}: leaf is over capacity"
                packed_edge = right_edge and self.append_fill   # the right edge may be sparse after packed appends
                assert is_root or packed_edge or len(keys) >= self.min_leaf, f"page {page_no}: leaf is under-full"
                leaves.append(node)
                depths.add(depth)
                return
            internals += 1
            assert len(node.kids) == len(keys) + 1, f"page {page_no}: an internal node needs one more child than keys"
            assert len(keys) <= self.max_keys, f"page {page_no}: internal node is over capacity"
            assert len(keys) >= (1 if is_root else self.min_keys), f"page {page_no}: internal node is under-full"
            bounds = [low, *keys, high]
            for i, kid in enumerate(node.kids):
                walk(kid, bounds[i], bounds[i + 1], depth + 1, right_edge and i == len(node.kids) - 1)

        walk(self.root, None, None, 0, True)
        assert len(depths) == 1, f"leaves sit at different depths: {sorted(depths)}"
        for left, right in zip(leaves, leaves[1:] + [None]):
            assert left.nxt == (right.page_no if right else 0), f"leaf p{left.page_no}: the next-leaf link is wrong"
        if pager.fresh:
            assert len(seen) + len(pager.free_list) == pager.n_pages - 1, "some pages are neither in the tree nor free"
        entries = sum(len(leaf.keys) for leaf in leaves)
        pager.settle()
        return {"height": depths.pop() + 1, "leaves": len(leaves), "internals": internals, "entries": entries,
                "leaf_fill": entries / (len(leaves) * self.max_leaf)}

The rules it enforces are: keys strictly increasing inside every page; every key inside the range its parent promises; sizes within the maximum and, except at the root, at least the minimum; one more child than keys in every internal page; every leaf at the same depth; the leaf chain visiting every leaf exactly once in key order; and, for a tree created in the current session, no page that is neither in the tree nor on the free list (a reopened file forgets its free list). The right-edge exception in the leaf-size rule is for the append_fill option in Step 9. To see the checker work, this script damages a healthy tree in five different ways.

"""step07_check.py: break a healthy tree in five different ways and watch check() notice each one."""
import os
import tempfile

from btree import LEAF, BTree, Pager


def healthy(folder, name):
    tree = BTree(Pager(os.path.join(folder, name), cache_pages=100), max_leaf=4, max_keys=4)
    for key in range(1, 41):
        tree.put(key, key)
    tree.check()
    return tree


def first_leaf(tree):
    node = tree.pager.get(tree.root)
    while not node.is_leaf:
        node = tree.pager.get(node.kids[0])
    return node


def swap_two_keys(tree):
    leaf = first_leaf(tree)
    leaf.keys[0], leaf.keys[1] = leaf.keys[1], leaf.keys[0]


def raise_a_separator(tree):
    root = tree.pager.get(tree.root)
    root.keys[0] += 3


def cut_the_leaf_chain(tree):
    first_leaf(tree).nxt = 0


def drop_a_value(tree):
    first_leaf(tree).vals.pop()


def lose_a_page(tree):
    tree.pager.allocate(LEAF)          # allocated, but never linked into the tree


with tempfile.TemporaryDirectory(ignore_cleanup_errors=True) as folder:
    for number, damage in enumerate((swap_two_keys, raise_a_separator, cut_the_leaf_chain, drop_a_value, lose_a_page)):
        tree = healthy(folder, f"c{number}.db")
        damage(tree)
        try:
            tree.check()
            print(f"{damage.__name__}: NOT NOTICED")
        except AssertionError as error:
            print(f"{damage.__name__}: {error}")
        tree.pager.file.close()

swap_two_keys: page 1: keys are not strictly increasing
raise_a_separator: page 5: a key lies outside the range its parent promises
cut_the_leaf_chain: leaf p1: the next-leaf link is wrong
drop_a_value: page 1: keys and values differ in length
lose_a_page: some pages are neither in the tree nor free

Each kind of damage produces a different message, and none goes unnoticed. That matters because the checker is what will make the next layer powerful.

Layer 2: compare with a dictionary

The simplest trustworthy specification of a key-value store is a Python dict. The first test applies 800 random inserts, deletes and lookups to a tiny tree and a dictionary side by side, compares every answer, and calls check every 40 steps. It runs with 25 different random seeds and with and without append_fill. The other tests cover range scans against a sorted list, closing and reopening the file, the page codec, the cold-lookup cost from Step 3, sorted inserts, packed appends, replacing a value, and growing a tree to 400 keys and then deleting all of them while checking after every deletion. That last test also asserts that every kind of restructuring happened at least once, so the suite cannot pass by accident without exercising borrows and merges. Save this as test_btree.py.

"""test_btree.py: the tests that keep the B+tree honest."""
import random

import pytest

from btree import INTERNAL, LEAF, BTree, Node, Pager


def small_tree(tmp_path, name="t.db", cache_pages=8, **options):
    """A tree whose nodes hold at most 4 entries, so splits and merges happen all the time."""
    return BTree(Pager(str(tmp_path / name), cache_pages=cache_pages), max_leaf=4, max_keys=4, **options)


@pytest.mark.parametrize("append_fill", [None, 1.0])
@pytest.mark.parametrize("seed", range(25))
def test_random_operations_match_a_dict(tmp_path, seed, append_fill):
    rng = random.Random(seed)
    tree, model = small_tree(tmp_path, append_fill=append_fill), {}
    for step in range(800):
        key, roll = rng.randrange(120), rng.random()
        if roll < 0.55:
            assert tree.put(key, step) == (key not in model)
            model[key] = step
        elif roll < 0.95:
            assert tree.delete(key) == (key in model)
            model.pop(key, None)
        else:
            assert tree.get(key, -1) == model.get(key, -1)
        if step % 40 == 0:
            tree.check()
    assert tree.check()["entries"] == len(model)
    assert list(tree.items()) == sorted(model.items())


def test_growing_then_emptying_visits_every_restructuring_path(tmp_path):
    rng = random.Random(11)
    tree = small_tree(tmp_path)
    keys = rng.sample(range(10_000), 400)
    for key in keys:
        tree.put(key, key)
    assert tree.check()["entries"] == 400
    rng.shuffle(keys)
    for key in keys:
        assert tree.delete(key)
        tree.check()
    assert tree.check() == {"height": 1, "leaves": 1, "internals": 0, "entries": 0, "leaf_fill": 0.0}
    for name in ("split_leaf", "split_internal", "new_root", "borrow_left", "borrow_right", "merge", "root_collapse"):
        assert tree.events[name] > 0, name


def test_range_scans_match_a_sorted_model(tmp_path):
    rng = random.Random(7)
    tree = small_tree(tmp_path)
    keys = rng.sample(range(10_000), 500)
    for key in keys:
        tree.put(key, key * 2)
    ordered = sorted(keys)
    for _ in range(100):
        low = rng.randrange(10_000)
        high = low + rng.randrange(1, 2_000)
        assert list(tree.items(low, high)) == [(k, k * 2) for k in ordered if low <= k < high]
    assert list(tree.items(high=0)) == []


def test_flush_and_reopen_returns_the_same_tree(tmp_path):
    path, rng, model = str(tmp_path / "p.db"), random.Random(3), {}
    tree = BTree(Pager(path, cache_pages=4), max_leaf=4, max_keys=4)
    for step in range(400):
        key = rng.randrange(1000)
        tree.put(key, step)
        model[key] = step
    for key in rng.sample(sorted(model), 150):
        tree.delete(key)
        del model[key]
    tree.flush()
    tree.pager.file.close()
    again = BTree(Pager(path, cache_pages=4))
    assert (again.max_leaf, again.max_keys) == (4, 4)
    assert list(again.items()) == sorted(model.items())
    again.check()


def test_page_codec_round_trips_and_refuses_overflow():
    leaf = Node(1, LEAF)
    leaf.keys, leaf.vals, leaf.nxt = [1, 5, 9], [10, 50, 90], 7
    inner = Node(2, INTERNAL)
    inner.keys, inner.kids = [5, 9], [1, 3, 4]
    for node in (leaf, inner):
        page = node.encode(4096)
        assert len(page) == 4096
        assert Node.decode(node.page_no, page).__dict__ == node.__dict__
    leaf.keys, leaf.vals = list(range(256)), list(range(256))
    with pytest.raises(ValueError):
        leaf.encode(4096)


def test_a_cold_lookup_reads_one_page_per_level(tmp_path):
    tree = BTree(Pager(str(tmp_path / "c.db"), cache_pages=0), max_leaf=8, max_keys=8)
    for key in range(2000):
        tree.put(key, key)
    height = tree.check()["height"]
    assert height >= 3
    tree.pager.gets = tree.pager.reads = 0
    assert tree.get(1234) == 1234
    assert tree.pager.gets == tree.pager.reads == height


@pytest.mark.parametrize("order", ["ascending", "descending"])
def test_sorted_inserts_keep_every_rule(tmp_path, order):
    tree = small_tree(tmp_path)
    for key in (range(300) if order == "ascending" else range(299, -1, -1)):
        tree.put(key, key)
    tree.check()
    assert [k for k, _ in tree.items()] == list(range(300))


def test_packed_appends_fill_leaves_but_plain_splits_leave_them_half_empty(tmp_path):
    packed = BTree(Pager(str(tmp_path / "a.db"), cache_pages=10**6), append_fill=1.0)
    plain = BTree(Pager(str(tmp_path / "b.db"), cache_pages=10**6))
    for key in range(20_000):
        packed.put(key, key)
        plain.put(key, key)
    assert packed.check()["leaf_fill"] > 0.99
    assert 0.49 < plain.check()["leaf_fill"] < 0.52


def test_put_replaces_a_value_and_rejects_out_of_range_numbers(tmp_path):
    tree = small_tree(tmp_path)
    assert tree.put(5, 1) is True
    assert tree.put(5, 2) is False
    assert tree.get(5) == 2 and tree.get(6, "none") == "none"
    for bad in (-1, 1 << 64):
        with pytest.raises(ValueError):
            tree.put(bad, 0)

Run the suite with python -m pytest -q.

........................................................... [100%]
59 passed in 1.38s

All 59 tests pass. The pytest timing will differ on your machine.

Layer 3: plant bugs and see whether the tests notice

A passing suite proves little until you have seen it fail. This script copies btree.py to a scratch folder twelve times, plants one realistic bug in each copy by replacing a line, and runs the whole suite against it. Save it as mutants.py and run python mutants.py.

"""mutants.py: plant one bug at a time in a copy of btree.py and see whether the tests notice."""
import pathlib
import re
import shutil
import subprocess
import sys
import tempfile
import textwrap

LAB = pathlib.Path(__file__).parent
SHORT = {
    "test_random_operations_match_a_dict": "random-ops",
    "test_growing_then_emptying_visits_every_restructuring_path": "grow-and-empty",
    "test_range_scans_match_a_sorted_model": "range-scans",
    "test_flush_and_reopen_returns_the_same_tree": "reopen",
    "test_page_codec_round_trips_and_refuses_overflow": "codec",
    "test_a_cold_lookup_reads_one_page_per_level": "cold-lookup",
    "test_sorted_inserts_keep_every_rule": "sorted-inserts",
    "test_packed_appends_fill_leaves_but_plain_splits_leave_them_half_empty": "packed-appends",
    "test_put_replaces_a_value_and_rejects_out_of_range_numbers": "put-replace",
}
MUTANTS = [
    ("equal key goes to the left child", "bisect.bisect_right(node.keys, key)", "bisect.bisect_left(node.keys, key)", 3),
    ("leaf split forgets the new leaf link", "right.nxt, leaf.nxt = leaf.nxt, right.page_no", "right.nxt = leaf.nxt", 1),
    ("separator taken from the left leaf", "return right.keys[0], right.page_no", "return leaf.keys[-1], right.page_no", 1),
    ("internal split keeps the pushed-up key", "node.keys[mid + 1:], node.keys[:mid]", "node.keys[mid:], node.keys[:mid]", 1),
    ("delete never rebalances", "            self._rebalance(node, i)", "            pass", 1),
    ("borrow from left leaves a stale separator", "            parent.keys[i - 1] = child.keys[0]", "            pass", 1),
    ("borrow from right takes the wrong entry", "child.keys.append(right.keys.pop(0))", "child.keys.append(right.keys.pop())", 1),
    ("merge drops the next-leaf link", "            left.nxt = right.nxt", "            pass", 1),
    ("root never collapses", "if not root.is_leaf and not root.keys:", "if False:", 1),
    ("merged page is never released", "        self.pager.free(right)", "        pass", 1),
    ("replace forgets to mark the page dirty", "                node.vals[i] = value\n                self.pager.mark(node)\n",
     "                node.vals[i] = value\n", 1),
    ("eviction forgets to write dirty pages", "                self._write(node)", "                pass", 1),
]

source = (LAB / "btree.py").read_text(encoding="utf-8")
caught = 0
for name, old, new, count in MUTANTS:
    assert source.count(old) == count, (name, source.count(old))
    with tempfile.TemporaryDirectory(ignore_cleanup_errors=True) as folder:
        shutil.copy(LAB / "test_btree.py", folder)
        (pathlib.Path(folder) / "btree.py").write_text(source.replace(old, new), encoding="utf-8")
        run = subprocess.run([sys.executable, "-m", "pytest", "-q", "--tb=no", "-p", "no:cacheprovider", "."],
                             capture_output=True, text=True, cwd=folder, timeout=600)
    failed = re.findall(r"^FAILED \S+?::([^\s\[]+)", run.stdout, re.M)
    total = re.search(r"(\d+) failed", run.stdout)
    caught += run.returncode != 0
    names = ", ".join(sorted({SHORT[name] for name in failed})) or "-"
    print(f"{'CAUGHT' if run.returncode else 'SURVIVED'}  {name} ({total.group(1) if total else 0} failing tests)")
    print(textwrap.fill(names, width=100, initial_indent=" " * 10, subsequent_indent=" " * 10, break_on_hyphens=False))
print(f"{caught} of {len(MUTANTS)} planted bugs were caught")

CAUGHT  equal key goes to the left child (52 failing tests)
          grow-and-empty, random-ops, reopen
CAUGHT  leaf split forgets the new leaf link (57 failing tests)
          cold-lookup, grow-and-empty, packed-appends, random-ops, range-scans, reopen,
          sorted-inserts
CAUGHT  separator taken from the left leaf (57 failing tests)
          cold-lookup, grow-and-empty, packed-appends, random-ops, range-scans, reopen,
          sorted-inserts
CAUGHT  internal split keeps the pushed-up key (56 failing tests)
          cold-lookup, grow-and-empty, random-ops, range-scans, reopen, sorted-inserts
CAUGHT  delete never rebalances (52 failing tests)
          grow-and-empty, random-ops, reopen
CAUGHT  borrow from left leaves a stale separator (52 failing tests)
          grow-and-empty, random-ops, reopen
CAUGHT  borrow from right takes the wrong entry (52 failing tests)
          grow-and-empty, random-ops, reopen
CAUGHT  merge drops the next-leaf link (52 failing tests)
          grow-and-empty, random-ops, reopen
CAUGHT  root never collapses (6 failing tests)
          grow-and-empty, random-ops
CAUGHT  merged page is never released (51 failing tests)
          grow-and-empty, random-ops
CAUGHT  replace forgets to mark the page dirty (51 failing tests)
          random-ops, reopen
CAUGHT  eviction forgets to write dirty pages (56 failing tests)
          cold-lookup, grow-and-empty, random-ops, range-scans, reopen, sorted-inserts
12 of 12 planted bugs were caught

All twelve planted bugs were caught. Each entry shows how many of the 59 tests it broke and which test functions did the catching. Notice how different the bugs look to the suite. Leaf split forgets the new leaf link breaks seven of the nine test functions (57 of the 59 tests), because so many behaviours depend on the chain. Root never collapses breaks only six tests, found by just two test functions, the ones that delete enough keys to empty the tree. Replace forgets to mark the page dirty is invisible while everything stays in the cache and shows up only after the page has been evicted and read back, which both the random test (its cache holds only 8 pages) and the reopen test force. If a planted bug had survived, I would have written a new test before going on.

Step 8: Count the pages one lookup touches

Now we can use the tree for what it was built for. This script builds a tree of one million random keys with full-size 4,096-byte pages, flushes it to a file, reopens it, and measures lookups with no cache and with a 64-page cache. For comparison it also counts the pages that a binary search of a sorted file of the same records would touch, counting each page once because probes inside one page cost no extra read.

"""step08_scale.py: how many pages does one lookup touch in a tree of real 4 KiB pages?"""
import os
import random
import tempfile

from btree import BTree, Pager

N = 1_000_000
PER_PAGE = 255          # 16-byte records in a 4,096-byte page after a 16-byte header


def binary_search_pages(n, target):
    """Distinct pages touched when binary-searching a sorted file of n records for record number target."""
    low, high, touched = 0, n - 1, set()
    while low <= high:
        mid = (low + high) // 2
        touched.add(mid // PER_PAGE)
        if mid == target:
            break
        low, high = (mid + 1, high) if mid < target else (low, mid - 1)
    return len(touched)


def lookups(path, cache_pages, sample, warmup=0):
    pager = Pager(path, cache_pages=cache_pages)
    tree = BTree(pager)
    for key in sample[:warmup]:
        tree.get(key)
    pager.gets = pager.reads = 0
    for key in sample[warmup:]:
        tree.get(key)
    pager.file.close()
    count = len(sample) - warmup
    return pager.gets / count, pager.reads / count


rng = random.Random(1)
keys = rng.sample(range(1 << 40), N)
with tempfile.TemporaryDirectory(ignore_cleanup_errors=True) as folder:
    path = os.path.join(folder, "big.db")
    tree = BTree(Pager(path, cache_pages=10**7))      # everything stays in memory while we build
    for key in keys:
        tree.put(key, key)
    stats = tree.check()
    tree.flush()
    tree.pager.file.close()
    print(f"{N:,} entries: {stats['height']} levels, {stats['leaves']:,} leaves, {stats['internals']} internal pages")
    print(f"file size: {os.path.getsize(path) / 2**20:.1f} MiB; full-page capacity: 255 entries per leaf")
    leaf_avg = stats["entries"] / stats["leaves"]
    fan_out = (stats["leaves"] + stats["internals"] - 1) / stats["internals"]
    print(f"average entries per leaf {leaf_avg:.1f}, average children per internal page {fan_out:.1f}")

    sample = rng.sample(keys, 3000)
    cold = lookups(path, 0, sample[:1000])
    warm = lookups(path, 64, sample, warmup=2000)
    sorted_pages = -(-N // PER_PAGE)
    binary = sum(binary_search_pages(N, rng.randrange(N)) for _ in range(2000)) / 2000
    print()
    print(f"{'method':<42}{'pages read per lookup':>22}")
    print(f"{'linear scan of the sorted file (worst)':<42}{sorted_pages:>22,}")
    print(f"{'binary search of the sorted file':<42}{binary:>22.1f}")
    print(f"{'B+tree, no cache (logical = physical)':<42}{cold[0]:>22.1f}")
    print(f"{'B+tree, 64-page cache, physical reads':<42}{warm[1]:>22.2f}")

    print()
    print("levels needed at the measured shape:")
    for n in (10**3, 10**6, 10**9, 10**12):
        height = 1
        while leaf_avg * fan_out ** (height - 1) < n:
            height += 1
        print(f"{n:>18,} entries -> {height} levels")

1,000,000 entries: 3 levels, 5,647 leaves, 33 internal pages
file size: 22.2 MiB; full-page capacity: 255 entries per leaf
average entries per leaf 177.1, average children per internal page 172.1

method                                     pages read per lookup
linear scan of the sorted file (worst)                     3,922
binary search of the sorted file                            11.9
B+tree, no cache (logical = physical)                        3.0
B+tree, 64-page cache, physical reads                       1.28

levels needed at the measured shape:
             1,000 entries -> 2 levels
         1,000,000 entries -> 3 levels
     1,000,000,000 entries -> 5 levels
 1,000,000,000,000 entries -> 6 levels

A million entries fit in a three-level tree with 5,647 leaves and only 33 internal pages, in a 22.2 MiB file. The leaves hold 177.1 entries on average, which is about 69 percent of the 255 they could hold (more on that in Step 9), and each internal page has 172.1 children on average. A lookup with no cache reads exactly 3.0 pages, one per level. Binary search over a sorted file of the same data touches 11.9 pages, and scanning it would read up to 3,922. With a 64-page cache the physical reads fall to 1.28 per lookup, because the root and the other internal pages are used constantly, so most lookups need a real read only for the leaf. The average is above 1 because leaf pages crowd some of the 33 internal pages out of such a small cache. PostgreSQL’s documentation says the same thing about its own indexes: “Typically, over 99% of all pages are leaf pages.” Here 5,647 of 5,680 pages are leaves, which is 99.4 percent.

The last four lines use the measured shape to estimate how deep bigger trees get. At 177 entries per leaf and 172 children per page, four levels hold about 900 million entries by my arithmetic, so a billion entries needs five levels and a trillion needs six. Height grows with the logarithm of the table size, which is why adding a thousand times more data adds only one or two page reads per lookup.

Step 9: Measure how full the pages get

A page that is 50 percent empty still costs a whole page of disk space and a whole page of cache. How full the leaves are depends on the order in which keys arrive, and the simplest split rule, cut in half, has a famous consequence. A recent paper on B-tree fragmentation credits the result to Yao’s 1978 analysis and states it this way: “evenly splitting the leaves of a B-tree under uniform insertions results in an average fill of ln 2 ≈ 69%”. (The paper is Bounding the Fragmentation of B-trees Subject to Batched Insertions, arXiv:2603.12211.) Let us see whether our tree agrees.

Random inserts

The first part of this script inserts one million random keys one by one, records the leaf fill every 1,000 inserts, and summarizes it for three random seeds in two size windows. The second part builds five 200,000-entry trees with different insert patterns. The second part uses the append_fill option that we added in Step 4, so look at _split_leaf again: when the new key lands at the end of the right-most leaf and append_fill is set, the page is cut so that the left page keeps that fraction of its capacity and the new key starts a fresh page.

"""step09_fill.py: how full do leaf pages get? Random inserts, sorted inserts, and packed appends."""
import itertools
import math
import os
import random
import tempfile

from btree import BTree, Pager

counter = itertools.count()


def build(keys, folder, **options):
    tree = BTree(Pager(os.path.join(folder, f"t{next(counter)}.db"), cache_pages=10**7), **options)
    for key in keys:
        tree.put(key, key)
    stats = tree.check()
    tree.pager.file.close()
    return stats


def trajectory(folder, seed, limit=1_000_000, every=1_000):
    """Insert random keys one by one and record the leaf fill every `every` inserts."""
    tree = BTree(Pager(os.path.join(folder, f"g{next(counter)}.db"), cache_pages=10**7))
    fills = {}
    for n, key in enumerate(random.Random(seed).sample(range(1 << 40), limit), 1):
        tree.put(key, key)
        if n % every == 0:
            fills[n] = n / ((1 + tree.events["split_leaf"]) * tree.max_leaf)   # no merges, so leaves = splits + 1
    assert tree.check()["leaves"] == 1 + tree.events["split_leaf"]
    tree.pager.file.close()
    return fills


with tempfile.TemporaryDirectory(ignore_cleanup_errors=True) as folder:
    print(f"ln 2 = {math.log(2):.4f}")
    print()
    print("random inserts: leaf fill sampled every 1,000 inserts, three seeds")
    print(f"{'seed':>6}{'sizes':>16}{'min':>8}{'mean':>8}{'max':>8}")
    runs = [trajectory(folder, seed) for seed in range(3)]
    for seed, fills in enumerate(runs):
        for low, high in ((10_000, 100_000), (100_000, 1_000_000)):
            window = [fill for n, fill in fills.items() if low <= n <= high]
            print(f"{seed:>6}{f'{low // 1000}k to {high // 1000}k':>16}{min(window):>8.3f}{sum(window) / len(window):>8.3f}{max(window):>8.3f}")

    n = 200_000
    shuffled = random.Random(9).sample(range(1 << 40), n)
    cases = [
        ("random order, split in half", shuffled, {}),
        ("ascending, split in half", range(n), {}),
        ("descending, split in half", range(n - 1, -1, -1), {}),
        ("ascending, packed appends 100%", range(n), {"append_fill": 1.0}),
        ("ascending, packed appends 90%", range(n), {"append_fill": 0.9}),
    ]
    print()
    print(f"{n:,} entries, leaf capacity 255, 4 KiB pages")
    print(f"{'insert pattern':<34}{'leaves':>8}{'leaf fill':>11}{'levels':>8}{'size (MiB)':>12}")
    for label, keys, options in cases:
        stats = build(keys, folder, **options)
        pages = stats["leaves"] + stats["internals"]
        print(f"{label:<34}{stats['leaves']:>8,}{stats['leaf_fill']:>11.3f}{stats['height']:>8}{pages * 4096 / 2**20:>12.1f}")
    print(f"{'perfectly packed (200,000 / 255)':<34}{-(-n // 255):>8,}{n / (-(-n // 255) * 255):>11.3f}")

ln 2 = 0.6931

random inserts: leaf fill sampled every 1,000 inserts, three seeds
  seed           sizes     min    mean     max
     0     10k to 100k   0.654   0.696   0.784
     0   100k to 1000k   0.659   0.696   0.733
     1     10k to 100k   0.609   0.695   0.832
     1   100k to 1000k   0.641   0.700   0.767
     2     10k to 100k   0.601   0.694   0.819
     2   100k to 1000k   0.640   0.700   0.755

The mean fill is between 0.694 and 0.700 in every row, within about one percent of ln 2, which is 0.6931. A single snapshot is another matter. The fill swings from as low as 0.601 to as high as 0.832 in the 10,000 to 100,000 window and from 0.640 to 0.767 above that, so the 69 percent figure is an average over many sizes, not a number every tree has at every moment. My guess is that leaves created at about the same time also fill and split at about the same time, but I did not test that explanation.

Sorted inserts and packed appends

200,000 entries, leaf capacity 255, 4 KiB pages
insert pattern                      leaves  leaf fill  levels  size (MiB)
random order, split in half          1,078      0.728       3         4.2
ascending, split in half             1,562      0.502       3         6.2
descending, split in half            1,562      0.502       3         6.2
ascending, packed appends 100%         785      0.999       3         3.1
ascending, packed appends 90%          870      0.902       3         3.4
perfectly packed (200,000 / 255)       785      0.999

Random order gives 0.728 at this particular size, above the long-run average of about 0.70, and a tree of 1,078 leaves. Ascending and descending keys are much worse, 0.502 with 1,562 leaves, which is 45 percent more pages for the same data. The reason is easy to see in ascending order. Every new key is larger than all the others, so it always lands in the right-most leaf. When that leaf overflows it is cut in half, and the left half, with 128 of 255 entries, never receives another key. Every leaf except the last stays half full forever.

The fix is a special case for appends, and the two bottom rows show it. With append_fill=1.0 the left page keeps all 255 entries and the new key starts a new page, so the leaves are 0.999 full and the tree has 785 leaves, exactly the number a perfectly packed file would need. With 0.9 the leaves are 0.902 full and the tree has 870. Real systems do this. The PostgreSQL documentation for CREATE INDEX says that for B-trees “leaf pages are filled to this percentage during initial index builds, and also when extending the index at the right (adding new largest key values)”, and that “B-trees use a default fillfactor of 90”. A fill factor below 100 deliberately leaves room, so that later random inserts do not split pages right away.

Common mistake: leaving the right edge sparse and then enforcing the minimum

A packed append leaves the new right-most leaf with a single entry, far below the usual minimum. That is fine, because the next appends fill it, but the invariant checker must know about it. That is the right-edge exception in check, and it applies only when append_fill is set.

Step 10: Compare with a real SQLite database file

Our tree says three things: random inserts leave pages about 70 percent full, ascending inserts leave them half full unless the tree has an append rule, and an append rule packs them. Does a real database behave the same way? SQLite makes it easy to find out, because its file format is public and simple. SQLite also has a virtual table called dbstat that reports the disk space used, but it is “available on all database connections when SQLite is built using the SQLITE_ENABLE_DBSTAT_VTAB compile-time option”, and the SQLite bundled with this Python build was not (I tried it and got no such table: dbstat). So we will read the file ourselves, which is the more educational route anyway.

Reading b-tree pages from the file

The file format document tells us what to look for. The page size is a two-byte number at offset 16 of the file, and a value of 1 means 65,536. Page 1 starts with a 100-byte database header. Every b-tree page starts with a flag byte: 0x05 is an interior table page and 0x0d is a leaf table page. The document says “The b-tree page header is 8 bytes in size for leaf pages and 12 bytes for interior pages.” At offset 3 there is a two-byte count of cells, at offset 5 the start of the cell content area, at offset 1 the start of a chain of free blocks, and at offset 7 a count of fragmented free bytes. An interior page’s right-most child pointer is at offset 8, and after the header comes an array of two-byte offsets, one per cell. Each interior table cell begins with a 4-byte left child page number. From these facts we can compute how much of each page is free. Save this module as sqlite_pages.py.

"""sqlite_pages.py: walk the b-tree pages of a SQLite database file and report depth and page fill."""
import sqlite3
import struct

INTERIOR_KINDS = (0x02, 0x05)   # 0x02 index interior, 0x05 table interior; leaves are 0x0A and 0x0D


def page_facts(data, page_size, number):
    """Return (kind, cell count, fraction of the page in use, child page numbers) for one b-tree page."""
    start = (number - 1) * page_size
    base = 100 if number == 1 else 0          # page 1 begins with the 100-byte database header
    kind = data[start + base]
    header = 12 if kind in INTERIOR_KINDS else 8
    first_free, cells, content, fragments = struct.unpack_from(">HHHB", data, start + base + 1)
    content = content or 65536                # a stored 0 means 65536
    free = content - (base + header + 2 * cells) + fragments
    while first_free:                         # add up the chain of free blocks inside the page
        first_free, size = struct.unpack_from(">HH", data, start + first_free)
        free += size
    children = []
    if kind in INTERIOR_KINDS:
        pointers = struct.unpack_from(f">{cells}H", data, start + base + header)
        children = [struct.unpack_from(">I", data, start + pointer)[0] for pointer in pointers]
        children.append(struct.unpack_from(">I", data, start + base + 8)[0])   # the right-most child
    return kind, cells, 1 - free / (page_size - base), children


def analyze(path, table):
    con = sqlite3.connect(path)
    root = con.execute("select rootpage from sqlite_schema where name = ?", (table,)).fetchone()[0]
    con.close()
    data = open(path, "rb").read()
    page_size = struct.unpack_from(">H", data, 16)[0]
    page_size = 65536 if page_size == 1 else page_size
    leaves, interior, depths = [], 0, set()

    def walk(number, depth):
        nonlocal interior
        kind, cells, fill, children = page_facts(data, page_size, number)
        if not children:
            leaves.append((cells, fill))
            depths.add(depth)
            return
        interior += 1
        for child in children:
            walk(child, depth + 1)

    walk(root, 1)
    assert len(depths) == 1, "all leaves of a b-tree sit at the same depth"
    return {"page_size": page_size, "file_pages": len(data) // page_size, "levels": depths.pop(),
            "interior": interior, "leaves": len(leaves),
            "rows": sum(cells for cells, _ in leaves),
            "mean_fill": sum(fill for _, fill in leaves) / len(leaves)}

page_facts decodes one page and analyze finds the table’s root page in sqlite_schema, walks every page below it, checks that all leaves sit at the same depth, and reports levels, page counts and the average fraction of each leaf page that is in use. It uses only the facts above. Now build three databases with 200,000 rows each and look at them.

"""step10_sqlite.py: the same experiment on a real database, SQLite table b-trees read straight from the file."""
import os
import random
import sqlite3
import tempfile

from sqlite_pages import analyze

N = 200_000


def report(label, info):
    per_leaf = info["rows"] / info["leaves"]
    print(f"{label:<30}{info['levels']:>7}{info['interior']:>10}{info['leaves']:>8,}{per_leaf:>12.1f}{info['mean_fill']:>11.3f}")


print("SQLite", sqlite3.sqlite_version, "| rows:", f"{N:,}")
print(f"{'insert pattern':<30}{'levels':>7}{'interior':>10}{'leaves':>8}{'rows/leaf':>12}{'leaf fill':>11}")
with tempfile.TemporaryDirectory(ignore_cleanup_errors=True) as folder:
    random_ids = random.Random(1).sample(range(1, 1 << 40), N)
    for label, ids in (("random rowids", random_ids), ("ascending rowids", range(1, N + 1))):
        path = os.path.join(folder, label.split()[0] + ".db")
        con = sqlite3.connect(path)
        con.execute("create table t (id integer primary key, v integer)")
        con.executemany("insert into t values (?, ?)", ((k, k % 1000) for k in ids))
        con.commit()
        con.close()
        page_size = analyze(path, "t")["page_size"]
        report(label, analyze(path, "t"))
        if label.startswith("random"):
            con = sqlite3.connect(path)
            con.execute("vacuum")
            con.close()
            report("random rowids, then VACUUM", analyze(path, "t"))
    print("page size:", page_size, "bytes")

SQLite 3.50.4 | rows: 200,000
insert pattern                 levels  interior  leaves   rows/leaf  leaf fill
random rowids                       3         4     737       271.4      0.919
random rowids, then VACUUM          3         3     679       294.6      0.997
ascending rowids                    3         3     529       378.1      0.998
page size: 4096 bytes

The rows are 200,000 in a table whose key is the row id. Inserting in ascending order produces leaves that are 0.998 full, just like our packed appends. After a VACUUM, which rewrites the table, the random-order database also becomes 0.997 full. Random row ids give 0.919, much better than our 0.70. The columns show why you must compare fill and not rows per leaf: the random row ids are large numbers that need more bytes in SQLite’s variable-length integer encoding than the small row ids 1 to 200,000, so fewer rows fit on a page (271.4 against 378.1). Divide each count by its fill and you get about 295 rows per full page in both the random and the vacuumed database, which is a useful sanity check on the page reader.

Why SQLite beats the simple rule

The SQLite source explains both results in comments. For appends: “Instead of trying to balance the 3 right-most leaf pages, just add a new page to the right-hand side and put the one new entry in that page.” That is our append_fill=1.0. For everything else, the comment on the routine that rebalances a page says it “redistributes cells on the iParentIdx’th child of pParent (hereafter “the page”) and up to 2 siblings so that all pages have about the same amount of free space”, and that the number of siblings is changed “in an effort to keep pages nearly full but not over full”. Instead of cutting an overflowing page in half, SQLite spreads the cells over the page and its neighbours, so pages end up fuller. That is consistent with the 0.919 we measured, but I did not change SQLite’s algorithm to prove it, so treat it as the design explanation, not as a controlled experiment. The lesson for your own tree is the same: the plain split-in-half rule gives about 70 percent, and production systems add append and redistribution rules to do better.

Step 11: Measure what writes cost

The last measurement is about writes. Every insert changes at least one leaf, and a leaf is a whole 4,096-byte page. This script inserts 100,000 random keys, and then the same keys in ascending order, using caches of 0, 16, 128 and 1,024 pages, and counts how many pages the pager writes to the file.

"""step11_writes.py: how many pages reach the file for 100,000 inserts, for different cache sizes?"""
import os
import random
import tempfile

from btree import BTree, Pager

N = 100_000
random_keys = random.Random(2).sample(range(1 << 40), N)
with tempfile.TemporaryDirectory(ignore_cleanup_errors=True) as folder:
    print(f"{N:,} inserts of 16 bytes each = {N * 16 / 2**20:.1f} MiB of new data")
    print(f"{'order':<10}{'cache pages':>12}{'pages written':>15}{'per insert':>12}{'MiB written':>13}{'bytes out / bytes in':>22}")
    for order, keys in (("random", random_keys), ("ascending", sorted(random_keys))):
        for cache in (0, 16, 128, 1024):
            pager = Pager(os.path.join(folder, f"{order}{cache}.db"), cache_pages=cache)
            tree = BTree(pager)
            for key in keys:
                tree.put(key, key)
            tree.flush()
            written = pager.writes * 4096
            print(f"{order:<10}{cache:>12}{pager.writes:>15,}{pager.writes / N:>12.3f}{written / 2**20:>13.1f}{written / (N * 16):>22.1f}")
            pager.file.close()

100,000 inserts of 16 bytes each = 1.5 MiB of new data
order      cache pages  pages written  per insert  MiB written  bytes out / bytes in
random               0        101,068       1.011        394.8                 258.7
random              16         88,248       0.882        344.7                 225.9
random             128         43,859       0.439        171.3                 112.3
random            1024            537       0.005          2.1                   1.4
ascending            0        101,570       1.016        396.8                 260.0
ascending           16            788       0.008          3.1                   2.0
ascending          128            788       0.008          3.1                   2.0
ascending         1024            788       0.008          3.1                   2.0

With no cache, every insert writes about one page: 101,068 page writes for 100,000 inserts, or 394.8 MiB for 1.5 MiB of new data, which is 258.7 bytes written for every byte inserted. A cache of 16 pages barely helps, because random keys land on random leaves among the 537 pages of the finished tree. A cache of 128 pages cuts the writes to 0.439 per insert. A cache of 1,024 pages holds the entire tree, so each page is written once at the end: 537 writes, 1.4 bytes written per byte inserted. Ascending keys behave very differently. They all land on the right-most leaf, so a cache of just 16 pages cuts the writes to 788, one per page of the finished file.

This is one reason real databases keep a large buffer cache and also a write-ahead log: a write-back cache turns thousands of tiny updates into a few page writes, but pages sitting dirty in memory are lost in a crash unless the changes were logged first. It is also one of the pressures behind log-structured designs that turn random writes into sequential ones; our LSM-tree tutorial builds one, and the SQLite WAL tutorial shows how SQLite handles the same problem.

Common mistakes and how to catch them

Almost every bug in a B+tree is one of a handful of off-by-one decisions, and the planted-bug list in Step 7 is a catalogue of them. Choosing the child with bisect_left hides separator keys. Copying a key up from an internal page, or moving it up from a leaf, duplicates or loses a key. Forgetting to link a new leaf or to carry the link across a merge breaks range scans while point lookups still pass. Forgetting mark loses an update only when the page is evicted. Forgetting to release a merged page leaks it. Forgetting to collapse the root leaves a tall tree with a useless top level. The defence is the same each time: write the invariant down once in check, then let a model-based test hammer the tree with random operations and call it often.

Confirm the whole thing works end to end

Run these commands from the project folder. Each should finish without an error, and the numbers should match what you saw above, apart from the pytest timing and anything that depends on your SQLite version.

python -m pytest -q
python mutants.py
python step08_scale.py
python step09_fill.py
python step10_sqlite.py
python step11_writes.py

You should see 59 passed, then twelve of twelve planted bugs caught, then the lookup table (3.0 pages cold for a million keys), then the fill tables (means of about 0.69 to 0.70 for random inserts, 0.502 for ascending, 0.999 for packed appends), then the SQLite fills, and finally the write counts. If the deterministic numbers differ, run python -m pytest -q first: a failing test points to the line that differs from the code in this tutorial.

Where to go next

You have built the core, and each missing piece is a real topic. Variable-length keys need pages that store cells of different sizes behind an array of offsets, which is what the SQLite reader in Step 10 decodes. Several readers and writers at once need locking or the careful ordering that the long README in PostgreSQL’s btree code describes. Crash safety needs a log: build one with the write-ahead log tutorial. Loading a sorted file quickly is a bottom-up build that packs pages to a chosen fill factor, which is the idea behind PostgreSQL’s fillfactor setting. To see how a query planner decides whether to use an index at all, read how to find a slow query in PostgreSQL 18 and fix it with the right index or how to read SQLite’s EXPLAIN QUERY PLAN. For other ways to find a key fast, see the skip list and Bloom filter tutorials.

Sources and further reading

• SQLite database file format: page layout, b-tree page header, table and index b-trees.
• SQLite src/btree.c: the comments on balance_quick and balance_nonroot (master branch as read on 2026-11-01).
• PostgreSQL 18, B-Tree Indexes and CREATE INDEX: the btree index type and the fillfactor setting.
• PostgreSQL nbtree README: how page deletion works when readers are concurrent.
• Bender et al., Bounding the Fragmentation of B-trees Subject to Batched Insertions (arXiv:2603.12211): the ln 2 fill result and Yao’s 1978 analysis.
• Python bisect and Python struct documentation.