Case Study 3.2: How does Spotify support text search?

Concept. Spotify supports text search across 100 million tracks using an inverted index, a per-word lookup table that maps each search term to the list of song_ids containing it.

Intuition. Without an index, a search for "Yesterday" reads every row in a 100-million-song Songs table. An inverted index looks up "Yesterday" once, returns a short list of matching song_ids, and limits reads to the rows for those IDs.

Case Study 3.2 Reading Time: 6 mins

The Solution: An Inverted Index

An inverted index looks like the index at the back of a textbook. Each term (word) is a key, and its value is a list of locations (track IDs) where that word appears. The figure walks the live "Crazy Heart" example.

Inverted index. A green B+Tree term dictionary on the left stores every unique word in the Songs table; Crazy and Heart are highlighted in purple. Each highlighted term points at its green postings list on the right, a packed array of song IDs. The red Bitwise-AND-intersection box runs in RAM, walking both lists in lockstep and keeping IDs that appear in both. Result: song IDs 12 and 108. About 10 IOs total versus 100 million for a full-table scan.

Figure 1. An inverted index over the Songs table uses a term dictionary on disk, implemented as a B+Tree over every unique word, and postings lists on disk, stored as sorted packed arrays of song IDs per word. For "Crazy Heart" the engine looks up each word, intersects the two sorted postings lists in RAM to {12, 108}, and reads those 2 data pages, about 10 IOs. A full-table scan reads all 100 million rows, so the index uses roughly 10,000,000× fewer reads.

Why a B+Tree for the Term Dictionary

One detail worth pulling out: the term dictionary is a B+Tree, which supports both exact and prefix lookups. Users often type prefixes ("Craz" before they finish typing "Crazy"); a hash index would scatter neighbouring terms to random buckets and could not auto-complete.

Beyond Keyword Matching

Inverted indexes get you the candidate songs fast. Real search engines then apply two more layers on top:

  • Query expansion. A search for "happy" also checks related terms like "joyful" and "cheerful", broadening recall without forcing the user to guess synonyms.

  • Ranking. Not all matches are equally relevant. Spotify scores each match on three signals: where the term appeared (title beats tag), overall popularity (a global hit beats a deep cut), and personal history (an artist you listen to often moves up).

Takeaway: An inverted index turns an O(N) row scan into an O(log N) term-dictionary lookup (a B+Tree, for exact and prefix), intersecting postings in RAM so the expensive random IO only fires for the rows you actually need.