The R-Tree We Built and Turned Off

17 September 2026 - 28 mins read time
Tags: csharp dotnet database ecs performance spatial typhon

💡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

  1. Why I’m Building a Database Engine in C#
  2. What Game Engines Know About Data That Databases Forgot
  3. Microsecond Latency in a Managed Language
  4. Deadlock-Free by Construction
  5. Three Durability Modes, One WAL
  6. Building a Page Cache That Doesn’t Count
  7. MVCC at Microsecond Scale
  8. The 8-Byte Lock
  9. Why We Eliminated the Primary Key B+Tree
  10. The R-Tree We Built and Turned Off (this post)
  11. 125,000 Spatial Queries in 23 Milliseconds (coming soon)

Octocat GitHub repo  •  :mailbox_with_mail: Subscribe via RSS

🕯️ A personal note, before the technical part. 🕯️

This blog has been quiet since July. I lost my father recently, to cancer, and writing was not where my head was.

He was my number one believer. Always, from the very beginning, without conditions and without a single gap. I am grateful for everything he taught me, and for everything he did for me over the years.

Last time I promised a list of performance assumptions that turned out to be wrong. One of them grew into a whole post, so the list waits another round.

Here is the line at the centre of it, straight out of Typhon’s spatial options:

public const int DefaultCellTreePromoteThreshold = int.MaxValue;

That is a promotion threshold. Typhon’s spatial index can swap a dense region of the world from a linear scan over bounding boxes to a real R-Tree over the same boxes: O(log C) descent instead of O(C) scan, where C is the number of boxes. The tree exists. It is implemented, tested against the scan for identical results, profiled, and in September I went and vectorised it.

The shipped default says: never build one. Not “build one when the cell gets dense”. Never, at any density, unless the application explicitly asks for it.

Before we go further, let me narrow the claim, because the title oversells it a little. The R-Tree is still in the engine and it is still the right answer for some workloads. The threshold is a public option precisely because I cannot make that call for you. What I can tell you is that on the one game-shaped workload I measured properly, forcing it on made the tick 1.43× to 1.75× slower at every density I tried, including the densities where the tree genuinely made the query faster.

Faster query, slower tick. That gap is the whole post, and it took me three separate measurements to work out why. Each one is a different way of being wrong about what a data structure costs.

🗺️ Where the query actually goes

Some structure first, because the argument depends on knowing which layer we are talking about.

Typhon has exactly one spatial index, built from two levels. The first is a coarse cell grid: the world divided into fixed-size cubes, sparse, so an empty region costs one absent hash entry rather than a descriptor. A position maps to a cell in O(1), and a query box maps to the handful of cells it overlaps.

The second level lives inside each occupied cell. Entities are not indexed individually. They are grouped into clusters of up to 64 that share a cell and a contiguous chunk, and each cluster carries one bounding box. So inside a cell, one archetype’s index is an array of cluster boxes. A query scans that array, opens the clusters whose box overlaps, and then tests those clusters’ entities one by one.

Three stages, and the costs land very differently on each:

A spatial query resolves in three stages. First the grid maps the query box to a handful of cells — a sparse O(1) mapping, and the pruning that matters, done before any per-cell structure is consulted. Second, inside one cell, the broadphase decides which structure tests the cluster boxes, where C is how many cluster boxes that one cell holds and the three rows are three densities. A linear SoA scan of six float compares per cluster, eight per SIMD instruction, costs 6.8 ns in a typical cell at C equals 4, 102 ns when very dense at C equals 512, and 403 ns at the crossover at C equals 2048. An opt-in per-cell R-Tree with O(log C) descent and pointer chasing costs 146 ns, 247 ns and 246 ns at those same three densities. The tree only starts winning at C of about 2048, while a real clumped world holds 1.8 cluster boxes per cell and 102 in its worst one. Third, the narrowphase opens the surviving clusters and tests their entities at 0.576 ns each — and that is where a query spends its time, so making the broadphase three to four times faster gains the whole query at most 1.1 times.
The tree only ever competes for stage ②. Stage ① has already thrown away most of the world, and stage ③ is where the time goes.

The R-Tree, when it exists, replaces stage ② inside one cell. It does not replace the grid and it does not touch the narrowphase. That matters, and it is where the first of my three wrong assumptions was hiding.

📉 Wrong assumption #1: the dense cell arrives

