Free lesson · System Design Fundamentals

Why Regular Data Structures Aren't Enough at Scale

Hard8 min readsystem-designhlddistributed-systems

Lesson 23.1 - Why Regular Data Structures Aren't Enough at Scale

The first lesson of Module 23.

You know arrays, hash maps, binary search trees, heaps, stacks, queues, and graphs. These are the building blocks of every algorithm course and every coding interview. They're essential. They're also insufficient for the problems that emerge at scale - not because they're wrong, but because they optimize for the wrong thing when the dataset is billions of records, the query is approximate, or the access pattern is spatial.

Consider a ride-sharing app like Uber. A rider opens the app and the system must answer: "which drivers are within 2 km of this rider, right now?" The system has 100,000 active drivers in a city, each with a continuously-updating latitude/longitude. A hash map maps driver IDs to locations - O(1) lookup by driver ID. But the query isn't "where is driver X?" - it's "which drivers are near coordinates (40.7128, -74.0060)?" A hash map can't answer proximity queries. A sorted array (sorted by latitude, or by longitude, but not both simultaneously) can narrow the search to one dimension but not two. A balanced BST has the same limitation - it orders by ONE key, not by two-dimensional proximity. Finding "all points within 2 km of a location" in a hash map or BST requires scanning ALL 100,000 drivers and computing the distance to each - O(N) per query, hundreds of milliseconds, too slow for real-time ride matching.

Spatial data structures (Geohash, Quad Trees, R-Trees, S2/H3) solve this: they organize data by spatial proximity so that "find all points near this location" is O(log N) or O(√N), not O(N). Uber uses H3 (hexagonal hierarchical spatial index) for exactly this problem.

Now consider a different problem: a web crawler has visited 10 billion URLs. Before crawling a new URL, it must check: "have I already visited this URL?" A hash set provides O(1) lookup - perfect semantics. But 10 billion URLs × 100 bytes per URL = 1 TB of memory for the hash set. That doesn't fit in RAM. You could use a disk-based hash set, but each lookup requires a disk read - too slow at the crawler's throughput of 10,000 URLs per second.

Bloom filters solve this: a probabilistic data structure that answers "is this URL in the set?" using only 1.2 GB of memory (1.2 bytes per URL instead of 100 bytes) with 1% false positive rate. The trade-off: it might say "yes, you've visited this URL" when you haven't (a false positive - the crawler skips a URL it hasn't actually visited). But it NEVER says "no" when the answer is "yes" (no false negatives - the crawler never re-visits a URL it has already crawled). For a web crawler, a 1% false positive rate is acceptable - missing 1% of URLs is fine. Saving 99% of memory is essential.

These are the problems this module covers: queries and operations that general-purpose data structures handle poorly at scale, and the specialized data structures designed for each.

The Four Problem Categories

Category 1: Spatial Queries (Lessons 23.2-23.5)

The problem: given a set of points in 2D (or 3D) space (latitude/longitude, x/y coordinates), answer queries about spatial relationships: "find all points within R distance of location P," "find the K nearest points to P," "find all points within this rectangular/polygonal region."

Why general-purpose structures fail: hash maps organize by key, not by proximity. BSTs order by one dimension. Neither supports efficient two-dimensional range queries or nearest-neighbor queries. A 2D range query on a hash map is O(N) - check every point. On a BST sorted by latitude: O(√N) for latitude range but still O(N) for the longitude filter within that range.

Specialized structures:

Category 2: Probabilistic Data Structures (Lessons 23.6-23.10)

The problem: answer questions about massive datasets - set membership ("is X in the set?"), cardinality ("how many unique elements?"), frequency ("how many times does X appear?"), similarity ("how similar are sets A and B?") - using far less memory than exact data structures, accepting a small probability of error.

Why general-purpose structures fail: exact data structures (hash sets, hash maps, counters) use O(N) memory - proportional to the dataset size. At billions of elements, this is terabytes of memory. The queries often don't need exact answers: "approximately 14.2 million unique visitors ± 0.5%" is as useful as "exactly 14,203,847 unique visitors" for a dashboard. Trading exactness for memory efficiency - from terabytes to megabytes - is an enormous practical win.

Specialized structures:

The unifying principle: probabilistic data structures trade exactness for dramatic memory reduction. A Bloom filter uses 10x less memory than a hash set. A HyperLogLog uses 12 KB to count unique elements regardless of whether there are 1,000 or 10 billion - a hash set counting 10 billion elements would need ~100 GB. The error is bounded, configurable, and well-understood mathematically.

Category 3: Structural Data Structures (Lessons 23.11-23.12)

Skip Lists (23.11): a randomized alternative to balanced binary search trees (AVL, red-black trees). Skip lists provide O(log N) search, insert, and delete - the same complexity as balanced BSTs - but with a simpler implementation (no rotations, no rebalancing). Redis uses skip lists for sorted sets (ZRANGEBYSCORE, ZRANK) - Antirez (Redis creator) chose skip lists over red-black trees because they're simpler to implement, have better concurrent-access properties, and their performance is equivalent in practice.

Merkle Trees (23.12): a tree of hashes where each leaf is the hash of a data block, and each internal node is the hash of its children's hashes. Changing any data block changes its leaf hash, which changes its parent's hash, which propagates to the root. By comparing root hashes, two parties can determine whether their datasets are identical - and if not, efficiently identify which blocks differ. Git uses Merkle trees for commit integrity. Bitcoin uses them for transaction verification. Cassandra uses them for anti-entropy repair (detecting and fixing inconsistencies between replicas).

The Scale Threshold

These specialized structures aren't needed at small scale. A hash set with 10,000 elements uses ~1 MB of memory - no need for a Bloom filter. A table with 100,000 rows and a B-tree index handles spatial queries via full-scan-with-filter in milliseconds - no need for an R-tree. A COUNT(DISTINCT user_id) on 1 million rows runs in seconds - no need for HyperLogLog.

The specialized structures become necessary at specific scale thresholds:

The interview signal: knowing WHEN to use a specialized data structure - not just what it is - demonstrates system design maturity. An interviewer asking "design a URL shortener that checks for duplicate URLs" wants to hear: "at 10 billion URLs, a hash set would require ~1 TB of RAM. A Bloom filter with 1% false positive rate uses ~1.2 GB. The false positives mean we occasionally generate a new short URL for a URL that already has one - acceptable because the cost of a duplicate short URL is low. The 1,000x memory reduction is essential because the service must fit in a single machine's RAM."

How This Module Is Organized

The remaining eleven lessons each cover one data structure in depth:

For each data structure, the lesson covers:

1. The problem it solves - what query or operation is it designed for?
2. The intuition - how does it work, conceptually, before the math?
3. The mechanism - how the data structure operates internally, with diagrams
4. The math - the key formulas (error rate, memory usage, time complexity)
5. Where it's used in production - specific systems and companies
6. The trade-offs - what you give up (exactness, deletion support, memory) and what you gain
7. When to use it - the scale threshold and the decision criteria

The first four lessons (23.2-23.5) cover spatial data structures - starting with Geohash (the simplest), progressing through Quad Trees and R-Trees (more sophisticated), and ending with S2/H3 (the industry standard for large-scale spatial systems).

Six Takeaways from This Lesson

1. General-purpose data structures (hash maps, BSTs, arrays) are insufficient for specific problems at scale: spatial proximity, probabilistic membership, cardinality estimation, similarity, and integrity verification.

2. Spatial data structures (Geohash, Quad Tree, R-Tree, S2/H3) organize data by two-dimensional proximity - enabling "find nearby" queries in O(log N) instead of O(N).

3. Probabilistic data structures (Bloom filter, HyperLogLog, Count-Min Sketch, MinHash) trade exactness for 100-1,000x memory reduction - answering approximate queries on billions of elements using kilobytes to megabytes.

4. Each specialized structure solves ONE specific problem. Bloom filters answer set membership. HyperLogLog answers cardinality. R-Trees answer spatial range queries. Don't force one structure into another's problem domain.

5. Scale thresholds determine when to switch from exact to specialized. Below the threshold: use hash maps, hash sets, B-trees. Above the threshold: specialized structures become essential.

6. These structures are production infrastructure, not academic exercises. Redis (Skip Lists), Cassandra (Bloom filters), PostgreSQL/PostGIS (R-Trees), Git (Merkle trees), Google Maps (S2), Uber (H3) - every major system uses them.

What's Next

Lesson 23.2 covers Geohash - encoding latitude/longitude into a string where nearby locations share a common prefix, converting 2D proximity queries into 1D string prefix matching.

Back to System Design Fundamentals