Skip to content
Hari KharelStudy

Secondary indexes and query design

intermediateCommon atStripeAnthropicAmazonGoogleRead firstHash mapsSorted containersPractise in the Sandbox →

The primary map (id → record) answers “get by id” in O(1). Every other question (“all records in Oslo”, “battery between 20 and 40”) is a scan, O(n), unless you add a secondary index: a second map from a field’s value to the ids that have it (hash index, for equality) or a sorted structure (ordered index, for ranges). Indexes are derived data: every write must update them in the same method, removing the old entry before adding the new one. In SQL, a composite index on (a, b) helps queries that constrain a leading prefix: a, or a then b, but not b alone.

The idea in plain words

Section titled “The idea in plain words”

A book has its pages in order (the primary data) and an index at the back: “hash maps, see pages 12, 48, 97”. The index doesn’t contain the content, only pointers to it. It makes one kind of question fast, and it costs something: every time a page changes, someone has to fix the index.

In code, the index is literally another map:

  • Primary: vehicles = { "v3": {city: "Oslo", status: "busy"}, ... }
  • Secondary: by_city = { "Oslo": {"v1", "v3"}, "Lima": {"v2", "v5"} }

find(city="Oslo") becomes one lookup plus reading the matching ids, instead of walking every vehicle.

The danger is drift. Update v3’s city to Lima and forget to remove it from by_city["Oslo"], and the index now lies. Queries return a vehicle that isn’t there. That bug is what interviewers watch for in the level that adds a query.

See it

Section titled “See it”

Change a vehicle’s status or city and watch three structures update together. Query by city: the log compares index cost with a full scan. Then switch to the buggy update and change a few rows: stale entries turn red and queries start returning wrong answers.

A primary map plus two secondary indexes
sandbox

primary: id → row5 rows

idcitystatus
v1Osloidle
v2Limabusy
v3Oslobusy
v4Puneidle
v5Limarepair
click a row to select it

index: city → idsin sync

Oslov1v3Limav2v5Punev4

index: status → idsin sync

idlev1v4busyv2v3repairv5
v3:
writes per update
3
selected / just changedquery resultstale index entry
Change a vehicle's status, then query by city. Then switch to the buggy update and repeat.

When to reach for it

Section titled “When to reach for it”
The problem says… What to add
“find all X with field = v” and it’s called often Hash index: value → set of ids.
“…should not scan every record” That’s the interviewer asking for an index by name.
“all X with field between lo and hi” / “top k by field” Ordered index: sorted list or sorted set of (value, id).
“count how many have value v” A count map value → count (an index that stores only the size).
“records that have all of these tags” Inverted index tag → ids; intersect the sets, smallest first.
“names starting with prefix” Sorted keys + binary search, or a trie.

How it works

Section titled “How it works”
  1. Keep one source of truth: the primary map. Indexes only hold ids (or keys), never their own copy of the record.
  2. Route every write through one method per operation: insert, update, delete. Each touches the primary map and every index.
  3. On update, unindex the old value first, then index the new one. Read the old value before overwriting it.
  4. Delete empty buckets so “key present” means “at least one id”.
  5. Write a check() that rebuilds each index from the primary and compares. Call it in tests after every operation.
devices.py
from collections import defaultdict




class Devices:
    """Primary map id -> room, plus a secondary index room -> ids, always in sync."""


    def __init__(self) -> None:
        self.room_of: dict[str, str] = {}  # 1. primary: the source of truth
        self.in_room: defaultdict[str, set[str]] = defaultdict(set)  # 2. derived index


    def put(self, dev: str, room: str) -> None:
        old = self.room_of.get(dev)
        if old is not None:
            self._unindex(dev, old)  # 3. remove the OLD index entry first
        self.room_of[dev] = room
        self.in_room[room].add(dev)  # 4. then add the new one


    def remove(self, dev: str) -> bool:
        room = self.room_of.pop(dev, None)
        if room is None:
            return False
        self._unindex(dev, room)
        return True


    def find(self, room: str) -> list[str]:
        return sorted(self.in_room.get(room, ()))  # O(k log k), not O(n)


    def _unindex(self, dev: str, room: str) -> None:
        ids = self.in_room[room]
        ids.discard(dev)
        if not ids:
            del self.in_room[room]  # 5. drop empty buckets so keys mean "non-empty"


    def check(self) -> None:  # rebuild the index from the primary and compare
        rebuilt: defaultdict[str, set[str]] = defaultdict(set)
        for dev, room in self.room_of.items():
            rebuilt[room].add(dev)
        assert rebuilt == self.in_room, "index out of sync"