The case for promotion is easy to make. A linear scan is O(C) in the clusters in a cell. Real worlds have hot spots — a city, a battle, a spawn point — and in a hot cell C gets large, at which point a narrow query pays for every box in the cell instead of the two or three it geometrically overlaps. That is a real failure mode. A tree fixes it.

So: how large does C actually get?

I measured it two ways. On a synthetic clumped sweep, the mean cell held 1.8 clusters and the single worst cell in the entire world held 102. On SWG Tatooine — a reconstruction of Star Wars Galaxies’ Tatooine, 17 724 entities at its faithful population, ticked through a real system DAG — the densest cell half held 3 clusters. Scaled 16× to 268 944 entities, still on the default 256 m cells: 34.

The crossover where a tree starts to pay is around 2 048.

That is not a near miss, and the reason is stage ①. The grid has already done the pruning. A cell is a small box of world space and a cluster holds up to 64 entities, so a cell carrying 2 048 clusters is carrying something like a hundred and thirty thousand entities of one archetype. If your world is doing that, your cell size is wrong, and no per-cell structure is going to rescue you from it.

I had to deliberately break the configuration to get there. Running Tatooine at 16× with 16 384 m cells — the entire planet as a single cell, a grid four hundred times too coarse — finally produced 8 021 clusters in one half. Keep that run in mind, because it is the one where the tree wins the query.

So: a structure whose advantage begins in the tail needs you to check that you actually have a tail. “It degrades gracefully under clustering” is only worth paying for if the clustering is reachable from a configuration a sane person would choose.

⚡ Wrong assumption #2: the crossover stays where you left it

This next one is more interesting, and I did it to myself.

Both structures do the same geometry: test an axis-aligned box against a query box, six float compares. The tree does it at a few nodes, the scan does it at every cluster. That is the classic trade, and where the crossover sits is a function of the constant factors.

Constant factors move. In September I vectorised both structures, and here is the bit I had not thought about: they are not equally vectorisable.

The linear scan is a structure-of-arrays layout, six contiguous float[], and the whole operation is embarrassingly wide. This is the actual broadphase kernel, unabridged:

ulong mask = 0UL;
int i = 0;
if (Vector256.IsHardwareAccelerated)
{
    var qMinX = Vector256.Create(minX);
    var qMinY = Vector256.Create(minY);
    var qMaxX = Vector256.Create(maxX);
    var qMaxY = Vector256.Create(maxY);

    for (; i + 8 <= count; i += 8)
    {
        int b = start + i;
        var m = Vector256.GreaterThanOrEqual(Vector256.Create(aMaxX, b), qMinX)
              & Vector256.LessThanOrEqual(   Vector256.Create(aMinX, b), qMaxX)
              & Vector256.GreaterThanOrEqual(Vector256.Create(aMaxY, b), qMinY)
              & Vector256.LessThanOrEqual(   Vector256.Create(aMinY, b), qMaxY);
        // … the Z axis, for a 3D archetype …
        mask |= (ulong)m.ExtractMostSignificantBits() << i;
    }
}

Eight clusters per instruction, 64 per batch, the result a ulong of set bits the caller walks. No branches in the loop, no pointers to follow, the prefetcher doing exactly what it exists for.

The tree can be vectorised too. Its leaf and internal nodes are also SoA, so the comparisons inside a node go eight or sixteen at a time just as happily. But only inside a node. Between two nodes there is a pointer to follow and a version to validate, and there is no vector instruction that makes a dependent load arrive sooner.

Here is what that asymmetry is worth. Best of nine interleaved rounds, one binary with a switch, C is clusters in the cell, and the query is selective — it returns a handful of hits:

C scan, scalar scan, SIMD best tree
4 7.0 ns 6.8 ns 146 ns
16 12.3 10.4 183
64 35.7 18.2 216
512 313.3 102.1 247
2 048 1 359.8 403.4 246

Vectorising the scan bought 49 % at C = 64, 67 % at 512, 70 % at 2 048. Vectorising the tree’s internal-node classification bought 12–14 %.

Read that table against the old scalar scan and the tree wins from about 512. Read it against the vectorised scan and the tree first wins at 2 048. Same work, applied honestly to both structures, and the crossover moved four times further away from the thing I had spent the effort on.

The tree also never wins a broad query at any density, because there is nothing to prune. At C = 512 with everything matching, the scan costs 346 ns and the tree 3 100.

The general lesson, and it is the one I would actually hand to someone else: a crossover point is not a property of two algorithms. It is a property of two implementations on this year’s hardware, and it moves every time you touch either one.

