1. The problem: why do queries get slow as Instagram grows?

Open any Instagram profile and the app shows the 12 most recent posts in a grid. The query behind it looks innocent:

SELECT id, created_at FROM posts
 WHERE user_id = 42
 ORDER BY created_at DESC
 LIMIT 12;

With 1,000 posts in the table this takes microseconds no matter how it's executed. Now assume the table holds 100 million posts of about 200 bytes each — 20 GB. Without an index the database has exactly one strategy: read every row, keep those with user_id = 42, sort them and return 12. Even at a generous 500 MB/s of sequential disk throughput that's ~40 seconds of I/O for a single profile view, and every concurrent profile view competes for the same disk. Instagram serves hundreds of thousands of such reads per second. Without indexes, the product simply cannot exist.

With the right index the same query reads about 4–5 small pages (~40 KB) and finishes in well under a millisecond. That gap — 40 s versus 0.1 ms, a factor of roughly 400,000 — is why indexing is one of the highest-leverage skills in system design.

2. The cost of a full table scan

Databases store rows in fixed-size pages (8 KB in PostgreSQL, 16 KB in MySQL InnoDB). Reading a page from disk is the unit of cost. A full table scan (PostgreSQL calls it a Seq Scan) reads every page of the table:

rows per page   = 8 KB / 200 B          ≈ 40
pages           = 100,000,000 / 40      = 2,500,000 pages (≈ 20 GB)
scan time (SSD) = 20 GB / 500 MB/s      ≈ 40 s
scan time (RAM) = 20 GB / ~5 GB/s       ≈ 4 s   (even fully cached it's far too slow)

The cost is O(n): it grows linearly with table size, so a query that was fine at launch gets 10× slower each time the table grows 10×. Full scans also evict useful pages from the buffer cache, hurting every other query.

Full scans are not always bad. They are the right choice when you need a large fraction of the table anyway (analytics, "count all posts per country"), because reading pages sequentially is much faster than jumping around randomly via an index. The optimizer weighs this trade-off using selectivity (Section 8).

3. B-trees and B+trees: the default index

3.1 Structure

A B-tree is a balanced search tree designed for disks: each node is one page and holds many sorted keys (hundreds), so the tree is very wide and very shallow. Almost every relational database actually uses the B+tree variant:

• Internal nodes contain only keys and child pointers — "keys below 2000 go left, 2000–5999 middle, 6000+ right". They act as signposts.
• Leaf nodes contain all the keys, in sorted order, each with its payload: either a pointer to the row (PostgreSQL's tuple ID) or the row itself (InnoDB's clustered index).
• Leaves are linked to their neighbours, so once you've found the start of a range you just walk sideways — that's how ORDER BY … LIMIT and BETWEEN become cheap.
• All leaves are at the same depth (the tree is balanced), so every lookup costs the same number of page reads.

The number of children per node is the fan-out. With 8 KB pages and ~16-byte entries (8-byte key + pointer), an internal node holds roughly 400–500 entries.

3.2 Lookup is O(log n) — and log base 500 is tiny

1. Read the root page (almost always cached in RAM). Binary-search its keys to pick the child.
2. Read that internal page, binary-search again, pick the next child.
3. Reach the leaf; find the key; follow the pointer to the row (one more page read, unless the index covers the query).

The height of the tree is about log_fan-out(n). With fan-out 500:

So looking up one row among 100 million costs 3 index page reads + 1 table page read. Because the root and internal levels are small (level 2 of a 100M-row index is only ~200 pages ≈ 1.6 MB) they stay in memory, so in practice it's often one or two actual disk reads. Compare 2,500,000 page reads for the full scan.

3.3 Inserts, page splits and fill factor

To insert a key, the database finds the correct leaf and adds the key in sorted position. If the leaf is full, it splits into two half-full pages and pushes a separator key up into the parent (which may split in turn; if the root splits, the tree grows one level taller — that's how B-trees stay balanced). Consequences worth knowing:

• Random keys cause random I/O and fragmentation. Inserting random UUIDs touches a random leaf every time and leaves pages half full. Inserting monotonically increasing keys (auto-increment, time-sortable IDs like Instagram's 64-bit IDs) always appends to the rightmost leaf — cache-friendly and compact. (The flip side: in a distributed system, sequential keys can create a write hotspot on one node; see Sharding.)
• Updates are in place. Changing a 100-byte value rewrites the whole 8 KB page (plus a WAL record). That is B-tree write amplification.
• Fill factor leaves free space in pages so future inserts/updates don't immediately split them.

4. Hash indexes

A hash index applies a hash function to the key and stores the entry in the corresponding bucket — a hash table on disk (or in memory). Lookups by exact key are O(1) on average.

Because B+trees are nearly as fast for equality and far more flexible, relational databases default to them. Hash indexing shines in key-value stores: Redis is essentially an in-memory hash table, and Bitcask (Riak's engine) keeps an in-memory hash map from key to file offset on disk. Hashing is also how distributed systems decide which node owns a key — see Consistent Hashing.

5. LSM-trees: the write-optimised storage engine

B-trees update pages in place, which means random writes. For workloads with enormous write rates — Instagram's likes, feed entries, activity and messages — a different design wins: the Log-Structured Merge-tree (LSM-tree), used by Cassandra, ScyllaDB, HBase, Bigtable, RocksDB, LevelDB and (under the hood) many others. The core idea: never modify data on disk; only append sorted files and merge them later in the background.

5.1 The write path

1. WAL (commit log). The write is appended to a sequential log on disk for durability. Appends are the fastest possible disk operation.
2. Memtable. The write is inserted into an in-memory sorted structure (typically a skip list or balanced tree). The client gets "OK" now — no data file has been touched.
3. Flush. When the memtable reaches a threshold (e.g. 64–256 MB) it's frozen and written to disk in one sequential pass as an SSTable (Sorted String Table): an immutable file of key-sorted entries plus a small index and a Bloom filter. The WAL segment covering it can then be discarded.
4. Compaction. Background threads merge SSTables (a merge-sort of already-sorted files), keeping only the newest version of each key and dropping deleted data, so the number of files a read must check stays bounded.

5.2 The read path

A key might be in the memtable or in any SSTable, and newer data shadows older data. So a read checks: memtable → then SSTables from newest to oldest, stopping at the first hit. To avoid opening files that can't contain the key, each SSTable has a Bloom filter in memory, plus a sparse index (every N-th key with its file offset) to jump close to the key within a file.

5.3 Deletes and updates

Because files are immutable, an update is just a newer write of the same key, and a delete is a special write called a tombstone ("key k deleted at time t"). Reads see the newest entry, so the tombstone hides older values. Compaction eventually discards both the tombstone and the shadowed data (in Cassandra, only after gc_grace_seconds, so replicas that missed the delete can't "resurrect" the data). Lots of tombstones in a range make reads slow — a well-known Cassandra pitfall.

5.4 Bloom filters

A Bloom filter is a compact probabilistic set: a bit array of m bits plus k hash functions. To add a key, set the k bits it hashes to. To test a key, check those k bits: if any is 0, the key is definitely not present; if all are 1, it's probably present. There are no false negatives, only occasional false positives.

false-positive rate  p ≈ (1 − e^(−k·n/m))^k        n = keys, m = bits, k = hash functions
optimal k            k = (m/n) · ln 2

Example: 10 bits per key (m/n = 10), k = 7  →  p ≈ 0.8 %
         an SSTable with 10 M keys needs 100 M bits ≈ 12 MB of RAM for its filter

Effect: a read for a key that exists in only one of 20 SSTables opens ~1 file instead of 20. Cassandra lets you tune bloom_filter_fp_chance per table (more memory, fewer wasted disk reads).

5.5 Compaction strategies

5.6 B-tree vs LSM-tree

Three "amplification" metrics frame the comparison:

• Write amplification = bytes written to disk ÷ bytes written by the application. A B-tree rewrites an 8 KB page (plus WAL) to change a 100-byte row; an LSM writes the row to the WAL, then to an SSTable, then again at every compaction (often 10–30× with leveled compaction).
• Read amplification = disk reads per query. A B-tree is ~1 path (3–4 pages, mostly cached). An LSM may check the memtable plus several SSTables (mitigated by Bloom filters).
• Space amplification = disk used ÷ live data size. B-trees waste free space inside half-full pages; LSMs hold obsolete versions and tombstones until compaction.

6. Clustered vs non-clustered indexes

Where does the actual row live?

• Clustered index — the table is the index: rows are stored inside the B+tree leaves, physically ordered by the clustering key. A table can have only one. MySQL InnoDB always clusters by the primary key; SQL Server lets you choose; Cassandra's clustering columns order rows within each partition.
• Non-clustered (secondary) index — a separate structure whose leaves hold the indexed key plus a pointer to the row. In InnoDB that pointer is the primary key (so a secondary lookup is two tree traversals); in PostgreSQL every index is non-clustered and points to a physical location (ctid, page + slot) in an unordered heap file.

 MySQL InnoDB (clustered by PRIMARY KEY id)          PostgreSQL (heap + indexes)

 secondary idx (username)     PK B+tree (id)         idx (username)        heap file (unordered)
 +----------------------+     +-----------------+    +-----------------+   +---------------------+
 | "alice"  → id 42     | --> | id 42 | FULL ROW|    | "alice" → (7,3) |-->| page 7, slot 3: row |
 | "bob"    → id 17     |     | id 43 | FULL ROW|    | "bob"   → (2,9) |   | page 2, slot 9: row |
 +----------------------+     +-----------------+    +-----------------+   +---------------------+
 lookup by username = 2 tree walks                    lookup = 1 tree walk + 1 heap page read
 lookup by id       = 1 tree walk (row is right there) range by PK may hit many scattered heap pages

Why it matters:

• Range scans on the clustering key are very fast — consecutive keys sit on the same pages. If the posts table is clustered on (user_id, id), a user's posts are physically adjacent: the profile grid reads one or two pages.
• Choose a narrow, stable, increasing clustering key. In InnoDB every secondary index stores the PK, so a fat PK (e.g. a 36-character UUID string) bloats every index; random PKs cause page splits.
• PostgreSQL can physically reorder a table once with CLUSTER, but doesn't maintain the order on later writes; covering indexes (below) are the usual way to get the same benefit.

7. Kinds of indexes you'll design

7.1 Primary index

The index on the primary key — unique and non-null, created automatically. Every table should have one; in InnoDB it's the clustered index. Prefer compact integer keys; Instagram's 64-bit time-sortable IDs are a good example: 8 bytes, unique across shards, and naturally ordered by creation time.

7.2 Secondary index

Any additional index on non-PK columns, to support other access paths — e.g. UNIQUE INDEX ON users (email) for login by email. Secondary indexes may be unique (also enforce a constraint) or non-unique. In a sharded system, a secondary index on a column that isn't the shard key is a hard problem (local vs global indexes — see Sharding).

7.3 Composite (multi-column) index and the leftmost-prefix rule

A composite index on (a, b, c) sorts entries by a, then by b within equal a, then by c — like a phone book sorted by (last name, first name). You can efficiently find "all Smiths" or "Smith, John", but not "everyone named John" — they're scattered across the whole book. That's the leftmost-prefix rule: an index can be used for a contiguous prefix of its columns, starting from the left.

For CREATE INDEX posts_user_recent ON posts (user_id, created_at DESC):

Column order rules of thumb: put columns used with equality first, then the column used for a range or ORDER BY last; a range on column b stops the index from helping with column c after it. Among equality columns, the order matters less for a single query but should be chosen so the prefix serves other queries too.

7.4 Covering index (index-only scan)

If an index contains every column a query needs, the database answers from the index alone and never touches the table — an index-only scan. That saves one random page read per row.

-- The grid needs id, created_at and the thumbnail key. Add the extra column as payload:
CREATE INDEX posts_grid_covering
    ON posts (user_id, created_at DESC)
    INCLUDE (id, thumb_key);          -- PostgreSQL 11+ / SQL Server syntax; in MySQL append the columns

Covering indexes are bigger, so add them only for hot queries. In PostgreSQL an index-only scan also needs the table's visibility map to be up to date (maintained by VACUUM).

7.5 Partial (filtered) index

A partial index indexes only rows matching a predicate. It's smaller, faster to update and more likely to stay in memory.

-- 3% of posts are soft-deleted and never shown; don't index them at all
CREATE INDEX posts_live_by_user ON posts (user_id, created_at DESC)
 WHERE deleted_at IS NULL;

-- Only a small fraction of comments are flagged for moderation review
CREATE INDEX comments_pending_review ON comments (created_at)
 WHERE status = 'pending_review';

The query must include a compatible predicate (AND deleted_at IS NULL) for the planner to use it. Instagram's engineering blog has publicly recommended partial indexes as one of its PostgreSQL scaling tips.

7.6 Expression (functional) index

Index the result of an expression, e.g. case-insensitive usernames: CREATE UNIQUE INDEX users_username_ci ON users (lower(username)); then query with WHERE lower(username) = lower($1). Without it, wrapping a column in a function prevents the normal index from being used.

8. Cardinality and selectivity: is the index even worth it?

• Cardinality of a column = number of distinct values. users.id: 2 billion (high). users.is_private: 2 (low). posts.country: ~200.
• Selectivity of a predicate = fraction of rows it matches (lower fraction = more selective = better for an index). id = 42 matches 1 row in 2 billion; is_private = false might match 70% of rows.

Using an index costs roughly one random page read per matching row (unless the matching rows are physically adjacent or the index covers the query). A sequential scan costs one cheap sequential read per page. So if a predicate matches a big fraction of rows, the planner correctly ignores the index and scans. The crossover is often somewhere around a few percent to ~10–20% of rows, depending on row width, caching and storage type.

Table: 100 M posts, 2.5 M pages.
Predicate A: user_id = 42        → ~300 rows (0.0003 %)  → index: ~300 page reads  ✅
Predicate B: media_type = 'photo'→ ~70 M rows (70 %)     → index: ~70 M random reads ❌  seq scan: 2.5 M pages ✅
Predicate C: is_private = true AND created_at > now() - interval '1 hour'
             → combine: index on created_at (selective) + filter on is_private

Planners estimate selectivity from statistics (histograms, most-common values, distinct counts) gathered by ANALYZE. Stale statistics → bad estimates → bad plans; a classic production incident is a plan flip after a large data load. Low-cardinality columns can still be useful inside a composite index or as a partial-index predicate (e.g. WHERE status = 'pending' when pending rows are rare).

9. The write cost of indexes

Indexes are not free. Every INSERT must add an entry to every index on the table; every DELETE must remove them; an UPDATE must modify every index whose columns changed (and in PostgreSQL, a non-HOT update touches all indexes). Each of those is a B-tree descent and possibly a page split, plus WAL records and replication traffic.

Assume the likes table receives 58,000 inserts/s on average (see the databases lesson).
  PK (post_id, user_id)               → 1 index write
  + index (user_id, created_at)       → 1 more
  + index (created_at) "for analytics"→ 1 more
  = 174,000 B-tree insertions/s, each a potential random page write, plus 3× the WAL volume.

Drop the analytics index (run analytics on the data warehouse instead) → 116,000/s: one third less write I/O.

Costs of each additional index:

• Write latency and throughput — more random I/O and WAL per write; more lock/latch contention on hot index pages (e.g. the rightmost leaf of a timestamp index).
• Storage and memory — indexes compete with table data for the buffer cache. It's common for a table's indexes to be larger than the table itself.
• Replication lag — more WAL to ship and replay on replicas.
• Maintenance — bloat, rebuilds, vacuum time. Creating an index on a live table locks writes unless you use CREATE INDEX CONCURRENTLY (PostgreSQL) or an online DDL tool.

So: index what your real queries need, monitor index usage (pg_stat_user_indexes.idx_scan), and drop indexes that nobody uses. For bulk loads, it's often faster to drop indexes, load, and rebuild.

10. Reading EXPLAIN plans

EXPLAIN shows the plan the optimizer chose; EXPLAIN ANALYZE also runs the query and reports real row counts and timings. This is how you prove an index is used. (Example outputs below are PostgreSQL-style, simplified, with parallelism disabled for clarity.)

10.1 Before: no suitable index

EXPLAIN ANALYZE
SELECT id, created_at FROM posts WHERE user_id = 42 ORDER BY created_at DESC LIMIT 12;

Limit  (cost=2350412.10..2350412.13 rows=12 width=16) (actual time=8123.4..8123.4 rows=12 loops=1)
  ->  Sort  (cost=2350412.10..2350412.85 rows=300 width=16) (actual time=8123.4..8123.4 rows=12 loops=1)
        Sort Key: created_at DESC
        Sort Method: top-N heapsort  Memory: 25kB
        ->  Seq Scan on posts  (cost=0.00..2350405.00 rows=300 width=16)
                                (actual time=0.03..8120.9 rows=287 loops=1)
              Filter: (user_id = 42)
              Rows Removed by Filter: 99999713
Planning Time: 0.1 ms
Execution Time: 8123.5 ms

How to read it (bottom-up, innermost first):

• Seq Scan on posts — a full table scan. Rows Removed by Filter: 99,999,713 is the smoking gun: we read 100M rows to keep 287.
• cost=start..total — the planner's estimate in arbitrary units (roughly page reads); rows — estimated row count (300) vs actual rows (287): the statistics are good.
• Sort — an extra step because data wasn't already ordered.
• Execution Time: 8.1 s.

10.2 After: composite index

CREATE INDEX CONCURRENTLY posts_user_recent ON posts (user_id, created_at DESC);

Limit  (cost=0.57..48.90 rows=12 width=16) (actual time=0.031..0.058 rows=12 loops=1)
  ->  Index Scan using posts_user_recent on posts  (cost=0.57..1208.90 rows=300 width=16)
                                                  (actual time=0.030..0.055 rows=12 loops=1)
        Index Cond: (user_id = 42)
Planning Time: 0.2 ms
Execution Time: 0.08 ms

• Index Scan … Index Cond — the B-tree is descended directly to user 42's entries.
• No Sort node — the index already returns rows in created_at DESC order, and the Limit stops after 12 rows (actual rows=12, not 287).
• 0.08 ms vs 8,123 ms — ~100,000× faster.

10.3 Even better: covering index

Index Only Scan using posts_grid_covering on posts  (actual time=0.020..0.031 rows=12 loops=1)
  Index Cond: (user_id = 42)
  Heap Fetches: 0

Heap Fetches: 0 means the table was never touched. Other plan nodes to recognise: Bitmap Index Scan / Bitmap Heap Scan (collect many matching row locations, then read table pages in physical order — used for medium selectivity or to combine indexes with AND/OR), Nested Loop / Hash Join / Merge Join (join algorithms), and in MySQL's EXPLAIN the type column (ALL = full scan, ref/range = index) and Extra: Using index (covering) or Using filesort (extra sort).

11. Geospatial indexes: "posts near me"

Instagram lets users tag a location on a post and browse a place's page or a map of nearby places. The query "places within 2 km of (lat, lng)" can't use an ordinary B-tree well: an index on lat finds a horizontal band spanning the globe, and an index on (lat, lng) still only narrows on latitude. Two dimensions need a spatial index. Three common approaches:

11.1 Geohash: turn 2-D into a sortable string

A geohash recursively halves the world, alternating longitude and latitude: each bit says "left/right half" or "bottom/top half". The interleaved bits are encoded 5 at a time in base-32 characters. Key property: points that share a prefix are in the same cell, and longer prefixes mean smaller cells. So a spatial lookup becomes a prefix search on an ordinary B-tree (or a key lookup in Redis/Cassandra).

 Bits are interleaved: lng, lat, lng, lat, …     then grouped by 5 → base-32 char
   lng bit 1: is lng ≥ 0?        → 1
   lat bit 1: is lat ≥ 0?        → 1
   lng bit 2: upper half of [0,180)?  …            "t", "td", "tdr", "tdr1", … (each char = 32× smaller cell)

 Neighbour search: the target point P may sit near a cell edge, so query P's cell
 AND its 8 neighbours (prefix length chosen so a cell ≈ the search radius):

        +--------+--------+--------+
        | NW     | N      | NE     |
        +--------+--------+--------+
        | W      | P's    | E      |      9 prefix lookups, then filter by exact
        |        | cell • |        |      distance (haversine) on the candidates
        +--------+--------+--------+
        | SW     | S      | SE     |
        +--------+--------+--------+

Caveats: two points a metre apart on either side of a cell boundary can have completely different prefixes (hence the 9-cell query), and cells distort towards the poles. Redis GEOADD/GEOSEARCH is built on geohash-encoded sorted-set scores; Elasticsearch supports geo_point fields with distance queries.

11.2 Quadtree: adaptive cells

A quadtree starts with one square covering the map and splits any cell holding more than K points into four quadrants (NW, NE, SW, SE), recursively. Dense cities get tiny cells, oceans stay as one big cell — so every leaf holds a similar number of places. To search, descend from the root into the quadrants that intersect the search circle and test the points in those leaves.

11.3 R-trees, S2 and H3

• R-tree — groups nearby objects into nested bounding rectangles; handles shapes (polygons, lines), not just points. PostGIS uses R-tree-over-GiST indexes: CREATE INDEX ON places USING gist (geom); then WHERE ST_DWithin(geom, ST_MakePoint(lng, lat)::geography, 2000).
• S2 (Google) maps the sphere onto a cube and fills it with a Hilbert curve, giving 64-bit cell IDs that preserve locality better than geohash. H3 (Uber) uses hexagonal cells, whose neighbours are all equidistant — handy for aggregations like "demand per area".

12. Inverted indexes (for search)

B-trees find rows by a column's whole value or prefix. They can't answer "captions containing the word sunset" or "usernames similar to selna". For that, search engines build an inverted index: a map from each term to the list of documents containing it (a "posting list"), e.g. sunset → [post 17, post 942, post 10,331 …]. Text is first tokenised, lower-cased and stemmed; queries intersect posting lists and rank the results. Instagram's user, hashtag and place search runs on this kind of index in Elasticsearch-style clusters, fed asynchronously from Kafka. The full story — tokenisation, posting lists, TF-IDF/BM25 ranking, typeahead — is in Search & Inverted Indexes.

13. How Instagram uses indexes

Map every hot screen to a query, and every query to an index (or, in Cassandra, a primary-key design):

Rough numbers (assumptions)

Assume one PostgreSQL shard holds 50 M posts.
Index (user_id BIGINT, created_at TIMESTAMPTZ) ≈ 16 B key + ~8 B pointer + overhead ≈ 32 B/entry
  → 50 M × 32 B ≈ 1.6 GB  — fits in RAM next to the hot table pages
Height: 8 KB pages / 32 B ≈ 250 entries per page → 250³ ≈ 15.6 M, 250⁴ ≈ 3.9 B → 4 levels
Profile grid lookup: ~3 cached internal pages + 1 leaf page (+ 12 heap pages, or 0 if covering)
At 20,000 profile views/s on this shard: ~20,000–260,000 page touches/s, nearly all from RAM.

14. Trade-offs & common pitfalls

Common mistakes

• Indexing every column "just in case". Write throughput collapses and most indexes are never used. Index from real query patterns and monitor usage.
• Wrong composite column order — (created_at, user_id) for a "by user, newest first" query can't serve it efficiently. Equality columns first, range/sort column last.
• Redundant indexes — (user_id) is redundant when (user_id, created_at) exists (leftmost prefix).
• Indexing low-selectivity columns alone (is_private, media_type). Use them in a composite or as a partial-index predicate.
• Functions or casts on indexed columns in WHERE, and leading-wildcard LIKE '%x'.
• OFFSET pagination — OFFSET 100000 LIMIT 12 still walks 100,012 index entries. Use keyset (cursor) pagination: WHERE user_id = 42 AND id < :last_seen_id ORDER BY id DESC LIMIT 12.
• Random UUID primary keys in a clustered B-tree → page splits, fragmentation, cache misses. Prefer time-ordered IDs.
• Building an index on a hot table without CONCURRENTLY / online DDL → writes blocked for minutes.
• Never running EXPLAIN ANALYZE — assuming the index is used rather than proving it.
• Using Cassandra secondary indexes or ALLOW FILTERING for high-cardinality lookups instead of a dedicated query table.

15. Real-world technologies

16. Interview corner

17. Check your understanding

Related lessons

• Databases: SQL vs NoSQL — which engines use B-trees vs LSM-trees and why
• Search & Inverted Indexes — full-text indexing in depth
• Sharding — local vs global secondary indexes across shards
• Unique ID Generation — time-sortable IDs that keep B-trees compact
• Replication — why extra index writes increase replica lag
• Likes, Comments & Counters — the access patterns these indexes serve
• Caching — Redis sorted sets as in-memory indexes