System design2 min

Database Indexing

Imagine trying to find a specific word in a 1,000-page book that has no index. You would have to read every single page from beginning to end. In databases, this is called a Full Table Scan, and it is brutally slow.

A database index works exactly like a book's index. It is a separate data structure (usually a B-Tree or Hash Table) that stores a small piece of data (the indexed column) along with a pointer to the full row of data on the disk.

Types of Indexes

1. B-Tree Indexes

This is the default index type in almost all relational databases (PostgreSQL, MySQL).

  • A B-Tree (Balanced Tree) keeps data sorted and allows searches, sequential access, insertions, and deletions in logarithmic time O(log N).
  • Because it is sorted, B-Trees are excellent for range queries (e.g., SELECT * FROM users WHERE age BETWEEN 20 AND 30).

2. Hash Indexes

  • These map a hashed value directly to a row location.
  • Search time is O(1), making it incredibly fast.
  • However, because hashing randomizes the order, Hash Indexes cannot be used for range queries. They only work for exact matches (e.g., SELECT * FROM users WHERE id = 'user123').

The Cost of Indexing

If indexes make reads so much faster, why don't we just index every single column in the database?

  1. Storage Overhead: An index is a literal copy of a column's data structured into a tree. If you index every column, your database size will explode.
  2. Write Performance Hit: Every time you INSERT, UPDATE, or DELETE a row, the database must not only update the actual table but also traverse and update every single index attached to that table. Heavy indexing makes write-heavy applications painfully slow.

Best Practices

  • Index columns that are frequently used in WHERE, ORDER BY, or JOIN clauses.
  • Avoid indexing columns with low cardinality (e.g., a "gender" column with only 2 or 3 distinct values). A full table scan might actually be faster than traversing the B-Tree for such columns.
  • Use Composite Indexes when you frequently query by multiple columns together (e.g., WHERE last_name = 'Smith' AND first_name = 'John'). The order of columns in a composite index matters!