🧠 Why the scan is fast in the first place

I have been talking about SIMD as if width were the whole story. It is not, and if you take one thing away from this post I would rather it were this section than the R-Tree.

The reason a linear scan can beat a tree is not mainly that it does eight compares at once. It is that it never has to wait for the machine to tell it where to look next.

Let me put actual numbers on it. Everything below is a Ryzen 9 7950X, Zen 4, boosting to 5.7 GHz, which makes one cycle 0.175 ns.

What one load costs on a Ryzen 9 7950X, Zen 4 at 5.7 GHz where one cycle is 0.175 nanoseconds. L1 data cache is 32 KB at 4 cycles or 0.7 ns; L2 is 1 MB at 14 cycles or 2.4 ns, three times L1; L3 is 32 MB at about 50 cycles or 8 to 9 ns, twelve times L1; DRAM is 61 to 73 ns, about ninety times L1. And you never load a byte, you load a 64-byte line: reading one int out of a line you touch nowhere else costs 61 ns for 4 useful bytes with 60 thrown away, while reading all sixteen ints in that line costs the same 61 ns, under 4 ns each. Sequential access, the linear scan, loads A then B then C then D with all addresses known in advance, so Zen 4's six prefetchers run ahead and the line is there before you ask, misses overlap, and the latency amortises over everything already in flight — the hardware was built for this. A pointer chase, the tree descent, loads A which holds B's address, then loads B which holds C's address, then loads C: the address is the data you are waiting for, nothing can be prefetched, nothing overlaps, and the 320-entry reorder buffer has no independent work to fill the stall with, so the latencies add up. Three dependent loads that miss to DRAM is about 200 ns of pure waiting, and in that same 200 ns a prefetched vectorised linear scan walks about a thousand cluster boxes.
The ratio from L1 to DRAM is about 90×. Everything in a modern data structure design is an argument about which rung of that ladder you land on, and how often you have to wait for the answer before you can ask the next question.

More in-depth explanation (for the curious)

Three facts, and they compound.

You never load a byte. You load a line. The smallest thing that moves between DRAM and the CPU is a 64-byte cache line. If you read one int from a line and touch nothing else in it, you have just paid 61 nanoseconds for four useful bytes and thrown sixty away. Read all sixteen ints in that line and it is the same 61 nanoseconds, under 4 ns each. Data layout, in one sentence, is the practice of making sure that everything you drag across that bus is something you were going to want anyway.

The gap between the rungs is enormous, and it is a latency gap. L1 at 0.7 ns, L2 at 2.4, L3 at 8–9, DRAM at 61–73. Bandwidth you can usually overlap; latency you can only hide if the machine knows in advance what to fetch. When it does not, the core simply stops. A 5.7 GHz processor waiting 61 ns for DRAM has burned about 350 cycles doing nothing, and on Zen 4 that is enough time to have retired several hundred instructions if it had any it was allowed to run.

Which brings us to the thing that actually decides it: dependent loads. Zen 4 has six hardware prefetchers and a 320-entry reorder buffer. Walk an array in order and the prefetchers spot the stride, run ahead of you, and the line you are about to want is already on its way. Ten misses can be in flight at once, so ten times 61 ns costs you roughly 61 ns, not 610. This is why “it’s O(n)” is so often a lie about the wall clock: the machine is doing your n iterations several at a time whether you asked it to or not.

Now chase a pointer. To load node B you must first have read node A, because A is where B’s address lives. The address is the data you are waiting for. Nothing can be prefetched, nothing overlaps, and the reorder buffer fills up with instructions that all, eventually, depend on that one load. The latencies stop overlapping and start adding.

Three levels of tree, three cache misses out to DRAM, and you have spent roughly 200 nanoseconds doing nothing but waiting. In that same 200 ns the vectorised linear scan gets through about a thousand cluster boxes.

That is the mechanism behind the table in the previous section. Look again at C = 4: the scan costs 6.8 ns and the tree 146. Four boxes is 96 bytes of float data, one and a half cache lines, and after the first access the whole thing is in L1 and stays there. The tree answers the same question by touching a root node and a leaf node in different chunks, validating a version counter at each, and it pays 20× for it. Not because it did more arithmetic. Because it spent its time waiting, and the scan spent its time computing.

