Word Store with Lexicographic Range Queries

0) Problem Restatement

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 words w with L ≤ w ≤ R in dictionary (lexicographic) order, possibly with a limit or pagination.

The data may be larger than memory.

1) 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).

2) 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 out

3) On Disk (data larger than memory)

• 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).

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"]

4) 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).

5) Why Not a Trie?

A trie is great for prefix lookups in memory, but it uses a lot of memory (pointers per character) and doesn't map well to disk pages. Arbitrary [L, R] ranges are still possible (an in-order traversal), but sorted structures (B+ tree / LSM) are simpler, compact and disk-friendly.

6) Wrap-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.