Data structures and storage engines
Data structures in practice
Choosing data structures by memory layout, access pattern and the operations that matter, with the common ones for arrays, hash maps, heaps, trees, caches and graphs.
Textbook data structures come with big-O costs, and those costs are a good start. In real systems, two other factors often decide the result. One is memory layout: whether the data is contiguous or spread across the heap, and whether it fits in cache. The other is which operations dominate: lookups, inserts, ordered scans or removals from the front. Choosing well means considering both.
A structure that is O(log n) on paper can lose to an O(n) scan over a small contiguous array. The array fits in cache lines and the CPU prefetches it, while the tree chases pointers to random memory.
The big idea
Pick a structure by asking three questions:
- What do I do most often? Look up by key, scan in order, find the minimum, or remove the oldest?
- How big does it get? A few hundred items and a few million items call for different choices.
- Where does it live? In cache, in RAM, or on disk, which changes the cost of each jump.
Concepts in this topic
| Step | Concept | What it answers |
|---|---|---|
| 1 | Arrays and memory layout | Why contiguous data is fast, and when a ring buffer wins |
| 2 | Hash maps | How do keys map to buckets, and when do they degrade? |
| 3 | Heaps and top-k | How do you keep the k largest items cheaply? |
| 4 | Sorted trees, skip lists and tries | How do you keep keys ordered, and search by prefix? |
| 5 | LRU caches | How do you evict the least recently used item in constant time? |
| 6 | Graphs and topological sort | How do you order tasks with dependencies? |
For probabilistic structures that trade exactness for size, such as Bloom filters and HyperLogLog, see probabilistic data structures.
A quick decision guide
Start with the dominant operation and the expected size. A few hundred items with simple access? Use the simplest structure, often an array, since it's fast and easy to test. Millions of keys with range queries? Use a sorted tree, or a B+tree if the data lives on disk. Repeated top-k queries? Use a heap. Repeated eviction of old items? Use an LRU. Dependencies between tasks? Use a graph with a topological sort.
Then measure. A simple array often beats a clever structure on real data, because the locality and the constant factors matter more than the asymptotic class at your size.
Common mistakes
- Choosing a structure by big-O alone and ignoring cache behavior.
- Using a hash map when a sorted array with binary search would give range queries for free.
- Treating a data structure as safe under adversarial input. Hash maps and sorting can be attacked with crafted keys.
Key takeaways
- Choose by the dominant operation, the expected size and where the data lives.
- Contiguous structures often beat asymptotically better pointer-based ones.
- Know the standard combinations: hash map plus list for LRU, heap for top-k, graph plus topological sort for build order.
Further learning
Start with arrays and memory layout. It explains why the same big-O can run at very different speeds.
Related
The memory hierarchy
From registers to SSDs to the network, the latency numbers that dominate performance, and why the tier your data sits in matters more than the code you write.
Performance and profiling
How to find where time goes before you optimize. Percentiles, two predictive laws, sampling profilers, off-CPU waiting and honest benchmarks, with a worked investigation of a slow endpoint. Start here for the performance toolkit.
Probabilistic data structures
Compact structures that answer membership, distinct-count, frequency, sampling and similarity questions with a small, bounded error. Start here for the family and how to choose one.
Coding interviews
Patterns, problem-solving process and communication for algorithm interviews — plus how practical coding rounds differ.