Why We Eliminated the Primary Key B+Tree
💡Typhon is an embedded, persistent, ACID database engine written in .NET that speaks the native language of game servers and real-time simulations: entities, components, and systems.
It delivers full transactional safety with MVCC snapshot isolation at sub-microsecond latency, powered by cache-line-aware storage, zero-copy access, and configurable durability.
Series: A Database That Thinks Like a Game Engine
- Why I’m Building a Database Engine in C#
- What Game Engines Know About Data That Databases Forgot
- Microsecond Latency in a Managed Language
- Deadlock-Free by Construction
- Three Durability Modes, One WAL
- Building a Page Cache That Doesn’t Count
- MVCC at Microsecond Scale
- The 8-Byte Lock
- Why We Eliminated the Primary Key B+Tree (this post)
- 5 Performance Assumptions That Were Wrong (coming soon)
Every database has a primary key index. That’s not a design decision anyone writes down — it’s furniture. You need to find a record by its identity, finding things by key is what B+Trees are for, so you build one, and nobody in the code review asks why.
Typhon had one per component type. LongSingleBTree for the ordinary case, LongMultipleBTree when a component allowed duplicates, both keyed by the entity’s primary key, both living on disk in their own segment. On the eve of the change the identifier PrimaryKeyIndex appeared 43 times across 14 files — ComponentTable, DatabaseEngine, Transaction, the WAL replay helper, the index maintainer, the query pipeline, the statistics worker, three of the query views, and the diagnostics command in the shell.
Today it appears zero times. Those trees are gone, and what replaced them is a hash map.
To be clear about the scope before we start, because the title oversells it: this is the primary key index only. Typhon still runs B+Trees and still likes them. Every secondary index — find all entities whose Level is between 10 and 20 — is a B+Tree, and will stay one, because a range scan over an unknown set is exactly what the structure is for.
The interesting part is why the primary key was never that. This post is a small argument with a sharp edge: a B+Tree charges you, on every single operation, for a property that nothing in this engine ever asked it for.
🚦 Two ways to reach an entity, and only one of them uses the key
Before any implementation, there’s a distinction that decides the whole design.
There are exactly two ways data gets reached in this engine.
The first is direct access: you already hold the id. You got it from a previous query, or from an EntityLink<T> field on some other component pointing at this one, or from your own game-server state that has been carrying it across ticks. You know precisely which entity you want, you want it now, and you want its components. One entity, exact match, no searching involved. This is ResolveEntity — the path behind tx.Open(id).
The second is a query: you don’t hold any ids, you hold a predicate. And here is the fact everything else follows from — not a convention, an enforced rule:
A query can only filter on an indexed component field. If a field has no index, it cannot appear in the query at all.
Typhon has no full table scan. It isn’t discouraged or deoptimised; it doesn’t exist, deliberately. Either a field carries an index — so the planner can estimate its selectivity and evaluate a real key range — or the engine refuses to plan on it. That constraint is what keeps query cost predictable in an engine budgeting microseconds, and it means every query in the system enters through a secondary index by construction.
Now notice which field can never be one of those. Real queries look like “return all Player entities whose GuildId equals 12.” They filter on component field values — guild membership, level, health, team — because those carry meaning about the entity. An entity id carries none. It’s a handle: assigned by the engine in whatever order entities happened to be created, encoding identity and routing and nothing else. Two entities with adjacent ids have nothing whatsoever in common — one might be a level-3 goblin, the next a player’s guild bank. The id tells you which entity, never what kind or what state.
So WHERE EntityId > 8000 isn’t slow in Typhon. It’s not expressible, and it wouldn’t mean anything if it were.
Put the two halves together and you get the conclusion that drove the change:
The query engine never touches the primary key index. It enters through a secondary index, finds the matching entities there, and comes out holding ids — which it then resolves through path one. The primary key was never an entry point for a search. It was the step after the search.
Which leaves that index with exactly one job, performed the same way every single time: give me the entity with this key, which I already have. An exact match. Never a range, never a scan, never an ordered walk — not rarely, but never, because the engine forbids the queries that would need one.
🧮 Ordering you never asked for
A B+Tree’s defining property is that it keeps its keys in order. That’s the entire reason it’s shaped the way it is: the fanout, the balanced descent, the leaves linked left to right. Order is what lets you answer Level BETWEEN 10 AND 20 by finding one boundary and walking sideways until you fall out of range. It’s a genuinely excellent structure and Typhon’s secondary indexes depend on it completely.
Ours was a good one, too — 256-byte nodes holding 19 entries, sized so that the CPU’s adjacent-line prefetcher pulls in the whole node, with optimistic lock coupling so readers never take a latch on the way down. Nothing that follows is a story about a badly built tree. It was carefully made, it worked, and it was the wrong shape for the only question anyone ever asked it.
Order is also not free, and — this is the part that’s easy to miss — you don’t pay for it once when you build the index. You pay on every operation that touches it, forever.
-
On lookup, you pay
O(log n). The descent exists to preserve the invariant that keys are sorted; each level is a pointer chase to a node that may be on a different page. A hash map paysO(1): hash the key, go to the bucket. - On insert, you pay node splits and rebalancing. Keeping a total order under mutation means occasionally rewriting the shape of the tree — sometimes propagating all the way to the root.
- On concurrency, you pay optimistic lock coupling at every level of the descent. Both structures use OLC — that part doesn’t change — but a tree has to validate on the way down: snapshot the root’s version, then each internal node’s, then the leaf’s, and restart the entire descent if any of them moved, because a rebalance can invalidate an ancestor you already walked past. The hash map validates once, on the bucket it landed on, and a failed validation costs you one bucket probe.
Every item on that list is the price of ordering. And nothing had ever read this index in order.
Two indexes, two completely different requirements, one structure. Only the top one was getting its money’s worth.
That’s the whole argument, and it fits in a sentence: a B+Tree is a hash map that also knows how to sort, and sorting is the part we were paying for and never using.
Which makes the replacement a slightly unusual kind of change. The new structure isn’t cleverer than the old one. It’s deliberately less capable — it cannot do range scans, it cannot enumerate in key order, it has strictly fewer abilities than the thing it replaced. That’s the point. The missing capability had no user, and everything the old structure did to provide it was cost.
🗺️ What replaced it
A per-archetype entity map: one hash map per archetype, keyed by the 48-bit EntityKey, whose value is the entity’s record stored inline in the bucket.
bool found = es.EntityMap.TryGet(id.EntityKey, readBuf, ref _entityMapCacheAccessor);
Hash the key, read one bucket, done. The map is a RawValuePagedHashMap<long, PersistentStore> — the design docs call it a LinearHash — and the “paged” part matters: it’s backed by the same page cache as everything else, so it persists, pages, and checkpoints like any other structure in the engine. This is a durable index, not an in-memory accelerator.
It is also fully concurrent, and — worth stating plainly, because it’s the detail that makes this an honest comparison — it uses the same optimistic lock coupling the B+Trees use. Readers take no lock at all. They snapshot the bucket’s version counter, probe the bucket, then re-read that same counter and only trust the result if it hasn’t moved; if it has, they retry:
int version = Volatile.Read(ref stripe.OlcVersion);
if ((version & 1) != 0) { Thread.SpinWait(1); continue; } // a writer holds it — bit 0 is the lock
// … probe the bucket …
if (Volatile.Read(ref stripe.OlcVersion) != version) { continue; } // it moved under us — retry
return found;
Writers claim that bucket exclusively with a CompareExchange on bit 0 of the same word, then release by incrementing it — which bumps the version and invalidates exactly the readers who were mid-probe. One word, doing double duty as lock and version, in the style the whole engine uses.
So this was never “swap a concurrent structure for a simpler serialised one.” It’s the same concurrency discipline, applied to a structure that needs far less of it — one validation instead of one per level, and a retry that costs a bucket probe instead of a walk from the root.
📊 The numbers
Straight to it — the two structures, head to head, with every variable but the structure held fixed. A LongSingleBTree and a PagedHashMap — the typed sibling of the raw-value map the engine actually uses, so both sides store long → long and neither gets an unfair shape — both on the same page store, both pre-filled with the same 10,000 keys, both driven by the same generated key stream. Same process, same run.
Ryzen 9 7950X, .NET 10, in-process toolchain:
| Operation | B+Tree | Hash map | Tree costs |
|---|---|---|---|
| Lookup, random keys (×100) | 215.4 ns | 47.4 ns | 4.5× |
| Lookup, fixed key | 227.7 ns | 77.9 ns | 2.9× |
| Lookup, miss | 241.0 ns | 71.1 ns | 3.4× |
| Insert, sequential append | 140.3 ns | 64.6 ns | 2.2× |
| Insert, random position | 342.4 ns | 75.0 ns | 4.6× |
The two bold rows are the workload. Entity ids are handed out in creation order and then looked up in arbitrary order for the life of the database, so random-key exact-match is entity resolution — you touch whatever entities the simulation happens to reference this tick. Across three separate runs the random rows land at 176–215 ns for the tree against 46–50 ns for the map on lookup, and 329–348 ns against 70–75 ns on insert. Call it 4×, and don’t read more precision into it than that.
But the row I didn’t expect is the interesting one. Look at what happens to the tree between its two insert cases: 140 ns when the key appends to the end, 342 ns when it lands somewhere in the middle. Same tree, same key count, same operation — a 2.4× swing that depends entirely on where the key falls. Now look at the hash map across those same two rows: 64.6 ns and 75.0 ns. Essentially flat.
That gap is the ordering tax, caught in the act. The tree is slower on a random insert precisely because it is keeping keys sorted — a key landing mid-structure means shifting entries, and sometimes splitting a node and propagating the split upward. The hash map has no order to preserve, so one position is as good as another and it genuinely doesn’t care where your key hashes to. The variance is the feature you’re paying for.
Three caveats, all mine.
The ×100 batch amortises the per-call accessor setup that each single-op row pays once — that’s most of the 47-vs-78 gap on the map, where a fixed cost weighs heavier on a smaller number. And these are in-process figures, so don’t line them up against the project’s standard harness; the tree’s fixed-key lookup measures 227.7 ns here against 213.7 ns there, close enough to trust.
The one that cuts against me: 10,000 keys is a small tree. At 19 entries per node that’s about three levels, entirely cache-resident — near the B+Tree’s best case, where O(log n) barely gets going. Every extra level adds another potentially-cold page to the descent while the map still touches one bucket. So 4× is a floor, not a ceiling — measured where the tree looks good.
And this is not an end-to-end number for the change. It’s the two structures in isolation, which is exactly the claim I’m making — not “the engine got 4× faster.”
⚖️ Trade-offs, and what I got wrong
Something broke silently and stayed broken. Navigation views — the relationship-traversal path — were still populating themselves from the primary key index. When it vanished they didn’t throw; they just quietly stopped finding things, and it took a dedicated port to entity-map iteration to fix them. A structure with 43 references across 14 files has 43 chances to be load-bearing in a way no test covers. If I did it again I’d land the new structure first and run both in parallel, so a divergence surfaces as a mismatch rather than an absence.
The engine is too quiet about the queries it won’t run. Typhon’s “indexed fields only” rule is deliberate and I’d defend it — it’s what makes query cost predictable. But the enforcement doesn’t match the intent: when the planner can’t find a usable indexed field it still produces a plan with PrimaryFieldIndex = -1, and the executor then short-circuits, so a Count on such a query returns zero rather than an error. A design constraint should announce itself. Returning an empty result for a question you’ve decided not to answer is the worst of both worlds, and making that path fail loudly is outstanding work.
And none of this means B+Trees were the problem. They’re still here, they’re still the right answer for every secondary index, and they still key on the full EntityId rather than the 48-bit key — deliberately, so an index scan can filter by archetype without a second lookup. The change wasn’t “trees are slow.” It was that one specific tree was selling a feature nobody was buying.
🎯 The takeaway
The reusable idea isn’t “replace your primary key index with a hash map.” It’s the question that found it: what is this structure doing that nobody ever asked it to do?
That’s a different question from “is this fast,” and it finds different things. A profiler tells you the tree probe costs about 185 ns. It will never tell you that roughly three-quarters of that is maintaining an ordering no caller has read. Cost you can see; unused capability is invisible, because from the inside it looks exactly like the structure working correctly — the tree wasn’t malfunctioning, it was doing precisely what a B+Tree is supposed to do.
And unused capability is what inherited assumptions turn into. “The primary key needs an index” — true, never in doubt. “Therefore it’s a B+Tree” — the part nobody says out loud, imported whole from relational databases, where it’s correct because in a relational database you really do want WHERE id BETWEEN 100 AND 200 to work. Typhon isn’t that. An entity id is a handle with no semantics, the engine won’t let you query on it, and the moment you write those two facts next to each other the tree stops making sense.
So: go find the structure in your system that’s more capable than its callers. The ordered collection nobody iterates in order. The concurrent dictionary reached from one thread. The cache with an eviction policy for entries that are never evicted. Each of those charges you on every operation for a guarantee nobody wanted, and none of them will ever show up as a bug.
Pay for the properties you use. Every other one is a tax you’re collecting on yourself.
⏭️ What’s next
That’s four posts in a row of things that went right — version chains that don’t clone rows, a page cache that doesn’t count, a lock that fits in eight bytes, and a tree that turned out to be the wrong shape. Time to balance the ledger.
The next one is a list of things I was simply wrong about, each caught by a measurement that contradicted an intuition I’d have defended in an argument. Integer division that wasn’t cheap. Batching that made spawning four times slower than not batching. A hash table that lost to a linear scan. A Volatile.Read that was protecting nothing on the only architecture we run on.
Post #10: 5 Performance Assumptions That Were Wrong — with the numbers that settled each one.
Follow the GitHub repo for source and benchmarks, or subscribe via RSS.