A web crawler may track billions of URLs. A ride-sharing app may search for nearby drivers across an entire city. A database may keep copies of the same data on many machines and need to check whether those copies still match.

Workloads like these push past what everyday data structures were built for.

Hash sets, B-trees, and sorted arrays are excellent tools. The problem is not that they are bad. The problem is that they usually assume the data fits on one machine, memory is available, and exact answers are affordable.

At billions of items, those assumptions start to break. Sometimes the system needs to save memory. Sometimes it needs to avoid network traffic. Sometimes it needs to answer "close enough" quickly instead of answering exactly slowly.

This section covers eleven data structures that show up in real large-scale systems. They trade a little accuracy, flexibility, or simplicity for big wins in memory, speed, or keeping machines in sync.

A HashSet<String> is fine for a few million entries. A balanced tree is good when you need sorted data. A sorted array works well when data changes rarely and binary search is enough.

But these structures often rely on three assumptions that break in large systems.

Specialized structures replace one expensive assumption with something cheaper.

The cost they reduce is usually not raw CPU. It is memory, lookup time, write pressure, network traffic, or the work needed to keep machines in sync.

The eleven structures in this section fit into four families:

The rest of this chapter walks through each family.

Probabilistic structures answer useful questions without storing every item.

They answer questions like:

They do this by turning inputs into bits, fingerprints, or small counters. They cannot rebuild the original items later. In return, they use far less memory.

The memory difference can be large enough to change the product.

A HashSet of one billion 20-byte identifiers can take tens of gigabytes after hash-table overhead.

A Bloom Filter at a 1% false-positive rate for the same workload uses about 1.2 GB. A HyperLogLog estimating distinct counts uses around 12 KB regardless of whether it sees a million or a billion items.

That is why these structures appear in systems that handle huge or never-ending inputs:

The answer is not always exact. The application must be able to tolerate false positives, counts that are a little too high, or small similarity errors.

Spatial problems are about location and shape. They do not fit cleanly into a normal single-column index.

A B-tree on latitude and a separate B-tree on longitude cannot efficiently answer:

Find all restaurants within 2 km of this location.

The reason is simple: latitude and longitude only make sense together. Two separate indexes do not understand that combined point.

Spatial structures index data by location, region, or shape. They make nearby searches, map-box searches, and shape intersection queries fast by ruling out large areas early.

Here is where each one fits:

A ride-sharing service cannot scan every driver's coordinates for every rider request. A mapping product cannot test every road shape against the visible map area on every pan or zoom.

Spatial indexes make those queries practical by ruling out large regions early. They power PostGIS, MongoDB's 2dsphere index, Elasticsearch geo queries, and the cell-based dispatch indexes used inside ride-sharing systems.

The choice usually depends on where the structure lives and what kind of query the system runs.

Storage engines, in-memory indexes, and ordered caches often need three things at the same time:

Balanced binary search trees support these operations, but their rebalancing logic can be hard to make fast when many threads are writing at once.

Skip Lists solve the problem with a simpler idea: add higher-level "express lanes" above a sorted linked list. Searches use the upper lanes to skip over large parts of the list. Updates usually touch only a few nearby nodes.

The lookup starts in the highest lane. When the next jump would go past the target, it drops down one lane and keeps going.

Skip Lists give expected O(log n) lookups, inserts, and deletes while keeping the implementation relatively small. That simplicity is one reason they work well under concurrent writes.

They appear in LSM-tree memtables such as RocksDB and LevelDB. Redis sorted sets pair a skip list with a hash table, giving ordered range queries plus fast membership checks. Skip Lists also show up in embedded indexes where simple, reliable implementation matters.

The trade-off is that balance is random. Bad cases are unlikely, but not impossible. If a system needs strict worst-case guarantees, a balanced tree may still be the better choice.

Distributed systems often keep more than one copy of the same data. Over time, those copies can drift apart.

That can happen during network partitions, failed writes, delayed replication, or backup jobs. The system needs a cheap way to answer:

Are these two copies identical? If not, which small part is different?

A naive comparison sends every record across the network and compares the bytes. That is fine for small datasets. It is painful for terabytes of data.

A Merkle Tree organizes hashes into a tree:

Two replicas compare their root hashes first. If the roots match, the datasets match. If the roots differ, the systems walk down only the branches whose hashes disagree until they find the changed blocks.

Merkle Trees show up in many places:

The catch is that both sides must build the tree the same way. They must agree on hashing, ordering, byte format, and tree shape. If they disagree on any of those, the trees may look different even when the data is logically the same.

A few common mistakes are worth calling out before the deep-dive chapters:

A single production system may use several of these structures in different layers.

None of these structures replaces hash tables or B-trees everywhere. They solve specific pressure points where the main cost is memory, network traffic, location search, concurrent writes, or replica comparison.

General-purpose data structures stop being enough when the data is too large, too distributed, too location-heavy, or too expensive to compare directly.

The four families in this section handle those pressures:

Each structure gives up being useful for everything so it can become excellent at one specific job.