And it explains the shape of the whole curve. As C grows, the scan’s cost rises smoothly — 6.8, 10.4, 18.2, 102, 403 — because it is bandwidth-bound over contiguous memory and the prefetcher keeps up. The tree’s cost is almost flat — 146, 183, 216, 247, 246 — because it is latency-bound on a handful of dependent loads whose count grows logarithmically. Flat is the right shape for a tree and it is a genuine achievement of the data structure. It just starts so high that the scan has to get to two thousand boxes before flat becomes an advantage.

Then there is the update side, which is where a dynamic tree really bleeds. A cluster’s bounding box changes whenever an entity inside it moves. In the linear index that is six float stores into an array you were about to touch anyway. In the tree it is a leaf update and then a refit walking back up the ancestors, which is the same pointer chase as the descent, in reverse, except now you are writing. A write needs the line in exclusive state, which means a coherency transaction rather than just a load, and on Zen 4 a line contended between cores costs 20–25 ns inside a CCD and 76–80 ns across the two CCDs.

Measured, that comes out as a tree update being 20.8× dearer than six float stores at 512 clusters and 29.9× at 1 563. Motion hysteresis absorbs about 97 % of moves before they ever reach the index, which brings it down to 61 ns against 23 ns per moved cluster — expensive, but survivable on its own.

Hold that thought. It is not survivable in combination with the last section of this post.

⏱️ Wrong assumption #3: the broadphase is the query

Suppose you are past both of those. Your cell genuinely holds thousands of clusters, and the tree genuinely answers the broadphase three to four times faster. Does the query get three to four times faster?

No. It gets at most about 1.1× faster, because the broadphase was never the query.

Go back to the first diagram. Stage ② decides which clusters to open. Stage ③ opens them and tests their entities individually at 0.576 ns each, and a cluster holds up to 64 entities of which a radius query might match a handful. Winning the broadphase by 150 ns, on a query whose narrowphase runs into microseconds, is a rounding error.

This is the most ordinary mistake of the three and the one I would be most likely to repeat. I had a profile that said the broadphase was hot. It was hot relative to the rest of the broadphase. My optimisation effort went to the sharpest peak in the region I happened to be looking at, which is not the same thing as the sharpest peak.

The comment I eventually left on that kernel is blunter than anything I would write in a blog post:

It was a scalar loop over six float arrays while the R-Tree’s leaf scan had already been vectorised, which had the optimisation effort pointed at the path that does not run.

💸 The one that actually decides it: where the cost lands

Everything so far has been about the query. But the tree also has to be maintained, and this is the finding I think justifies the whole post.

We left the update side at 61 ns against 23 ns per moved cluster, which looked survivable. In the dense configuration the ratio at least looked like something you could argue about: those cells were read around 1 200 times a tick and updated around 6 000. Five times more writes than reads, against a 3× win on the broadphase. Not obviously a good trade, not obviously a bad one.

So I forced it on and measured the tick. Tatooine at 16× population, --promote 2 --tightness 1 so that every cell half of two or more clusters becomes a tree, against the shipped scan, three interleaved rounds each, median tick:

Cell size Densest half Scan Forced tree   Finalize phase Interest system
1 024 m 182 clusters 13.94 ms 20.00 ms 1.43× 0.55 → 5.07 ms 5 % slower
4 096 m 959 13.37 23.17 1.73× 0.29 → 8.15 ms 3 % slower
8 192 m 2 550 13.44 23.48 1.75× 0.11 → 8.55 ms 1 % slower
16 384 m 8 021 19.09 30.14 1.58× 0.04 → 10.15 ms 5 % faster

Read the last row carefully, because the whole argument is sitting in it. At 16 384 m — the entire planet as one cell, 8 021 creature clusters, 5 120 interest queries a tick hitting them — the tree does exactly what the theory promises. It makes the interest system 5 % faster.

And it costs the tick 58 %.

One tick, two currencies. On the left, the systems phase: 5120 interest queries a tick against 8021 creature clusters, spread across 64 workers — what the tree buys here is the interest system running 5 percent faster, and that saving is then divided by the pool. On the right, the tick fence, the serial tail: reconciling what the systems moved means refitting every loose leaf of a promoted cell, single-threaded, per archetype — what the tree costs here is the fence's finalize phase going from 0.04 ms to 10.15 ms, paid by one thread at full price. The median tick goes from 19.09 ms scanned to 30.14 ms with the tree, 1.58 times slower. The promotion gate priced both sides in CPU time and they nearly balanced; on the tick they are different currencies, because parallel work is divided by the pool while serial fence work is wall-clock.
The same CPU time, spent in two phases that convert to wall-clock at completely different rates.

