# Database Indexing

Database indexing is a data structure technique used to quickly locate and access the data in a database table. Indexes are created using a few database columns.

## 1. The Concept

Think of a database index like the **index at the back of a book**.
*   **Without an index:** To find a specific topic, you have to flip through every page of the book (Full Table Scan).
*   **With an index:** You look up the topic in the index, find the page number, and go directly there.

## 2. How it Works (B-Trees)

Most relational databases use **B-Trees** (Balanced Trees) for indexing.
*   A B-Tree keeps data sorted and allows searches, sequential access, insertions, and deletions in logarithmic time.
*   Instead of scanning $N$ records (O(N)), the database traverses the tree levels (O(log N)).

## 3. Pros and Cons

Indexing is a trade-off.

*   **Pros (Reads):** Drastically speeds up `SELECT` queries involving `WHERE`, `JOIN`, and `ORDER BY` clauses.
*   **Cons (Writes):** Slows down `INSERT`, `UPDATE`, and `DELETE` operations. Every time you change data, the database must update the indexes as well.
*   **Cons (Storage):** Indexes take up disk space and memory.

## 4. Types of Indexes

### Clustered Index (Primary)
*   Determines the physical order of data in the table.
*   A table can have only **one** clustered index (usually the Primary Key).
*   The leaf nodes of the B-Tree contain the actual row data.

### Non-Clustered Index (Secondary)
*   Stored separately from the table data.
*   Contains the column value and a pointer (reference) to the actual row in the table.
*   A table can have multiple non-clustered indexes.

### Composite Index
*   An index on two or more columns.
*   **Order matters:** An index on `(Lastname, Firstname)` is useful for searching by Lastname OR Lastname+Firstname, but NOT just Firstname.

## 5. When to Index?

*   **Do Index:** Columns frequently used in `WHERE`, `JOIN` keys, and `ORDER BY` clauses.
*   **Don't Index:** Small tables, columns with low cardinality (e.g., "Gender" with only 2 values), or columns that are frequently updated but rarely searched.

## 6. B-Trees vs. LSM Trees

While B-Trees are the standard for relational databases (read-heavy), Log-Structured Merge-trees (LSM Trees) are popular in NoSQL databases (write-heavy).

### B-Trees (Read Optimized)
*   **Structure:** Data is stored in a sorted tree structure on disk.
*   **Writes:** Random writes are slow because they require disk seeks to update specific pages in the tree.
*   **Reads:** Fast. $O(\log n)$ to find any key.
*   **Used By:** MySQL (InnoDB), PostgreSQL.

### LSM Trees (Write Optimized)
*   **Structure:** Writes are appended to a log in memory (MemTable) and flushed to disk as sorted immutable files (SSTables). Background processes merge these files (Compaction).
*   **Writes:** Extremely fast (sequential writes).
*   **Reads:** Slower. Might need to check MemTable and multiple SSTables on disk.
*   **Used By:** Cassandra, RocksDB, LevelDB.

[[programming/database-basics]]
[[programming/system-design-interview-basics]]