-
- Joined
- Mar 22, 2026
-
- Messages
- 434
-
- Reaction score
- 10
-
- Points
- 0
Database performance degradation is one of the most common bottlenecks in modern web applications. As datasets grow from thousands to millions of rows, sequential scans—where the database engine checks every single row to find matching data—become computationally expensive. Understanding how indexing works at a fundamental level is crucial for writing scalable backend systems.
What is a Database Index?
An index is a separate, disk-based data structure (most commonly a B-Tree) that improves the speed of data retrieval operations on a database table. Think of it like the index at the back of a textbook: instead of reading every page to find a specific topic, you look up the term in the index, find the exact page number, and jump straight to it.
Without an index, a query like this:
Requires the database to perform a Full Table Scan ($O(N)$ complexity). With an index on the
How B-Trees Work Under the Hood
The default index type in most relational databases (PostgreSQL, MySQL/InnoDB) is the Balanced Tree (B-Tree). A B-Tree keeps data sorted and allows searches, sequential access, insertions, and deletions in logarithmic time.
1. Root Node: The starting point of the search.
2. Branch/Intermediate Nodes: Contain pointers to child nodes, acting as a roadmap.
3. Leaf Nodes: Contain the actual index keys and either a pointer to the heap-allocated table row or the actual row data itself (in the case of clustered indexes).
Because the keys are stored in a sorted order, range queries (e.g.,
The Cost of Indexing
Indexes are not a silver bullet. Every index comes with trade-offs that every developer must weigh:
Best Practices for Creating Indexes
1. Index Foreign Keys: Columns used in
2. High Cardinality First: Cardinality refers to the uniqueness of data in a column. A
3. Composite Index Ordering: If you have a composite index on
4. Monitor Unused Indexes: Regularly check your database query planner statistics (like
What is a Database Index?
An index is a separate, disk-based data structure (most commonly a B-Tree) that improves the speed of data retrieval operations on a database table. Think of it like the index at the back of a textbook: instead of reading every page to find a specific topic, you look up the term in the index, find the exact page number, and jump straight to it.
Without an index, a query like this:
SQL:
SELECT * FROM users WHERE email = 'test@example.com';Requires the database to perform a Full Table Scan ($O(N)$ complexity). With an index on the
email column, the database uses a tree traversal algorithm to locate the record in $O(\log N)$ time.How B-Trees Work Under the Hood
The default index type in most relational databases (PostgreSQL, MySQL/InnoDB) is the Balanced Tree (B-Tree). A B-Tree keeps data sorted and allows searches, sequential access, insertions, and deletions in logarithmic time.
1. Root Node: The starting point of the search.
2. Branch/Intermediate Nodes: Contain pointers to child nodes, acting as a roadmap.
3. Leaf Nodes: Contain the actual index keys and either a pointer to the heap-allocated table row or the actual row data itself (in the case of clustered indexes).
Because the keys are stored in a sorted order, range queries (e.g.,
WHERE age BETWEEN 20 AND 30) are exceptionally fast. Once the lower bound is found, the storage engine simply reads sequentially through the leaf nodes.The Cost of Indexing
Indexes are not a silver bullet. Every index comes with trade-offs that every developer must weigh:
- Write Overhead: When you
INSERT,UPDATE, orDELETEdata, the database doesn't just modify the table; it also has to update every single index associated with that table. Too many indexes can severely degrade write performance. - Storage Space: Indexes consume disk space. In large tables, indexes can sometimes grow larger than the actual table data itself.
- Maintenance: Over time, heavy write operations cause index fragmentation, requiring periodic rebuilding or re-organizing to maintain optimal performance.
Best Practices for Creating Indexes
1. Index Foreign Keys: Columns used in
JOIN operations (like user_id in an orders table) should almost always be indexed.2. High Cardinality First: Cardinality refers to the uniqueness of data in a column. A
gender column has low cardinality (only a few unique values), making an index on it nearly useless. An email or uuid column has high cardinality, making it a prime candidate for an index.3. Composite Index Ordering: If you have a composite index on
(status, created_at), the database can use it for queries filtering by status, or status AND created_at. However, it *cannot* efficiently use it if you only filter by created_at. Follow the Leftmost Prefix Rule.4. Monitor Unused Indexes: Regularly check your database query planner statistics (like
pg_stat_user_indexes in PostgreSQL) to drop indexes that are never used by the query optimizer.