The mechanism goes like this. Typhon’s tick has two halves. Systems run first, dispatched as a DAG across the worker pool, and that is where queries live; on this machine that work is divided by 64. Then the tick fence runs: an exclusive window in which the engine reconciles everything the systems moved, and parts of it are irreducibly serial.

A promoted cell’s upkeep lands in the serial part. RefitPromotedCellTrees walks every loose leaf, single-threaded, per archetype, because the R-Tree is single-writer by specification and the fence slices its work by cluster rather than by cell. Around nine thousand creature updates a tick arrive there as 10 ms of wall-clock on one thread, while the query saving is spread across the pool and divided by 64.

Now recall what a refit actually is, from three sections ago. Every one of those nine thousand updates is a pointer chase back up the tree, with a coherency transaction on every line it writes. The cost is not abstract. It is the memory hierarchy, collecting, on the one thread in the tick that cannot afford to wait.

The promotion gate I had written priced both sides in CPU time, and in CPU terms it was close to a wash. It refused to promote here, and it refused for a reason that was nearly right: updates dominate reads in CPU terms too. But “nearly right” is why I deleted the gate instead of tuning it. On the tick, CPU time in the parallel phase and CPU time in the serial fence are not the same unit. One gets divided by the worker count. The other is wall-clock, at full price, and adding cores makes the ratio worse rather than better.

So a data structure’s cost has a query term, an update term, and a phase — and the third one is invisible to every benchmark that measures the structure in isolation.

⚖️ Trade-offs, and what I would still defend

The tree stays. It is not dead code that survived by inertia. It is reachable with one option, it has differential fixtures asserting it returns exactly what the scan returns, and there is a real shape of workload it wins: dense, tightly packed cells, selective queries, far more reads than writes. The crossover is a function of query selectivity and of the query-to-update ratio, and both of those are properties of your application rather than of my engine. The shipped default is “never” because the one game-shaped workload I measured lost at every density. That is a much weaker claim than “trees are wrong here”, and it is the only one I am entitled to.

🎯 The takeaway

The reusable idea is not “linear scans beat trees”. Sometimes they do, at small n, and that is the least interesting thing here.

There are two things worth carrying away.

The first is that big-O counts operations, and the machine does not bill you for operations. It bills you for cache lines and for the time you spend waiting to find out where to look next. A structure that does ten times fewer operations but serialises them behind dependent loads can lose, badly, to one that does the dumb thing across contiguous memory with a prefetcher running interference. That is not a special case or a small-n curiosity. It is the default condition of a CPU where DRAM sits 90× further away than L1, and it gets a little more true every hardware generation, because cores keep getting faster and memory does not.

So when you compare two structures, ask how many dependent memory accesses each one makes and how much of each fetched cache line it actually uses. Those two questions will predict the winner more often than the exponent will.

The second is that a data structure has three costs, not one, and the third has no notation at all.

Three questions, then, before you reach for the structure with the better exponent. Does my data actually reach the density where it wins? Has anyone re-measured the crossover since the constant factors last moved? And when it needs maintaining, which phase pays, and at what exchange rate?

For this one the answers were no, no, and the worst possible one. So the tree is still there, the default says never, and the engine scans.

Build the clever thing. Measure it in the schedule it has to live in. Then be willing to turn it off.

⏭️ What’s next

That is the negative result. The next post is about what the scan is holding up.

SWG Tatooine at full stretch: 20 480 players and 673 536 creatures, 1.07 million entities, ticking in 23 milliseconds on one desktop CPU.

Inside each of those ticks: 81 920 interest queries — four per player, one per queried archetype, each a 192 m radius — plus 43 298 aggro queries from the creature AI. A hundred and twenty-five thousand spatial queries per tick. The interest queries alone average 599 hits each and return 49 million matched entities, which at 10 Hz is 491 million a second. All of it inside 23 ms, with 553 ms of CPU compressed into that window.

I will walk through the design that gets there — why spatial bookkeeping is per-cluster and never per-entity, the AVX-512 narrowphase kernel that tests 16 entities per pass, and a batching trick that cut the fixed cost of an interest query by an order of magnitude, which came from noticing that twenty players standing near each other are asking almost the same question.

Post #11: 125,000 Spatial Queries in 23 Milliseconds — and then, finally, that list of wrong assumptions.

Follow the GitHub repo for source and benchmarks, or subscribe via RSS.