Skip to content
learn
  1. Learn
  2. High Level System Design
  3. Search, Geo and Specialized Data Structures

HLD-M15

Search, Geo and Specialized Data Structures

The specialized indexes behind search boxes, maps, analytics and AI features: inverted indexes, tries, geospatial cells, probabilistic sketches, time series and vectors.

6 lessonsabout 70 min

General-purpose databases answer "give me the row with this key" very well. Many product features ask different questions: which documents mention these words, ranked by relevance? What are the top completions for "sys"? Which drivers are within 2 km? Have we seen this URL before? How many unique visitors today? Which items are most similar to this one? Each needs a data structure designed for that question.

This module covers the important ones from a system designer's point of view: inverted indexes and BM25 ranking for full-text search, tries for typeahead, geohashes, quadtrees and hexagonal cells for location queries, Bloom filters, Count-Min Sketch and HyperLogLog for answering questions approximately in tiny memory, time-series storage with compression and downsampling, and where vector search fits when a system needs semantic similarity.

Lessons

  1. HLD-15.01 Inverted indexes and full-text search Full-text search engines build an inverted index: for every term, a list of documents that contain it. Intermediate 14 min
  2. HLD-15.02 Typeahead and autocomplete Autocomplete must answer within tens of milliseconds as the user types. Intermediate 10 min
  3. HLD-15.03 Geospatial indexing Finding things near a location is hard with plain latitude and longitude indexes. Intermediate 14 min
  4. HLD-15.04 Probabilistic data structures Probabilistic data structures answer questions approximately using tiny memory. Advanced 14 min
  5. HLD-15.05 Time-series data Time-series data is mostly appended, queried by time range and aggregated. Intermediate 10 min
  6. HLD-15.06 Vector search in system design Embeddings turn text, images or users into vectors where similar items are close together. Intermediate 10 min

Start with lesson 1