Problem RestatementProblem
Google asked: design storage for a large set of words (strings), stored persistently, that supports:
- add and delete words,
- range query: given
[L, R], return all wordswwithL ≤ w ≤ Rin dictionary (lexicographic) order, possibly with a limit or pagination.
The data may be larger than memory.
Key Insight: Keep Words Sorted
If words are kept sorted, all words in [L, R] sit next to each other. A range query = find the first word ≥ L (binary search), then scan forward until a word > R. The cost is O(log n + k), where k = the number of results.
A prefix query ("all words starting with 'app'") is just a range: ["app", "app"], or [app, apq).
In Memory (small data)
A sorted array plus binary search (bisect) for queries, but inserts are O(n). Better: a balanced tree / skip list / sorted container, with O(log n) insert, delete and seek.
from sortedcontainers import SortedList # balanced sorted structure
words = SortedList()
def add(w): words.add(w)
def delete(w): words.discard(w)
def range_query(lo, hi, limit=100):
start = words.bisect_left(lo)
out = []
for w in words.islice(start):
if w > hi or len(out) == limit: break
out.append(w)
return outOn Disk (data larger than memory)
Option A: B+ tree (like a database index):- Keys are sorted in leaf pages linked left to right. Upper levels are small and cached in RAM.
- Query: descend the tree to the leaf containing L (~1 disk read, since the upper levels are in memory), then read leaf pages sequentially until R.
- Inserts and deletes update pages in place (with page splits and merges).
- Writes go to an in-memory sorted buffer (plus a write-ahead log), flushed as immutable sorted files (SSTables), merged in the background.
- A range query merges iterators over the memtable and the SSTables (like merging sorted lists), skipping deleted words (tombstones).
- Great when writes are heavy. Range reads touch several files (mitigated by compaction and sparse indexes).
%%{init: {"look":"handDrawn","handDrawnSeed":7,"theme":"base","fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","themeVariables":{"fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","fontSize":"16px","primaryColor":"#fff4e6","primaryBorderColor":"#1e1e1e","primaryTextColor":"#1e1e1e","secondaryColor":"#e7f5ff","tertiaryColor":"#ebfbee","lineColor":"#1e1e1e","textColor":"#1e1e1e","mainBkg":"#fff4e6","nodeBorder":"#1e1e1e","clusterBkg":"#f8f9fa","edgeLabelBackground":"#ffffff","classText":"#1e1e1e"}}}%%
flowchart LR
Q["range(L, R)"] --> IDX["Top levels in RAM - find leaf for L"]
IDX --> P1["Leaf page with L"]
P1 -->|"next leaf"| P2["Leaf page"]
P2 -->|"next leaf"| P3["... until word > R"]Scaling Out
- Range-partition words across machines by key ranges (a–c, d–f, ...), with split points chosen so shards are equal in size. A query touches only the shards overlapping [L, R], in order.
- Split hot or large ranges automatically (as Bigtable/HBase do).
- Pagination: return a cursor = the last word returned. The next page starts just after it (seek to > cursor).
Deep Dive — Why a sorted structure, and not a trieDeep dive
[L, R] range queries over a large persistent word set. The structure choice is the whole design, and the popular answer is the wrong one.
A hash index
Hash each word to a bucket. Add, delete and exact lookup are all O(1).
%%{init: {"look":"handDrawn","handDrawnSeed":7,"theme":"base","fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","themeVariables":{"fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","fontSize":"16px","primaryColor":"#fff4e6","primaryBorderColor":"#1e1e1e","primaryTextColor":"#1e1e1e","secondaryColor":"#e7f5ff","tertiaryColor":"#ebfbee","lineColor":"#1e1e1e","textColor":"#1e1e1e","mainBkg":"#fff4e6","nodeBorder":"#1e1e1e","clusterBkg":"#f8f9fa","edgeLabelBackground":"#ffffff","classText":"#1e1e1e"}}}%%
flowchart LR
W["apple, banana, cherry"] --> H["hash()"]
H --> B["Scattered across buckets in no order"]
Q["Range query [ban, car]"] --> SCAN["No way to find neighbours"]
SCAN --> ALL["Scan every bucket and test each word"]
ALL --> ON["O(n) per query - the index contributes nothing"]Hashing deliberately destroys order, and order is exactly what the query needs. It is the right structure for the operations this problem does not ask for.
A trie
Store words character by character. Prefix lookups are excellent, and a range query is an in-order traversal between two bounds.
Correct, and it is what most people reach for. Two practical problems. Memory: a node with child pointers per character costs far more than the characters themselves, often several times the raw data. And disk: nodes are small and scattered, so a traversal is a chain of pointer dereferences across pages — the opposite of what a block device wants. A trie is an in-memory structure that does not survive the move to disk gracefully.
Keep the words sorted: a B+ tree or an LSM tree
%%{init: {"look":"handDrawn","handDrawnSeed":7,"theme":"base","fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","themeVariables":{"fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","fontSize":"16px","primaryColor":"#fff4e6","primaryBorderColor":"#1e1e1e","primaryTextColor":"#1e1e1e","secondaryColor":"#e7f5ff","tertiaryColor":"#ebfbee","lineColor":"#1e1e1e","textColor":"#1e1e1e","mainBkg":"#fff4e6","nodeBorder":"#1e1e1e","clusterBkg":"#f8f9fa","edgeLabelBackground":"#ffffff","classText":"#1e1e1e"}}}%%
flowchart LR
SORT["Words kept in sorted order"] --> SEEK["Seek to L - O(log n)"]
SEEK --> SCAN["Scan sequentially until R"]
SCAN --> OUT["Results - cost is proportional to what is returned"]
BP["B+ tree - leaves are sorted pages, linked"] --> DISK["One page read per few hundred words"]
LSM["LSM tree - sorted runs merged in the background"] --> WR["Sequential writes, ranges merge across runs"]- A range is a seek plus a sequential scan, so the cost is proportional to the size of the answer rather than the size of the data.
- Pages, not pointers. Leaves hold hundreds of words in sorted order, so one disk read produces a large run of results and the scan follows linked leaves sequentially — the access pattern disks are built for.
- Pick by workload. A B+ tree gives predictable in-place reads and updates; an LSM tree gives much faster writes at the cost of merging reads across sorted runs and background compaction.
Prefix queries, the trie's strong suit, come along for free: prefix* is the range [prefix, prefix + '\xff'], which is the same seek-and-scan. So the sorted structure covers both access patterns while staying compact and disk-friendly — and that is the argument to make when someone suggests a trie.
Wrap-UpWrap-up
Keep words sorted so any [L, R] range is a contiguous run: seek to the first word ≥ L with binary search or tree descent, then scan until > R, giving O(log n + k). In memory, use a balanced sorted structure. On disk, use a B+ tree (read-friendly) or an LSM tree (write-friendly) with prefix compression. Scale by range-partitioning with automatic splits, paginate with the last word as a cursor, and treat prefix queries as ranges.