Database Indexing

Indexes are data structures used to speed up data retrieval in databases. Proper use of indexes can improve query performance by orders of magnitude.

Why Indexing Matters

Without Index vs With Index

Query without index (Full Table Scan):
┌─────────────────────────────────────┐
│ Table: users (1,000,000 rows)       │
│ Query: WHERE email = 'john@...'     │
│ Operation: Scan all 1,000,000 rows  │
│ Time Complexity: O(n)               │
│ Estimated Time: 500ms - 2s          │
└─────────────────────────────────────┘

Query with index (Index Lookup):
┌─────────────────────────────────────┐
│ Table: users (1,000,000 rows)       │
│ Index: idx_users_email              │
│ Query: WHERE email = 'john@...'     │
│ Operation: B-Tree lookup            │
│ Time Complexity: O(log n)           │
│ Estimated Time: < 1ms               │
└─────────────────────────────────────┘

Query Cost Analysis

Data Size	Full Table Scan (O(n))	B-Tree Index (O(log n))
1,000	1,000 comparisons	~10 comparisons
100,000	100,000 comparisons	~17 comparisons
10,000,000	10,000,000 comparisons	~24 comparisons

Index Fundamentals

What is an Index?

An index is an additional data structure that maintains ordered references pointing to actual data:

Index Structure (B-Tree on email):

                    [john@...]
                   /          \
         [alice@...]           [mike@...]
         /        \             /        \
    [adam@...]  [bob@...]  [kate@...]  [zoe@...]
         |          |          |           |
         ▼          ▼          ▼           ▼
    Row Pointer  Row Pointer  Row Pointer  Row Pointer

Index Trade-offs

Benefits	Costs
Speeds up SELECT queries	Increases storage space
Speeds up JOIN operations	Slows down INSERT performance
Speeds up ORDER BY	Slows down UPDATE performance
Supports unique constraints	Slows down DELETE performance

Rule of thumb: Read-heavy tables benefit from more indexes; write-heavy tables should have indexes added cautiously.

Topics

Index Types - Detailed explanation of B-Tree, Hash, GIN, GiST and other index types
Index Strategies - Advanced strategies: composite indexes, covering indexes, partial indexes

Database Indexing

On this page