Database Indexes

An auxiliary data structure that maps column values to row locations. The most common type is a B-tree (or B+-tree): sorted, balanced, range-query-friendly. LSM-trees are the alternative used by write-heavy stores (Cassandra, RocksDB).

Without an index, finding a row by some column means scanning every row, an O(n) operation. On a table with billions of rows, that's intolerable. An index turns that into a fast lookup.

B-tree: sorted by indexed column; lookups walk the tree (log n). Updates are in-place but require rebalancing. LSM-tree: writes go to a memory buffer, periodically flushed to immutable sorted files; reads check multiple files and a Bloom filter to skip ones that don't have the key. Writes are much faster (append-only) but reads are amortized.

• Reads on indexed columns are dramatically faster
• Range scans (ORDER BY, BETWEEN) work efficiently on B-trees
• LSM-trees give very high write throughput for time-series workloads

• Every write must update every index, causing write amplification
• Indexes take storage (often as much as the table itself for heavily-indexed tables)
• Indexes only help if the query planner uses them, so composite index order matters

• URL Shortener →

  Postgres index on short_key turns redirect lookups into O(log n)

• Search Engine →

  Inverted index: the entire data structure that makes 'find documents containing X' fast

• Yelp →

  Geo index (geohash), a specialized spatial index

• Don't index every column. Each index slows writes and takes space. Add indexes for actual query patterns.
• Composite index column order matters. INDEX (a, b) supports queries on a or (a, b), not on b alone.
• B-trees for read-heavy, balanced workloads. LSM-trees for write-heavy time-series. The choice is at the storage engine level.