Database Indexing (Deep Dive)

Interview Definition:

"An index is a separate list created by the database to quickly find data. Instead of checking every single row in a table to find a specific record (which is slow), the database checks the index first. The index tells the database exactly where that record is saved on the hard drive, allowing it to jump straight to the data and return results instantly."

1. The B-Tree (B+ Tree) Index

The default index type in almost all relational databases (PostgreSQL, MySQL InnoDB) is the B+ Tree.

Why B+ Tree over Binary Search Tree?

A database is stored on a hard disk. Disks read data in blocks (pages), typically 4KB or 8KB in size. A Binary Tree has only 2 children per node, meaning it is very deep. Traversing a deep tree requires many random disk reads, which are slow. A B+ Tree is a "fat and shallow" tree. Each node can have hundreds of children, meaning even a table with a billion rows can be traversed in just 3 or 4 disk jumps.

ASCII Visualization of a B+ Tree:

[ Internal nodes only contain routing keys ]
                             [ 40  |  80 ]                        <-- Root Page (Disk block 1)
                           /       |       \
               ----------/         |         \----------
             /                     |                     \
    [ 15 | 25 | 35 ]       [ 50 | 60 | 70 ]       [ 85 | 95 | 100 ]   <-- Branch Pages
      /  |    |  \           /   |    |  \           /    |    |  \
     /   |    |   \         /    |    |   \         /     |    |   \
[10] -> [20] -> [30] ---> [45] -> [55] -> [65] ---> [81] -> [90] -> [99]  <-- Leaf Pages (Actual Data Pointers)
==================== Linked List for Range Queries ====================

Characteristics of B+ Tree:

Sorted: Data is kept in sorted order.
Logarithmic Lookup: $O(\log_b N)$ where $b$ is the branching factor (often > 100).
Range Queries: Because leaf nodes are linked like a linked list, queries like WHERE age BETWEEN 20 AND 30 are extremely fast. It finds 20, then just traverses the linked list rightwards until 30.

2. Hash Index

A Hash Index uses a hash function to compute a hash code for each key.

ASCII Visualization:

  Key (e.g. Email)         Hash Function       Bucket Array (Pointers to rows)
  ----------------         -------------       -------------------------------
  alice@foo.com    ----->  hash() = 02  ---->  [00] null
  bob@bar.com      ----->  hash() = 05  ---->  [01] null
  charlie@baz.com  ----->  hash() = 02  ---->  [02] -> [Row: Alice] -> [Row: Charlie] (Collision)
                                               [03] null
                                               [04] null
                                               [05] -> [Row: Bob]

Characteristics of Hash Index:

Speed: $O(1)$ lookup time. Faster than B-Tree for exact matches.
Limitation: Cannot do range queries. WHERE age > 20 will NOT use a hash index because hashing destroys the ordering.
Use Case: Key-Value stores (Redis), or specific memory-optimized exact-match lookups.

3. Composite Index (Multi-Column Index)

An index created on two or more columns, e.g., CREATE INDEX idx_name_age ON users (last_name, first_name, age);.

The Leftmost Prefix Rule

A composite index can only be used if the query filters on the columns from left to right without skipping.

Imagine the index is a phone book sorted by Last Name, then First Name.

Works: WHERE last_name = 'Smith' (You can find the Smith section easily).
Works: WHERE last_name = 'Smith' AND first_name = 'John' (Find Smith section, then look for John).
FAILS: WHERE first_name = 'John' (The book is sorted by last name first. Knowing the first name doesn't help you skip pages. Full scan required.)
FAILS: WHERE last_name = 'Smith' AND age = 30 (Will use the index to find Smiths, but then has to scan all Smiths to check their age, because first_name was skipped).

4. Advanced Indexing Concepts

Covering Index (Index-Only Scan)

If your query is SELECT age FROM users WHERE last_name = 'Smith'; and you have an index on (last_name, age). The database finds 'Smith' in the index. Because age is also stored right there in the index, the database does not need to read the actual table data. This is called a "Covering Index" and is extremely fast.

When Indexing Hurts (The Write Penalty)

Every time you INSERT, UPDATE, or DELETE a row, the database must also update all B-Trees that index that row.

If a table has 10 indexes, one INSERT statement actually results in 11 writes (1 for the table, 10 for the indexes).
Rule of Thumb: Index heavily for read-heavy tables (e.g., Product Catalog). Index sparingly for write-heavy tables (e.g., Audit Logs, Sensor Data).

Cardinality

Cardinality is the uniqueness of data in a column.

High Cardinality: user_id, email. Great candidates for indexing.
Low Cardinality: gender, status (active/inactive). Terrible candidates for indexing. If 50% of the table is 'active', the index is useless because the database will decide it's faster to just scan the whole table anyway.

02-indexing.md