Abstract flowing gradient in deep indigo and blue tones, smooth and luminous, evoking a modern digital learning atmosphere

Computer Science and programming articles. We do not sell courses.

Implementing a B-Tree for Database Indexing

B-trees sit quietly beneath almost every relational database an Australian developer touches, from the ATO's transactional systems processing tax returns to MyHealth Record storing patient histories. They are the unsung workhorses that turn a 50-million-row table scan into a handful of disk reads. Understanding how they work is more than academic curiosity; it shapes decisions about schema design, primary key choices, and query optimisation in production systems built on PostgreSQL, MySQL, or SQLite.

This walkthrough builds a B-tree from first principles, examines how it differs from a binary search tree, and shows how its balance guarantees translate into predictable performance. Along the way, the discussion touches on connections to other CS ideas explored in tutorials on the naive Bayes classifier guide and validation libraries in Python, both of which rely on disciplined data handling at scale.

The shape of a balanced search tree

A B-tree is a self-balancing search tree where each node can hold many keys and many children. The defining rule is simple: every leaf sits at the same depth, and internal nodes are at least half full. This structural regularity is what gives the tree its logarithmic access time, even after millions of insertions and deletions.

In a binary search tree, height can degrade to O(n) when data arrives in sorted order, a pattern that shows up constantly in timestamped records, invoice numbers, or the ascending IDs of a growing customer table. B-trees prevent this by allowing a node to hold, say, 64 to 512 child pointers, dramatically reducing the height. A tree indexing a billion rows might only be four or five levels deep, which means a lookup touches a handful of pages.

The "B" originally stood for Boeing, where Rudolf Bayer and Edward McCreight invented the structure in 1971 for mainframe file systems. Decades later, the same idea powers InnoDB in MySQL, the storage engine behind countless Australian e-commerce platforms built on stacks like Shopify's Australian storefronts or Atlassian's Postgres-backed Jira instances in Sydney.

Why databases reach for B-trees

Disk is slow, memory is fast, and the gap between them is what database indexing must bridge. A B-tree node is sized to match a disk block or page, typically 4 KB to 16 KB, so reading one node brings in a payload of keys and child pointers in a single I/O. Hash indexes give faster point lookups but cannot support range scans, which is why WHERE created_at BETWEEN ? AND ? remains a B-tree-friendly query in tools like the ABS data API used by analysts in Canberra.

In an Australian context, this matters for compliance. The Privacy Act 1988 and the Notifiable Data Breaches scheme require auditable access to historical records. When a regulator asks who accessed a row in the ATO's client register six months ago, the database needs an indexed path to that row. B-trees make such point-in-time lookups efficient because their structure is stable across inserts and updates, preserving the location of existing keys.

Compared to LSM-trees used by Cassandra or RocksDB, B-trees also offer strong read consistency without compaction pauses, which is why transactional systems in banking, healthcare, and government across Sydney and Melbourne tend to prefer them. They are not the fastest writer, but they offer predictable latency, which auditors and SREs appreciate.

Anatomy of a node

A B-tree node stores an ordered array of keys and an array of child pointers that is one element longer. For a node with n keys, there are n+1 children. Leaves, which may also hold values in a clustered index, have no children but carry the same structural contract: keys are sorted, and pointers to sibling leaves can support range scans without climbing back to the parent.

The branching factor, often called the minimum degree t, controls the fan-out. With t = 64, each node holds between 63 and 127 keys. Choosing t depends on page size and key size; a UUID primary key at 16 bytes behaves differently from a 4-byte integer, and the difference affects how many rows fit in a single InnoDB page on a cloud-hosted Aurora cluster in Sydney's ap-southeast-2 region.

A useful property is that the height grows very slowly. Doubling the number of rows from 100 million to 200 million typically adds only one level to the tree, because the width absorbs the new data. Engineers at Canva in Surry Hills or at REA Group in Melbourne often rely on this property when sizing indexes for user activity tables that grow monotonically.

Searching for a key