if __name__ == "__main__":
    d = Devices()
    d.put("lamp", "hall")
    d.put("fan", "hall")
    d.put("lamp", "office")  # a move: must leave "hall"
    assert d.find("hall") == ["fan"] and d.find("office") == ["lamp"]
    assert d.remove("fan") and not d.remove("fan")
    assert "hall" not in d.in_room
    d.check()
    print("ok")

For ranges, a hash index is useless: it can’t tell you which keys are “between”. Keep entries sorted and binary-search to the start of the range, then read forward.

range_index.py
import bisect


# An ordered index on battery level: sorted (level, id) pairs.
# A hash index answers "level == x"; only an ordered one answers "between lo and hi".
index: list[tuple[int, str]] = []




def add(dev: str, level: int) -> None:
    bisect.insort(index, (level, dev))  # 1. O(log n) search + O(n) shift in a list




def between(lo: int, hi: int) -> list[str]:
    start = bisect.bisect_left(index, (lo, ""))  # 2. seek: first entry with level >= lo
    out = []
    for level, dev in index[start:]:  # 3. read forward while still in range
        if level > hi:
            break
        out.append(dev)
    return out  # O(log n + k) for k results




if __name__ == "__main__":
    for dev, lvl in [("lamp", 80), ("lock", 15), ("cam", 40), ("fan", 22), ("tv", 40)]:
        add(dev, lvl)
    assert between(20, 40) == ["fan", "cam", "tv"]  # ordered by level, then id
    assert between(90, 99) == [] and between(0, 15) == ["lock"]
    print("ok")

The SQL side

Section titled “The SQL side”

A relational database does the same thing for you, with a B-tree index: a balanced tree whose leaves hold the indexed values in sorted order, each pointing at its row. Two things follow from “sorted”:

  • It answers equality, ranges (BETWEEN, <, >), prefix matches (LIKE 'abc%') and ORDER BY on the indexed columns, each with a seek of O(log n) plus the rows read.
  • A composite index on (a, b) is sorted by a, and by b only within equal a. So it can seek on a, or on a then b. It can’t seek on b alone: those rows are scattered across every a group. This is the leftmost-prefix rule.
Composite index column order: seek or scan?
interactive
BR1
#1
BR4
#16
BR5
#11
BR6
#6
DE1
#13
DE2
#8
DE3
#3
DE6
#18
IN2
#20
IN3
#15
IN4
#10
IN5
#5
JP1
#7
JP2
#2
JP5
#17
JP6
#12
US1
#19
US2
#14
US3
#9
US4
#4
index_order(country, day)
accessindex seek + range read
entries_read3 of 20
matches3
Equality on the leading column, then a range on the second: still one contiguous run. This is the ideal shape for a (country, day) index.
matches the queryread by the range but filtered outread by a full scannever touched
 
CREATE TABLE trips (
  id      INTEGER PRIMARY KEY,
  country TEXT    NOT NULL,
  day     DATE    NOT NULL,
  rider   INTEGER NOT NULL,
  fare    INTEGER NOT NULL           -- cents
);


-- Equality column first, range column second.
CREATE INDEX trips_country_day ON trips (country, day);


-- Seeks: country is the leading column, day narrows inside it.
SELECT id, fare FROM trips WHERE country = 'IN' AND day BETWEEN '2026-03-02' AND '2026-03-04';


-- Can't seek on this index: day alone isn't a leading prefix. Needs its own index on (day).
SELECT count(*) FROM trips WHERE day = '2026-03-03';


-- Covering index: every column the query reads is in the index, so the table is never touched.
CREATE INDEX trips_country_day_fare ON trips (country, day, fare);


-- Ask the database what it will do.
EXPLAIN QUERY PLAN                    -- SQLite; Postgres: EXPLAIN ANALYZE
SELECT sum(fare) FROM trips WHERE country = 'IN' AND day >= '2026-03-01';

