Data Systems
Database Indexing
Indexes enable efficient data retrieval without scanning entire tables. Choosing the right index structure and strategy is critical for query performance at scale.
- B-Tree â Balanced tree for reads and range queries
- LSM Tree â Write-optimized structure for high throughput
- Composite Index â Multi-column indexes for complex queries
Indexing is the single most impactful optimization for database performance.
Why Index?
Without an index, every query scans the entire table. Indexes create auxiliary data structures that map search keys to row locations.
B-Tree Index
The most common index structure in relational databases.
B-Tree Properties
| Property | Value |
|---|---|
| Height | O(log n) â typically 3-4 for billions of rows |
| Lookup | O(log n) â follow path from root to leaf |
| Range scan | O(k + log n) â traverse linked leaves |
| Insert/Delete | O(log n) â with rebalancing |
| Block size | Typically 4KB-16KB (aligns with disk pages) |
LSM Tree
Write-optimized index for high-throughput systems.
B-Tree vs LSM Tree
| Aspect | B-Tree | LSM Tree |
|---|---|---|
| Write pattern | Random I/O | Sequential I/O |
| Read pattern | O(log n) single lookup | May check multiple levels |
| Write throughput | Moderate | High (10-100x) |
| Read throughput | High | Moderate |
| Space efficiency | Fragmentation over time | Better (compaction) |
| Write amplification | Low | High (compaction) |
| Use case | OLTP, mixed workloads | Write-heavy, time-series |
Index Types
Primary Index
Secondary Index
Composite Index
Covering Index
Index Selection
Practice Exercises
-
Analysis: A table has 100M rows with a B-tree index on column
status. There are only 3 distinct values (active, inactive, pending). Should you use this index for a query filteringstatus = 'active'? -
Design: Design composite indexes for these queries:
- SELECT * FROM orders WHERE user_id = ? AND status = 'shipped' ORDER BY created_at DESC
- SELECT * FROM orders WHERE created_at > ? AND total > 100
-
Comparison: Compare B-tree and LSM tree performance for a time-series database receiving 100K writes/second with occasional range queries.
-
Optimization: A query takes 5 seconds with a full table scan. The table has 50M rows. After adding an index, it takes 50ms. Explain the improvement and identify what else could be done.
What to Learn Next
-> Databases SQL vs NoSQL, indexing, replication, and sharding.
-> Data Partitioning Horizontal partitioning, range vs hash partitioning.
-> Data Replication Leader-follower, multi-leader, and conflict resolution.
-> Scalability Fundamentals Vertical vs horizontal scaling and capacity planning.
-> Caching Redis, Memcached, cache strategies, and invalidation.
-> Event-Driven Architecture Event sourcing, CQRS, and saga patterns.