The search algorithm is a straightforward iteration through the keys in a node, followed by a recursive descent into the appropriate child. With many keys per node, a binary search inside the node is faster than a linear scan, though for node sizes in the low hundreds, linear scan with prefetching often wins on modern CPUs.

Pseudocode for a recursive lookup looks like this: start at the root, walk keys left to right, find the first key greater than the target, and descend into the child just before it. If the key matches, return the associated record or pointer. If a leaf is reached without a match, the key is absent. The recursion bottoms out when the height of the tree, usually four or five, is exhausted.

In practice, this translates to well-known operators in PostgreSQL or MySQL. When a query plan shows an "Index Scan using idx_orders_customer_id", the executor is performing exactly this tree walk, possibly with a correlated subquery pushed into the index. Developers debugging slow reports in tools like Metabase or Apache Superset often discover that the missing index is the difference between a 200ms response and a 30-second timeout.

Insertion and the split operation

Insertions start with a search for the target leaf, then place the new key in sorted order. The complication arises when the target node is full. B-trees fix this preemptively by splitting any full node encountered on the way down, which guarantees that the leaf receiving the new key always has room.

A split divides a node of 2t-1 keys into two nodes of t-1 keys each, pushing the median key up to the parent. If the parent is also full, the split propagates upward; in the worst case, the root splits and a new root is created, increasing the tree height by one. This is the only operation that changes height, and it happens rarely enough that amortised cost stays logarithmic.

Here is the heart of the matter: B-trees are write-optimised in the sense that the work per insertion is bounded, even though each split is O(t). The total cost over n insertions is O(n log n), and the constant is small because splits touch only a handful of nodes. Database engines exploit this to keep indexes healthy under sustained write loads, such as the constant ingest of sensor data from IoT deployments on mine sites in the Pilbara or from logistics fleets across Brisbane and Adelaide.

Deletion and rebalancing

Deletion is more involved than insertion because removing a key can leave a node underfull. The algorithm distinguishes three cases: deleting from a leaf, deleting from an internal node by swapping with the in-order successor or predecessor, and ensuring the target node has at least t keys before descending, otherwise borrowing from a sibling or merging two siblings.

Merges are the expensive case. When two siblings have only t-1 keys each, combining them produces a node with 2t-1 keys and pulls a key down from the parent. If this empties the parent, the height shrinks by one. Although these operations sound dramatic, they are infrequent and confined to a small neighbourhood of nodes.

Real-world databases sometimes defer this rebalancing. PostgreSQL's B-tree implementation does not physically delete entries immediately; instead, it marks them as dead and reuses the space during page splits. Vacuum workers reclaim the dead tuples asynchronously. This trick avoids write amplification on hot indexes, a useful pattern when designing custom storage engines for high-throughput telemetry pipelines used by agritech startups in regional Victoria and Western Australia.

Building the structure in Python

Putting it all together, a minimal B-tree implementation needs a Node class with a list of keys, a list of children, and a flag indicating whether it is a leaf. The Tree class holds the root and a degree parameter. Core methods include search, insert, split_child, and a recursive helper that navigates downward while splitting full nodes on the path.

Error handling deserves attention. A B-tree for a database index must reject duplicate keys or define a stable tiebreaker, and it must guard against integer overflow when computing the median index. For production code, the data validation layer built with pydantic for data validation is a clean way to enforce these invariants at the API boundary before records ever reach the index.

Properties to preserve when implementing

Common pitfalls during implementation

For a deeper dive into how data structures underpin machine learning workflows, the hello ML community collects working examples and pseudocode across dozens of topics, from boosting algorithms to graph traversal, all written and reviewed by contributors who use these structures in Australian production systems.

Testing this implementation should cover bulk loading a sorted sequence of 10 million keys, random insertions, and random deletions, comparing measured height against the theoretical O(log n) curve. If the tree grows beyond expectations, revisit the splitting logic. If lookups slow down disproportionately, the degree is likely too low for the key size, and increasing the node capacity will pay for itself many times over on the first production query that lands in a report served to a stakeholder in Perth or Hobart.