Implementing a B-tree for efficient disk storage
A B-tree is a balanced search structure designed around the unit of I/O that storage systems actually move: a page. Rather than placing one key at each node, it packs many keys into a page, so a small number of page reads can locate a record among millions. This high fan-out is the central reason an on-disk index remains effective when the working set exceeds available memory, and it explains why databases, file systems, and key-value stores use variations of the same design.
Those properties matter close to home. Cloud regions around Sydney and Melbourne serve large populations, while customers and public services in Perth, Adelaide, and regional Australia may sit far from those facilities. The Privacy Act 1988, Australian Privacy Principles, and Notifiable Data Breaches scheme also make storage integrity and access control more than academic concerns for Australian organisations handling personal information.
Why disk access rewards high fan-out
An ordinary binary search tree can require a page read for nearly every node on the search path. On a mechanical disk, that sequence of seeks is expensive; on an SSD, it still wastes I/O bandwidth and memory cache entries. A B-tree broadens each step by allowing one page to hold many ordered keys, combining child pointers with separators and turning navigation into a short walk through a shallow hierarchy.
Node capacity depends on the physical page size and entry size. If a 16 KiB page holds about 80 key-and-value entries, including routing metadata, a four-level tree can address tens of millions of leaf records. The important metric is therefore not the number of comparisons alone but the number of pages touched. Searches generally require O(log_t N) page accesses for minimum degree t, while each node’s sorted key array can be searched with O(log t) comparisons.
Sequential locality reinforces the benefit. Leaves can be visited in key order, and the operating system can use readahead when an entire range is requested. This suits Australia’s digital-banking and online-retail market, including banking apps checked during train commutes and catalogues browsed over home NBN connections or mobile broadband. It also helps retail platforms maintain responsive search when regional mobile connections are less stable than a fixed-line network.
Choosing node layout and search rules
For a textbook B-tree of minimum degree t, a non-root internal node has at least t children and at most 2t, with one key between adjacent children. Every node has at most 2t−1 keys, and a non-root leaf has at least t−1. The root is special: it may be an empty leaf, a non-empty leaf, or have at least two children. These invariants keep the height near logarithmic as records are added or removed.
Choose the order after measuring real records. Maximum keys per node depend on a fixed page size, variable-length key widths, value storage, and child-reference overhead. A fixed-width record can use an array-backed node, while variable records often need a slotted page so short values do not reserve unusable space. Internal and leaf pages can also have different layouts, allowing leaves to carry more payload while internal pages keep compact separators.
The core lookup is short because each node is already sorted:
search(node, key):
i = lower_bound(node.keys, key)
if i < length(node.keys) and node.keys[i] == key:
return node.values[i]
if node.is_leaf:
return NOT_FOUND
return search(node.children[i], key)
A production implementation should represent children as page identifiers rather than process pointers, and it should define key comparison and duplicate handling before coding. Many database indexes use the B+ tree variant: internal nodes hold separators only, while values live in leaves and leaves are linked. That change simplifies range scans and makes the textbook pseudocode slightly different, so the chosen variant must be explicit.
Inserting, deleting, and preserving balance
Insertion descends through the tree but splits full nodes before they become unreachable. When a child has 2t−1 keys, its median key is promoted and the remaining keys form two nodes. A full root produces a new root and increases the height by one. Searches therefore continue through a stable hierarchy, while splits localise structural change instead of rebuilding the entire index.
Deletion is the harder operation. After finding a key, an implementation must preserve minimum occupancy by borrowing from a sibling or merging nodes with one. Merging can create an underfull parent, so repairs may cascade toward the root. Replacing a deleted internal key with its predecessor or successor also requires careful separator updates. This work is why a database often separates immutable index pages from mutable records and journals structural changes.
Bulk loading offers a faster alternative when source data is already sorted. Pack full leaves sequentially, collect their separators, construct the next level, and repeat until one root remains. This reduces random writes and suits national product catalogues, geospatial datasets, and audit exports. The result should still pass the same balance checks as a tree grown through repeated inserts.
Practical implementation and validation checklist
A learning implementation can be written in Python with lists for keys, values, and children, but production storage benefits from a language with predictable memory behaviour, such as C, Rust, or Go. Use fixed-width page identifiers, explicit byte order, and a stable on-disk format. A version number in the metadata header allows future migrations without confusing old pages with new ones.
Durability must be designed alongside search. A write-ahead log can record page replacements before they reach stable storage, while checksums identify torn or corrupt pages. For replicated systems, checksums detect local damage and a Merkle tree integrity review describes how replicated trees can provide stronger tamper evidence across nodes.
Core implementation checks
- Calculate maximum node occupancy from page size and worst-case entry widths.
- Store child references as stable page identifiers, never raw memory addresses.
- Define ordering, duplicate-key, collation, and end-of-range behaviour before writing lookup code.
- Split full children before descending and repair underfull nodes after deletion.
- Keep leaf links when ordered range traversal is part of the interface.
- Assert key counts, child counts, occupancy, and separator order after every mutation.
Operational and compliance checks
- Cache hot upper levels and measure hit rate under realistic workloads.
- Log page updates, define sync semantics, and test recovery after abrupt termination.
- Verify checksums, metadata versions, and page identifiers during startup and scans.
- Encrypt sensitive pages and restrict keys according to data classification and role.
- Benchmark p95 and p99 latency, split rates, space use, and write amplification.
- Apply retention and deletion rules to Australian privacy, financial, and health information.
Measuring performance and comparing alternatives
Performance testing should count physical page reads, not just elapsed time in a warm cache. Useful measurements include cache hit ratio, pages touched per lookup, sequential bytes read, mutation latency, and recovery time. Include cold-cache cases, full scans, and workloads larger than RAM. An SSD reduces seek penalties, but it does not remove the benefit of fewer I/O operations or the predictability of a bounded tree height.
The closest database-oriented relative is usually the B+ tree, because storing values only in leaves makes leaf traversal and range scans straightforward. Other structures answer different access patterns, so the right choice depends on whether exact matches, ordered scans, or updates dominate.
| Structure | Physical layout | Strongest use | Main trade-off |
|---|---|---|---|
| B-tree | Keys and values can occupy every level | General on-disk indexes and file-system structures | Internal updates can require copying pages |
| B+ tree | Separators above linked value-bearing leaves | Database indexes with point and range queries | Usually needs a separate record lookup |
| Binary search tree | One key per node | In-memory ordered sets | Random disk access makes it unsuitable at scale |
| Hash index | Records grouped into hash buckets | Fast exact-match lookups | No natural key order or range traversal |
For regulated Australian workloads, the final design must combine efficient navigation with verifiable durability, least-privilege access, and documented retention. Systems touching health information must also account for the My Health Records Act 2012 rather than treating an index as a neutral technical component. The hello ML community publishes related explanations of computer-science concepts and implementation techniques.