Rules of thumb for column order: equality columns first, then the one range column, then columns you only read (to make it covering). Once a range condition is used, columns after it can’t narrow the seek any further.

What it costs

Section titled “What it costs”

With n records, k results, m indexes:

Find by id Find by field = v Field between lo, hi Insert / update / delete
Primary map only O(1) O(n) scan O(n) scan O(1)
+ hash index O(1) O(1) + k O(n) O(1) per index → O(m)
+ ordered index O(1) O(log n + k) O(log n + k) O(log n) per index (O(n) for a sorted array insert)
SQL B-tree O(log n) O(log n + k) O(log n + k) O(log n) per index, plus disk I/O

Each index speeds up reads and slows down every write, and uses memory. An index nobody queries is pure cost. In databases, too many indexes on a write-heavy table is a classic performance problem.

Variations you’ll meet

Section titled “Variations you’ll meet”
  • Unique index. At most one id per value. Enforces a constraint (“email must be unique”) as well as speeding up lookups. Check it before mutating anything.
  • Inverted index. word → documents containing it. The core of search engines; set-valued fields work the same way.
  • Composite in-memory index. Key the map by a tuple: (city, status) → ids. Only helps queries that give both.
  • Lazy / rebuilt index. Mark the index dirty on writes and rebuild on the next read. Good when writes come in bursts and reads are rare.
  • Partial index. Index only rows matching a condition (WHERE status = 'active'). Smaller and faster when queries only ever ask about that subset.
  • Order-by support. If results must be sorted by (priority desc, created asc), an ordered index on exactly that key returns them already sorted.

Pitfalls

Section titled “Pitfalls”
  • Overwrite before unindex. Writing the new value first loses the old one, so you can’t remove the stale index entry.
  • Partial failures. If an update throws halfway (say, a uniqueness check fails after the primary changed), the structures disagree. Validate everything, then mutate.
  • Empty buckets that make “list all cities” include cities with no vehicles.
  • Returning the internal set. The caller mutates it and corrupts your index. Return a sorted copy.
  • Indexing mutable records by reference. If a caller can edit a record object directly, your index never hears about it. Copy records on the way in and out.
  • SQL: functions on indexed columns. WHERE lower(email) = ? can’t use an index on email. Index the expression, or store the normalized value.

In the interview

Section titled “In the interview”
  • When a level adds a query, ask: “How often is this called compared to writes? How big can n get?” If queries are frequent, say “I’ll add an index from field to ids and update it in every write path.”
  • State the invariant: “For every record, its id appears in exactly the index buckets matching its current field values, and nowhere else.” Then name the check() you’ll use in tests.
  • Walk through update explicitly: read old value, unindex, write primary, index new.
  • For SQL questions, say the column order out loud and why: “Country first because it’s an equality filter, then day for the range.” Mention EXPLAIN.
  • Expect follow-ups: multi-condition queries, sorting the results, prefix search, and “what if writes are 100× more common than reads?” (fewer indexes, or lazy ones).

Check yourself

Section titled “Check yourself”
Check yourself
pick one
A record's city changes from Oslo to Lima. Which sequence keeps a city index correct?
Check yourself
pick one
A table has an index on (country, day). Which query can NOT seek into it?
Check yourself
pick one
Writes outnumber reads 1000 to 1, and the 'find by status' query runs once a day. What's the sensible design?

Practice on your own

Section titled “Practice on your own”

These are classic exercises, not gym questions:

  • A contact book with lookups by phone number (unique) and by last name (many), plus rename and delete.
  • A log store answering “all errors from service S between t1 and t2” with an ordered index per service.
  • A simple search engine: build an inverted index over 20 short documents and answer AND queries by intersecting smallest-first.
  • In SQLite, create a table with 100,000 rows, run a query with and without an index, and read EXPLAIN QUERY PLAN for both.

Go deeper

Section titled “Go deeper”
Section titled “Related”
Hash mapsThe building block of every in-memory index.
Sorted containersOrdered indexes for ranges and top-k.
Class design and invariantsIndex consistency is an invariant.
TriesPrefix queries over string keys.