{"schemaVersion":"1.0","type":"TechArticle","types":["Article","TechArticle"],"slug":"understanding-database-indexes-by-building-a-tiny-b-tree-gq5y9","url":"https://zyvop.com/understanding-database-indexes-by-building-a-tiny-b-tree-gq5y9","title":"Understanding Database Indexes by Building a Tiny B-Tree","subtitle":"Build a small B+ tree in Python to understand indexed lookups, leaf splits, range scans, and composite indexes from the inside out.","tldr":"Build a B+ tree from scratch in Python, test its invariants, and compare its behavior with SQLite. Learn why indexes speed up lookups, how composite indexes follow the leftmost-prefix rule, and what databases trade for faster reads.","keywords":["database indexes","Python","B+ Trees","Database Internals","SQLite","Databases"],"entities":["Emma Clements","database indexes","Python","B+ Trees","Database Internals","SQLite","Databases","ZyVOP"],"keyTakeaways":["It is a sorted data structure that the database keeps up to date for you.","In this post we build one from scratch in about 80 lines of Python, test it, and then watch a real database (SQLite) behave exactly the way our toy does.","Everything here uses only the Python standard library and was run on Python 3.13."],"headings":["The problem: scanning","Why a tree?","The implementation","Does it actually work?","How deep does it get?","The same thing in a real database","The cost side","What this toy leaves out","Appendix: the full test suite"],"outboundLinks":[],"contentText":"An index is not magic. It is a sorted data structure that the database keeps up to date for you. In this post we build one from scratch in about 80 lines of Python, test it, and then watch a real database (SQLite) behave exactly the way our toy does. Everything here uses only the Python standard library and was run on Python 3.13. The problem: scanning Take a users table with 500,000 rows and ask for one user by email. With no index, the database has no choice but to read every row until it finds a match. SQLite's query plan calls this a SCAN. I measured it (SQLite 3.53.1, in-memory, 500k rows, average of 20 lookups): Query plan Time per lookup No index SCAN users ~22.6 ms Index on email SEARCH users USING INDEX idx_email (email=?) ~0.002 ms That is roughly a 10,000x difference, and the gap grows with the table. Timings depend on your machine, so treat the ratio, not the absolute numbers, as the point. Why a tree? We need a sorted structure so we can jump to a key instead of walking to it. A sorted array supports binary search, but inserting into the middle means shifting everything after it. A binary tree fixes inserts, but it is deep, and on disk every level costs a page read. A B-tree fixes both by making nodes wide. Each node holds many keys (in a real database, one disk page's worth, often hundreds), so the tree stays very shallow. We will build the most common database flavor, the B+tree: Internal nodes hold only separator keys and child pointers. They are signposts. Leaf nodes hold the actual keys and values (in a database, a pointer to the row). Leaves are linked left to right, so a range scan walks along them without going back up the tree. All leaves are at the same depth. The tree only grows taller when the root splits. When a node holds more than max_keys keys, it splits in half and hands a separator key up to its parent. Real databases use variants of this design, but the mechanics are the same. The implementation from bisect import bisect_left, bisect_right class Node: def __init__(self, leaf): self.leaf = leaf self.keys = [] self.children = [] # internal nodes: len(keys) + 1 children self.values = [] # leaf nodes: parallel to keys self.next = None # leaf nodes: right sibling, for range scans class BPlusTree: def __init__(self, max_keys=4): assert max_keys &gt;= 3, \"need at least 3 keys per node\" self.max_keys = max_keys self.root = Node(leaf=True) self.height = 1 # nodes visited by every lookup def _find_leaf(self, key): node = self.root while not node.leaf: node = node.children[bisect_right(node.keys, key)] return node def get(self, key, default=None): leaf = self._find_leaf(key) i = bisect_left(leaf.keys, key) if i &lt; len(leaf.keys) and leaf.keys[i] == key: return leaf.values[i] return default def range(self, lo, hi): \"\"\"Yield (key, value) for lo &lt;= key &lt;= hi, in key order.\"\"\" leaf = self._find_leaf(lo) while leaf: for k, v in zip(leaf.keys, leaf.values): if k &gt; hi: return if k &gt;= lo: yield k, v leaf = leaf.next def insert(self, key, value): split = self._insert(self.root, key, value) if split: # the root itself split: the tree grows one level sep, right = split new_root = Node(leaf=False) new_root.keys = [sep] new_root.children = [self.root, right] self.root = new_root self.height += 1 def _insert(self, node, key, value): if node.leaf: i = bisect_left(node.keys, key) if i &lt; len(node.keys) and node.keys[i] == key: node.values[i] = value # key exists: overwrite return None node.keys.insert(i, key) node.values.insert(i, value) return self._split_leaf(node) if len(node.keys) &gt; self.max_keys else None i = bisect_right(node.keys, key) split = self._insert(node.children[i], key, value) if split is None: return None sep, right = split node.keys.insert(i, sep) node.children.insert(i + 1, right) return self._split_internal(node) if len(node.keys) &gt; self.max_keys else None def _split_leaf(self, node): mid = len(node.keys) // 2 right = Node(leaf=True) right.keys, node.keys = node.keys[mid:], node.keys[:mid] right.values, node.values = node.values[mid:], node.values[:mid] right.next, node.next = node.next, right return right.keys[0], right # separator is copied up; it stays in the leaf def _split_internal(self, node): mid = len(node.keys) // 2 sep = node.keys[mid] right = Node(leaf=False) right.keys, node.keys = node.keys[mid + 1:], node.keys[:mid] right.children, node.children = node.children[mid + 1:], node.children[:mid + 1] return sep, right # separator is pushed up; it leaves this levelFour ideas carry the whole thing: Lookup (_find_leaf) walks from the root, using binary search at each node to pick the child, until it reaches a leaf. Every lookup visits exactly height nodes. Leaf splits copy the separator up. The first key of the new right leaf is also kept in that leaf, because leaves must hold every key. Internal splits push the separator up. The middle key moves to the parent and leaves this level, because internal keys are only signposts. Range scans find the leaf containing lo, then follow the next pointers. No walking back up the tree is needed. Here it is on a small example, with a helper that prints the tree's shape: from btree import BPlusTree def show(node, depth=0): print(\" \" * depth + (\"leaf \" if node.leaf else \"node \") + str(node.keys)) for child in node.children: show(child, depth + 1) t = BPlusTree(max_keys=4) for k in [10, 20, 5, 6, 12, 30, 7, 17]: t.insert(k, f\"row-{k}\") show(t.root) print(t.get(12)) print(list(t.range(6, 17)))Output: node [10, 17] leaf [5, 6, 7] leaf [10, 12] leaf [17, 20, 30] row-12 [(6, 'row-6'), (7, 'row-7'), (10, 'row-10'), (12, 'row-12'), (17, 'row-17')]Drawn as a tree (dotted arrows are the next links between leaves): flowchart TD R[\"10 | 17\"] L1[\"5 6 7\"] L2[\"10 12\"] L3[\"17 20 30\"] R --&gt; L1 R --&gt; L2 R --&gt; L3 L1 -.-&gt;|next| L2 L2 -.-&gt;|next| L3Eight keys did not fit in one leaf, so leaves split and the root became an internal node holding the signposts 10 and 17. Looking up 12 means: compare against the root's keys, go to the middle leaf, find it there. The last insert, 17, is a leaf split in action. The leaf [10, 12, 20, 30] became [10, 12, 17, 20, 30], which is one key over max_keys=4. It splits in half, and the first key of the new right leaf (17) is copied up into the parent: flowchart LR subgraph before[\"Before: insert 17 overflows a leaf\"] direction TB B0[\"10\"] --&gt; B1[\"5 6 7\"] B0 --&gt; B2[\"10 12 17 20 30&lt;br/&gt;5 keys, max is 4\"] end subgraph after[\"After: split, 17 copied up\"] direction TB A0[\"10 | 17\"] --&gt; A1[\"5 6 7\"] A0 --&gt; A2[\"10 12\"] A0 --&gt; A3[\"17 20 30\"] end before --&gt; afterDoes it actually work? A data structure like this fails quietly: a bad split still returns plausible answers for a while. So the tests check three different things: Against an oracle. After thousands of random inserts (with deliberate overwrites), every get must match a plain Python dict, across several node sizes from 3 to 100. Against the structure's own rules. After inserts, a checker walks the whole tree and asserts that keys are sorted, no node is overfull, non-root nodes are at least half full, every key sits within its parent's bounds, all leaves are at the same depth, and the leaf chain contains exactly the sorted keys. On nasty input. Sorted and reverse-sorted inserts (the classic worst case for naive trees), empty and single-element trees, string keys, and 500 random range queries compared against a brute-force filter. The full test file is in the appendix. Running it: $ python3 test_btree.py ok test_empty_and_single ok test_matches_dict_oracle ok test_range_queries ok test_sorted_and_reverse_inserts ok test_string_keys 5 tests passedHow deep does it get? With 100 keys per node, I inserted keys in random order and recorded the tree's height: Keys Height 1,000 2 10,000 3 100,000 3 1,000,000 4 A million keys, four node visits. Height grows with the logarithm of the table size, and with wide nodes the base of that logarithm is large. The same arithmetic puts a billion keys at about five levels, which is why indexed lookups on huge tables still take a handful of page reads, and why the top levels of a busy index usually stay cached in memory. The same thing in a real database Our toy and SQLite agree. Using the 500k-row table from the start, I created a composite index on (country, created_at) and asked SQLite how it would run three queries: country AND created_at &gt; ? -&gt; SEARCH users USING INDEX idx_country_created (country=? AND created_at&gt;?) country only -&gt; SEARCH users USING INDEX idx_country_created (country=?) created_at only -&gt; SCAN usersThe tree is sorted by country first, then by created_at within each country. Here is the leaf level, simplified to three countries: flowchart LR D[\"DE&lt;br/&gt;oldest to newest\"] --&gt; I[\"IN&lt;br/&gt;oldest to newest\"] --&gt; U[\"US&lt;br/&gt;oldest to newest\"]A query on country jumps straight to one block. A query on created_at alone would have to look inside every block. That has direct consequences, and you can see each one in the toy: Leftmost-prefix rule. Filtering on country can descend the tree. Filtering on created_at alone cannot, because matching rows are scattered across every country's section. Hence the SCAN. Range conditions are cheap. created_at &gt; ? within one country is a descent plus a walk along linked leaves, exactly our range(). Leading wildcards defeat the index. For email LIKE '%99@example.com' SQLite also reported SCAN users, even with idx_email present. A suffix match gives the tree nothing to compare against at the top. Order comes free. Leaves are already sorted, so ORDER BY on the indexed column needs no separate sort. The cost side Reads get faster; writes get more work. Every insert has to find its leaf and may trigger splits that cascade up the tree, and each additional index on a table is another tree to update. Index the columns you actually query by, not every column. What this toy leaves out This is a teaching implementation, so be clear about its limits: No deletion. Real trees merge or borrow between underfull nodes. We only insert. Unique keys only. Inserting an existing key overwrites it, like a unique index. Non-unique indexes need duplicate handling. In memory. Real nodes are fixed-size disk pages, read through a buffer cache. Single-threaded. Real engines use fine-grained latching so many readers and writers share a tree. No crash safety. Real engines log changes (a write-ahead log) so a half-finished split can be recovered. Each of those is a good follow-up post on its own. Appendix: the full test suite import random from btree import BPlusTree def check_invariants(tree): \"\"\"Raise AssertionError if the tree breaks any B+tree rule.\"\"\" leaf_depths = set() min_fill = tree.max_keys // 2 def walk(node, depth, lo, hi): assert node.keys == sorted(node.keys), \"keys out of order\" assert len(node.keys) &lt;= tree.max_keys, \"node overfull\" if node is not tree.root: assert len(node.keys) &gt;= min_fill, \"node underfull\" for k in node.keys: # every key must sit inside its parent's bounds assert (lo is None or k &gt;= lo) and (hi is None or k &lt; hi) if node.leaf: leaf_depths.add(depth) assert len(node.keys) == len(node.values) return assert len(node.children) == len(node.keys) + 1 bounds = [lo] + node.keys + [hi] for i, child in enumerate(node.children): walk(child, depth + 1, bounds[i], bounds[i + 1]) walk(tree.root, 1, None, None) assert leaf_depths == {tree.height}, \"leaves at different depths\" def leaf_chain_keys(tree): node = tree.root while not node.leaf: node = node.children[0] keys = [] while node: keys.extend(node.keys) node = node.next return keys def test_matches_dict_oracle(): for max_keys in (3, 4, 5, 16, 100): rng = random.Random(max_keys) tree, oracle = BPlusTree(max_keys), {} for _ in range(5000): k = rng.randrange(2000) # small key space forces overwrites tree.insert(k, k * 10) oracle[k] = k * 10 check_invariants(tree) assert leaf_chain_keys(tree) == sorted(oracle) for k in range(-5, 2005): assert tree.get(k) == oracle.get(k) def test_range_queries(): rng = random.Random(1) tree, oracle = BPlusTree(4), {} for _ in range(3000): k = rng.randrange(10_000) tree.insert(k, str(k)) oracle[k] = str(k) for _ in range(500): lo, hi = sorted((rng.randrange(-100, 10_100), rng.randrange(-100, 10_100))) expected = [(k, oracle[k]) for k in sorted(oracle) if lo &lt;= k &lt;= hi] assert list(tree.range(lo, hi)) == expected assert list(tree.range(20_000, 30_000)) == [] # empty range past the end def test_sorted_and_reverse_inserts(): for keys in (range(1000), reversed(range(1000))): tree = BPlusTree(4) for k in keys: tree.insert(k, k) check_invariants(tree) assert leaf_chain_keys(tree) == list(range(1000)) def test_empty_and_single(): tree = BPlusTree(4) assert tree.get(1) is None and tree.get(1, \"x\") == \"x\" assert list(tree.range(0, 10)) == [] tree.insert(1, \"a\") assert tree.get(1) == \"a\" and tree.height == 1 def test_string_keys(): tree = BPlusTree(4) words = \"the quick brown fox jumps over the lazy dog\".split() for w in words: tree.insert(w, len(w)) check_invariants(tree) assert list(tree.range(\"a\", \"g\")) == [(\"brown\", 5), (\"dog\", 3), (\"fox\", 3)] if __name__ == \"__main__\": tests = [v for k, v in sorted(globals().items()) if k.startswith(\"test_\")] for t in tests: t() print(\"ok \", t.__name__) print(f\"{len(tests)} tests passed\")","contentHash":"sha256:b218c2d5e418d2b76f2603bc47aef8af32786c1a0e6159a393f246529017f668","authorName":"Emma Clements","authorUrl":"https://zyvop.com/author/emma512","authorSameAs":[],"category":"Databases","tags":["database indexes","Python","B+ Trees","Database Internals","SQLite"],"audience":"Software engineers and developers building applications with Databases","tone":"Practical and evidence-based engineering guidance","readingTimeMinutes":9,"wordCount":2231,"faqs":null,"primaryTopic":"Databases","publishedAt":"2026-11-20T15:36:48.151Z","updatedAt":"2026-11-20T15:36:48.151Z","canonicalUrl":"https://zyvop.com/understanding-database-indexes-by-building-a-tiny-b-tree-gq5y9"}