Case Study 3.2: How an inverted index supports Spotify search

Concept. This example architecture supports text search across 100 million tracks with an inverted index, which maps each search term to the song_ids that contain 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

An inverted index

Two sorted term-index pages hold multiple words. Crazy and Heart point to song-ID postings lists. Intersect the lists in RAM to obtain IDs 12 and 108, then fetch those song records from data pages. B+Tree routing nodes are omitted.

Figure 1. Each term-index page holds several sorted terms; each term points to a postings list of song IDs. For Crazy AND Heart, intersect the two lists in RAM to get {12, 108}, then fetch those songs from the data pages. The postings store IDs; the data pages store rows. The B+Tree routing nodes above the term pages are omitted.

Why the term dictionary uses a B+Tree

A B+Tree term dictionary supports exact and prefix lookups. When a user types "Craz," the engine can scan neighboring terms such as "Crazy." A hash index scatters those terms across buckets, so it cannot support the same prefix scan.

Beyond keyword matching

The search engine can expand the query before retrieval and rank the resulting candidates:

  • Query expansion. A search for "happy" also checks related terms such as "joyful" and "cheerful." This broadens recall without forcing the user to guess synonyms.

  • Ranking. This example scores each match using three signals: where the term appears (title beats tag), overall popularity (a global hit beats a deep cut), and personal history (an artist you often play moves up).

Takeaway: Look up terms, intersect their song-ID lists, then fetch the matching song rows.