Last Minute Notes
  • Github
  • Docs
  • Learn
    @sayanstwt
Lessons
0/37 done
  • SQL vs NoSQL
  • Indexes & Storage Engines
  • Replication
  • Sharding
  • Consistent Hashing
  • Object Storage & Uploads
  • Search & Inverted Indexes
Learn/System Design/Data & Storage

Search & Inverted Indexes

7 min Intermediate 7 steps

How a search engine finds documents by word in milliseconds.

Docs read
1 / 4
Words compared
4
Matches
0
find docs with the word "shoe"w1w2w3w4w5D1D2D3D4RunningshoesformenMen'srunningjacketTrailshoesShoecareforrunningshoesscan
current computed depends on
In this lessonStep 1 of 7
  1. The problem
  2. Analysis
  3. Inverted index
  4. Query
  5. Ranking
  6. Shards
  7. Recap
Step 1 / 7problem

Scanning text does not work

Find documents about "shoe". A scan compares every word of every document, so the cost grows with all the text you store.

Worse, raw words do not match: Shoes and Shoe are not shoe.

Key idea

Full text search needs an inverted index: for each term, the list of documents containing it.

←→ step·R replay·Space pause

You'll learn

  • Why scanning raw text is slow and misses matches
  • Normalize text with tokenizing, lowercasing, stop words and stemming
  • Build and query an inverted index
  • Rank results with TF-IDF and merge them across shards
Read the full notesHLD Building Blocks, 13