Data Structures for Systems
Data structures for system design: bloom filters, tries, skip lists, and their applications.
What is a data structure?
A data structure is a deliberate arrangement of data that makes some operations cheap and accepts costs elsewhere. An array makes indexed reads cheap because values are contiguous. A hash table spends extra memory to make key lookup fast. A balanced tree does more work per lookup so keys remain ordered.
The core invariant is simple: choose for the operations and semantics the system must preserve, not for a structure's popularity. Name the dominant reads and writes, decide whether answers must be exact or ordered, then check the cost at realistic scale.
Big O describes how work grows, not how fast a particular implementation runs. Allocation, cache locality, key distribution, load factor, and value size can decide the winner when two choices have the same asymptotic cost.
Choose from the dominant operation
Do not begin with a favorite structure. Begin with the operation consuming the latency or memory budget, then verify the choice against representative data.
1 Workload
Name the required operations
List indexed reads, key lookups, inserts, deletes, ordered scans, membership tests, and relationship traversals with their expected frequency.
2 Contract
Preserve the needed semantics
Decide whether answers must be exact, keys must stay ordered, priority must be visible, or relationships must be traversable.
3 Budget
Check time and memory bounds
Compare expected and worst-case time, per-item overhead, allocation behavior, and cache locality at target scale.
4 Evidence
Benchmark representative data
Measure the actual runtime and data distribution because constants, skew, and implementation details can dominate the theoretical model.
Choose from the operation, not the name
Select the work on the critical path, then add semantic constraints. The ranking changes when exactness or order is part of the contract.
Read complexity as a growth model
Let n be the number of stored items, m the length of a key, V the number of graph vertices, and E the number of graph edges. These symbols identify what makes the work grow.
O(1)
Constant
Work does not grow with n
O(log n)
Logarithmic
Doubling n adds about one step
O(n)
Linear
Doubling n roughly doubles work
O(V + E)
Graph traversal
Visit vertices and their edges
- Expected versus worst case: Hash-table lookup is expected O(1), but adversarial collisions can make it O(n).
- Amortized cost: A dynamic-array append is usually O(1), with occasional O(n) growth spread across many appends.
- Output-sensitive cost: A tree range scan is O(log n + k), where
kis the number of returned items. - Key-sensitive cost: Trie work is O(m), so long keys matter even when the collection size does not.
Never label every binary tree operation O(log n). An unbalanced binary search tree can become a chain and degrade to O(n). The logarithmic guarantee requires a balancing strategy such as an AVL or red-black tree.
Put time, memory, and semantics in the same budget
The fastest theoretical lookup may exceed the memory budget, while the smallest representation may weaken correctness. Use the model below to see why a production decision needs all three dimensions.
Make the hidden costs visible
Compare simplified in-memory representations for membership lookup. Scale the dataset and tighten the memory budget to reveal where asymptotic cost, locality, and exactness diverge.
45.8 MiB
Estimated memory
2
Lookup touches
Medium
Cache locality
Exact
Membership answer
Model assumption: 48 bytes per item for this simplified representation. Real runtimes vary by value size, allocator, load factor, and implementation.
This representation fits the contract
Hash table stays within budget and satisfies the requested membership semantics.
What Big O reveals
Lookup work grows as an expected constant.
What Big O hides
Expected constant lookup trades extra capacity and bucket metadata for speed.
Recognize the major structure families
The family tells you which relationship the representation preserves. The implementation determines the exact constants and operational behavior.
Position
Sequence
Arrays, linked lists, stacks, and queues organize values by position or insertion order. They differ in locality and which end can be changed cheaply.
Key
Associative
Hash tables associate a key with a value. They optimize exact lookup but do not preserve sorted key order.
Comparison
Ordered and priority
Balanced trees, heaps, and tries preserve sorted order, an extreme value, or a shared key prefix.
Specialized
Relationship and filter
Graphs model arbitrary relationships. Bloom filters answer a narrower approximate-membership question with very little memory.
Use the reference by decision boundary
Open a structure after identifying the operation you need to protect. Each entry names the useful operation profile and the condition that should make you reconsider it.
An array stores values contiguously and addresses a value by its numeric position. Dynamic arrays reserve spare capacity and occasionally allocate a larger region.
- Critical path: Indexed reads are O(1); iteration has strong cache locality.
- Updates: Append is amortized O(1). Inserting or deleting in the middle is O(n) because later values move.
- System uses: Batches, time-series chunks, image buffers, lookup tables, and the storage beneath many heaps.
- Boundary: Use a hash table for key lookup, or a linked representation when stable nodes and frequent known-position splices matter more than locality.
Compose structures around the full workload
Production components often combine representations because one structure rarely makes every required operation cheap.
Hash table + linked list
LRU cache
The hash table finds a cache entry by key in expected O(1). A doubly linked list moves that known entry to the most-recent position and evicts the oldest in O(1).
Heap + identity map
Mutable priority queue
The heap selects the next job. A map finds a job's heap position when its priority changes or it must be cancelled.
Bloom filter + database
Filtered exact store
The filter rejects definite misses in memory. Possible matches continue to the exact database, preserving correctness while reducing expensive reads.
Validate the production choice
Before committing to an implementation:
- Record operation frequencies, latency targets, peak item count, and value sizes.
- Verify semantic requirements such as exactness, ordering, duplicates, stable references, and concurrency.
- Model both expected and worst-case behavior, including resize, rebalance, collision, and skew paths.
- Measure total memory, not only payload bytes: include capacity, links, buckets, allocator metadata, and garbage-collector cost.
- Benchmark representative distributions and access patterns at target scale.
- Define the signal that would trigger a different structure or a composite design.
Choose the simplest structure that meets the measured contract. An advanced representation without a workload reason increases implementation and operational risk without buying useful performance.
Continue learning
- Design Principles: Frame engineering choices around explicit constraints and trade-offs.
- Performance Optimization: Measure bottlenecks and distinguish algorithmic growth from implementation cost.
- Trie: Explore prefix indexing and memory-performance tuning in depth.
- Consistent Hashing: See how hash-based ownership changes when a distributed cluster grows.