QuadTree Storage Estimation

In one line: the result — 12 GB for a global spatial index — is the single most consequential number in the chapter, because it means the index fits in one machine's memory.

The calculation

We store the PlaceID, Latitude, and Longitude for each place in the node. Each is 8 bytes. For 500 million places:

(8 + 8 + 8) x 500,000,000 = 24 x 500M = 12 GB

We'll have 500 places in a single node. So, for 500 million places, we'll need 500M / 500 = 1 million leaf nodes.

The QuadTree with 1 million leaf nodes has approximately 1/3 as many internal nodes, and each internal node has four pointers to its children at 8 bytes each:

1,000,000 x 1/3 x 4 x 8 = 10.67 MB

Total = 12 GB + 10.67 MB = 12.01 GB

Every figure reproduces exactly.

Why the internal nodes are a rounding error, and the general rule behind it

The tree structure costs one thousandth of what the data costs. That ratio is not an accident of these numbers — it holds for any tree with a reasonable branching factor and a meaningful leaf capacity.

The reason is the fan-out. Each leaf holds 500 places at 24 bytes each, so 12,000 bytes of payload, while its share of the internal structure is a handful of 8-byte pointers.

Payload per leaf:   500 places x 24 B = 12,000 B
Structure per leaf: ~32 B of pointers in the parent
Ratio:              roughly 375 : 1

The general form is worth carrying: in a tree, structural overhead scales with the number of nodes, and payload scales with the number of items. Raise the items-per-node and the structure becomes free.

That is precisely why B-trees use pages holding hundreds of keys rather than binary nodes, and why the leaf capacity of 500 in Lesson 9 was a good choice for more reasons than query cost.

The practical implication: do not spend estimation effort on the tree structure. If someone asks how much a spatial index costs, the answer is "essentially the size of the data in it." The 1/3 approximation for internal-node count could be off by a factor of three and change the total by 0.2%.

Where the 1/3 comes from

The design asserts "approximately 1/3 as many internal nodes as leaf nodes" without derivation. It is worth a line, because it is a standard result.

In a tree where every internal node has four children, the levels shrink by a factor of four going up:

leaves        L
one level up  L/4
next          L/16
next          L/64
...

That is a geometric series summing to L/3 as the depth grows:

L/4 + L/16 + L/64 + ... = L x (1/4)/(1 - 1/4) = L/3

So 1 million leaves implies about 333,000 internal nodes. Multiply by four pointers of 8 bytes: 333,333 × 32 ≈ 10.67 MB. Exactly the published figure.

Worth knowing the general form — in a tree with branching factor b, internal nodes number about L/(b-1) — because it lets you sanity-check any tree estimate in one line. For a binary tree that is L, which is why binary trees have far worse structural overhead than a quadtree, and dramatically worse than a B-tree.

Note this assumes a full tree, which our deliberately unbalanced tree is not. Real internal-node counts will differ. But at 0.1% of the total, the approximation costs nothing.

What 12 GB means

We can easily store a QuadTree on a server.

Fitting on one server licenses a lot — and one thing it does not

Twelve gigabytes is small. A commodity server has hundreds of gigabytes of RAM, so the entire spatial index for every place on Earth fits in memory with room to spare.

Four consequences, and all of them shape the rest of the design:

Searches never touch disk. Descending twenty levels is twenty memory dereferences — sub-microsecond. Lesson 10's cheap descent depends entirely on this.

Replication is cheap. Lesson 12 puts a quadtree on three servers. At 12 GB that is trivially affordable, and rebuilding a lost replica is a matter of minutes.

Partitioning is optional, not forced. Compare that building block, where the road graph could not fit on one machine and segmentation was therefore mandatory. Here the design partitions for throughput and availability, not because it must.

The whole thing can be rebuilt from the database. 500 million rows into a 12 GB structure is a batch job of minutes to hours, which is what makes Lesson 12's "the key-value store makes it easier to rebuild the quadtree if we lose it" credible.

The thing it does not license is treating capacity as solved. The index is 12 GB, but the queries are not. Lesson 2's hotspots — lunch hour, tourist season — mean one region's leaves absorb a disproportionate share of 60 million daily searches. You replicate not because the data is large but because the read load on parts of it is.

Small data does not imply few servers when the access is skewed. That distinction is worth making explicitly, because the design's "we can easily store a QuadTree on a server" invites the wrong conclusion.

What the tree stores, and the one field the estimate forgets

The estimate counts PlaceID, Latitude, Longitude — 24 bytes per place.

But Lesson 13 says: "We can store a place's rating in the database and in the QuadTree, along with its ID, latitude, and longitude."

So the tree actually holds four fields, not three. Adding a rating — 1 byte as in the schema, or 8 as a decimal — gives:

(8 + 8 + 8 + 8) x 500M = 16 GB    <- with an 8-byte rating
(8 + 8 + 8 + 1) x 500M = 12.5 GB  <- with a 1-byte rating

The estimate of 12 GB predates that decision and is never revised. A 33% understatement at worst, which does not change any conclusion — 16 GB still fits comfortably in memory.

It is worth flagging for a better reason than the number. The rating is in the tree specifically so ranking can happen during the search, without a database round trip per candidate. That is a real design decision — denormalizing a derived value into an index to avoid a lookup — and it is why Lesson 13's daily rating rebuild has to update the tree as well as the database.

Naming the field the estimate forgot shows you traced the design forward rather than taking each lesson in isolation.

The property that makes this choice low-stakes: the tree is derived, not authoritative. The places table is the source of truth, so a lost or corrupted tree costs rebuild time rather than data. That is why holding it in memory and rebuilding on startup is a defensible answer at this data size.

Next: partitioning and keeping the tree available.