The B+Tree
This is the page the whole project was built to earn. BisonDB's indexes are a hand-written, on-disk B+Tree, without std::map standing in for the hard part, and without using a storage library. It maps encoded key bytes → small values (a log offset for the _id index; nothing at all for secondary indexes, whose keys are self-contained) and is verified by 100,000-operation randomized fuzzing against std::map as an oracle.
Why a B+Tree at all
| Hash index | B+Tree | LSM tree | |
|---|---|---|---|
| Point lookup | O(1) | O(log n) | O(log n), multi-level |
| Range scan | impossible | sequential leaf walk | merge across levels |
| Ordered iteration | no | yes | yes |
| Write pattern | random | random page writes | append-only, compaction |
| Implementation size | small | moderate | large (levels, bloom, merge) |
| Used by | Redis hashes, Python dict | SQLite, Postgres, MySQL | RocksDB, Cassandra |
Queries like {pop: {$gte: 40000}} are range queries, which a hash index cannot answer at all (BisonDB's Phase-2 startup hash could only find exact _ids). An LSM tree wins on write-heavy workloads but costs far more machinery. The B+Tree is the smallest structure that makes range queries cheap, which is exactly what explain's 29470 → 1015 docsExamined collapse demonstrates.
Pages and the pager
An index file is an array of fixed 4096-byte pages. Page 0 is the header (magic BSNI, root page id, free-list head, page count, and the clean flag from the storage page). Freed pages form a linked free list and are reused before the file grows. A small LRU cache (256 pages) with write-back keeps hot pages in memory; sync flushes dirty pages, fsyncs, then sets the clean flag.
Node layout: slotted pages
Both node kinds share the same layout: a 12-byte header, a growing slot array, and cells grows backward from the page end:
offset 0 4096
┌────────────┬───────────────────────┬─────────┬────────────────┐
│ header 12B │ slot array (u16 × n) │ free │ cells ← │
│ │ sorted by key, grows →│ space │ grow backward │
└────────────┴───────────────────────┴─────────┴────────────────┘| Header offset | Field |
|---|---|
| 0 | node type: 1 = leaf, 2 = internal |
| 2-3 | cell count (u16) |
| 4-5 | free-space offset (the lowest cell start) |
| 8-11 | leaf: right-sibling page id · internal: rightmost child id |
A leaf cell is keyLen u16 │ key │ valLen u16 │ value. An internal cell is keyLen u16 │ key │ childPageId u32, where the child holds keys less than the cell's key, and the header's rightmost child catches everything ≥ the last separator.
Why slots instead of packed records? Binary search needs random access to the i-th key, but keys are variable-length. The slot array gives O(log n) search over offsets that are cheap to shift on insert; deleting a cell just removes its slot and leaves a hole, and a page compacts its cell area only when a later insert actually needs the space.
Leaves are also chained left-to-right through the sibling pointer; that single u32 per page is what turns "find the start of the range" into "now just keep reading."
Key encoding
The tree compares keys with plain memcmp. All type-aware ordering is pushed into the encoding, which must therefore be order-preserving: encoded bytes compare exactly like the values they represent. Each key starts with a type-class tag (giving the cross-type order Null < Numbers < String < ObjectId < Bool < DateTime) followed by a payload:
| Type | Encoding |
|---|---|
| Numbers | Int32/Int64/Double normalized to double, bits transformed (below), big-endian |
| String | UTF-8 with 00 escaped as 00 FF, terminated 00 00 |
| ObjectId | 12 raw bytes |
| Bool | one byte |
| DateTime | i64 + 2⁶³ bias, big-endian |
Keys cap at 512 encoded bytes. Longer values (as well as NaN, documents, and arrays) simply are not indexed. Those documents are still found by full scans, and index builds count them as skipped.
The double sign-flip trick
IEEE 754 doubles sort like their bit patterns for positive numbers, but negative numbers have the sign bit set (sorting them above positives unsigned) and grow downward in magnitude as their bit patterns grow. Two transformations address this:
- sign bit clear (positive): set the sign bit → moves positives above all negatives
- sign bit set (negative): flip all 64 bits, which reverses the negatives' order and clears their sign bit
| Value | IEEE bits | After transform | Unsigned order |
|---|---|---|---|
| −2.0 | C000…0000 | 3FFF…FFFF | smallest |
| −1.0 | BFF0…0000 | 400F…FFFF | ↑ |
| 0.0 | 0000…0000 | 8000…0000 | ↑ |
| 1.0 | 3FF0…0000 | BFF0…0000 | ↑ |
| 2.0 | 4000…0000 | C000…0000 | largest |
(−0.0 is normalized to +0.0 first so the two zeros collide to match numeric equality.) Stored big-endian, memcmp sorts doubles numerically. The string escaping ensures "a" < "a\0" < "aa" remains correct under bytewise comparison even with embedded NULs. A 30,000-case fuzz test asserts memcmp(encode(a), encode(b)) agrees with a direct value comparator on random pairs.
Composite keys for secondary indexes
A secondary index on pop stores encode(popValue) ‖ 00 ‖ _id. Twelve extra bytes make every key unique (duplicate field values differ in id), keep entries grouped by value, and let a range scan recover the _id from the key itself without storing any cell value.
Insertion and splits
Descent is standard: binary-search each internal node's separators, follow the child, insert into the leaf. When a page cannot fit the new cell even after compacting its holes, it splits:
Leaf splits copy the separator up (the key stays in the leaf because range scans need every key at leaf level); internal splits move their median up. A root split allocates a new root with one separator, which is the only way this tree gets taller; the tree grows perfectly balanced, by construction.
Deletion: deliberately lazy
Textbook B-trees rebalance on underflow: they borrow from a sibling, merge, and potentially cascading. BisonDB does something simpler: remove the cell, and only when a page hits zero cells, unlink it (stitch the sibling chain via its in-tree predecessor, drop the parent's reference, collapse single-child roots).
The rationale is a cost/benefit honestly weighed: rebalancing buys back space earlier but adds the most error-prone code in the textbook algorithm. Lazy deletion keeps pages valid at all times (search and scans never care that a page is half-empty), reclaims fully-empty pages through the free list. This leaves the worst case of a long-lived, half-empty tree after mass deletion to the same compact operation the log already needs, which rebuilds indexes densely from scratch. The 100k-op fuzz hammers exactly this path with mixed inserts and erases.
Recovery, again
Nothing on this page changes the storage layer's rule: the tree flushes dirty pages on sync and marks itself clean; any crash leaves the flag unset, and the next open throws the file away and rebuilds from the log. The B+Tree never has to be repairable, only detectably broken, which removes an entire class of subtle corruption bugs from the design space.
Concurrency
One writer or many readers, enforced by a tree-level reader-writer lock; cursors hold the read lock for their lifetime. Page-level latching (what production engines do) was explicitly scoped out; see concurrency.