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
SELECTqueries involvingWHERE,JOIN, andORDER BYclauses. - Cons (Writes): Slows down
INSERT,UPDATE, andDELETEoperations. 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,JOINkeys, andORDER BYclauses. - 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