Database Indexing Strategies
Why Indexes Matter
Section titled “Why Indexes Matter”Without indexes, databases must scan every row to find data. With indexes, databases can jump directly to the data they need.
Index Structure Basics
Section titled “Index Structure Basics”An index is a separate data structure that maps search keys to data locations.
Key Concept: Index stores keys (what you search by) mapped to locations (where the data is).
Strategy 1: B-Tree Index
Section titled “Strategy 1: B-Tree Index”B-tree (Balanced Tree) is the most common index structure in SQL databases. It’s a self-balancing tree that keeps data sorted.
How B-Tree Works
Section titled “How B-Tree Works”Search Process:
- Start at root
- Compare key with node values
- Follow appropriate branch
- Repeat until leaf node
- Time: O(log n) - logarithmic time!
B-Tree Characteristics
Section titled “B-Tree Characteristics”Pros:
- ✅ Fast reads: O(log n) lookups
- ✅ Range queries: Efficient “WHERE x BETWEEN a AND b”
- ✅ Sorted data: Data stays sorted
- ✅ Mature: Well-understood, optimized
Cons:
- ❌ Slower writes: Must rebalance tree
- ❌ Random writes: Not optimized for sequential writes
- ❌ Write amplification: One write can cause multiple disk writes
Used in: PostgreSQL, MySQL, SQL Server, Oracle
Strategy 2: LSM Tree
Section titled “Strategy 2: LSM Tree”LSM (Log-Structured Merge) Tree optimizes writes by batching them in memory and merging to disk.
How LSM Tree Works
Section titled “How LSM Tree Works”Key Concept: Writes go to fast memory first, then flush to disk in batches. Background process merges files.
LSM Tree Characteristics
Section titled “LSM Tree Characteristics”Pros:
- ✅ Fast writes: Sequential writes, batched operations
- ✅ High throughput: Can handle millions of writes/second
- ✅ Write-optimized: Designed for write-heavy workloads
- ✅ Compression: Merging compacts data
Cons:
- ❌ Slower reads: May need to check multiple files
- ❌ Read amplification: One read may touch multiple files
- ❌ Compaction overhead: Background merging uses resources
Used in: Cassandra, RocksDB, LevelDB, HBase
Strategy 3: Inverted Index
Section titled “Strategy 3: Inverted Index”Inverted index maps words to documents containing them. Used in search engines and full-text search.
How Inverted Index Works
Section titled “How Inverted Index Works”Key Concept: Instead of “document → words”, store “word → documents” for fast keyword lookups.
Inverted Index Example
Section titled “Inverted Index Example”Documents:
- Doc1: “The cat sat on the mat”
- Doc2: “The dog chased the cat”
- Doc3: “A bird flew away”
Inverted Index:
1the → [Doc1, Doc2]2cat → [Doc1, Doc2]3dog → [Doc2]4bird → [Doc3]5sat → [Doc1]6mat → [Doc1]7chased → [Doc2]8flew → [Doc3]9away → [Doc3]Query: “cat”
- Lookup “cat” in index → [Doc1, Doc2]
- Result: Doc1 and Doc2 contain “cat”
- Fast! No need to scan all documents
Inverted Index Characteristics
Section titled “Inverted Index Characteristics”Pros:
- ✅ Fast search: O(1) word lookup
- ✅ Boolean queries: AND, OR, NOT operations
- ✅ Phrase queries: Find exact phrases
- ✅ Ranking: Can rank results by relevance
Cons:
- ❌ Storage overhead: Index can be large
- ❌ Update cost: Must update index when documents change
- ❌ Complexity: More complex than simple indexes
Used in: Elasticsearch, Lucene, Solr, full-text search
B-Tree vs LSM Tree: When to Use What?
Section titled “B-Tree vs LSM Tree: When to Use What?”| Aspect | B-Tree | LSM Tree |
|---|---|---|
| Read Performance | ✅ Fast (O(log n)) | ⚠️ Slower (may check multiple files) |
| Write Performance | ⚠️ Slower (must rebalance) | ✅ Very fast (batched) |
| Range Queries | ✅ Excellent | ⚠️ Good |
| Storage | ✅ Efficient | ⚠️ More overhead (multiple files) |
| Use Case | Read-heavy, SQL databases | Write-heavy, NoSQL databases |
Index Design Best Practices
Section titled “Index Design Best Practices”1. Index Frequently Queried Columns
Section titled “1. Index Frequently Queried Columns”Rule: Index columns used in WHERE, JOIN, and ORDER BY clauses.
2. Composite Indexes for Multi-Column Queries
Section titled “2. Composite Indexes for Multi-Column Queries”Rule: For queries with multiple WHERE conditions, create composite indexes.
3. Don’t Over-Index
Section titled “3. Don’t Over-Index”Rule: Monitor index usage. Remove unused indexes. Balance read speed vs write performance.
LLD ↔ HLD Connection
Section titled “LLD ↔ HLD Connection”How indexing strategies affect your code design:
Index-Aware Query Design
Section titled “Index-Aware Query Design”1class UserRepository:2 def __init__(self, db_connection):3 self.db = db_connection4 # Ensure indexes exist5 self._create_indexes()6
7 def _create_indexes(self):8 """Create indexes for common queries"""9 # Index on email (frequent lookup)10 self.db.execute("""11 CREATE INDEX IF NOT EXISTS idx_users_email12 ON users(email)13 """)14
15 # Composite index for user queries16 self.db.execute("""17 CREATE INDEX IF NOT EXISTS idx_users_status_created18 ON users(status, created_at)19 """)20
21 def find_by_email(self, email: str):22 """Uses email index - fast!"""23 cursor = self.db.execute(24 "SELECT * FROM users WHERE email = %s",25 (email,)26 )27 return cursor.fetchone()28
29 def find_active_recent(self, days: int):30 """Uses composite index - fast!"""31 cursor = self.db.execute("""32 SELECT * FROM users33 WHERE status = 'active'34 AND created_at > NOW() - INTERVAL %s DAY35 ORDER BY created_at DESC36 """, (days,))37 return cursor.fetchall()1import java.sql.*;2
3public class UserRepository {4 private Connection connection;5
6 public UserRepository(Connection connection) {7 this.connection = connection;8 createIndexes();9 }10
11 private void createIndexes() {12 // Create indexes for common queries13 try (Statement stmt = connection.createStatement()) {14 // Index on email (frequent lookup)15 stmt.execute("""16 CREATE INDEX IF NOT EXISTS idx_users_email17 ON users(email)18 """);19
20 // Composite index for user queries21 stmt.execute("""22 CREATE INDEX IF NOT EXISTS idx_users_status_created23 ON users(status, created_at)24 """);25 } catch (SQLException e) {26 // Index might already exist27 }28 }29
30 public User findByEmail(String email) throws SQLException {31 // Uses email index - fast!32 try (PreparedStatement stmt = connection.prepareStatement(33 "SELECT * FROM users WHERE email = ?"34 )) {35 stmt.setString(1, email);36 ResultSet rs = stmt.executeQuery();37 if (rs.next()) {38 return mapToUser(rs);39 }40 }41 return null;42 }43
44 public List<User> findActiveRecent(int days) throws SQLException {45 // Uses composite index - fast!46 try (PreparedStatement stmt = connection.prepareStatement("""47 SELECT * FROM users48 WHERE status = 'active'49 AND created_at > NOW() - INTERVAL ? DAY50 ORDER BY created_at DESC51 """)) {52 stmt.setInt(1, days);53 ResultSet rs = stmt.executeQuery();54 List<User> users = new ArrayList<>();55 while (rs.next()) {56 users.add(mapToUser(rs));57 }58 return users;59 }60 }61}Deep Dive: Production Indexing Considerations
Section titled “Deep Dive: Production Indexing Considerations”B-Tree: Advanced Performance Characteristics
Section titled “B-Tree: Advanced Performance Characteristics”Write Amplification in B-Trees
Section titled “Write Amplification in B-Trees”Write Amplification: One logical write causes multiple physical writes.
Example:
- Logical write: Update one row
- Physical writes:
- Write to data page
- Write to index page (B-tree node)
- Write to WAL (Write-Ahead Log)
- Total: 3-5x amplification
Production Impact:
- SSD wear: More writes = shorter SSD lifespan
- Throughput: Limited by write amplification
- Latency: Higher latency due to multiple writes
Mitigation:
- Batch writes: Group multiple updates
- Delayed index updates: Update index asynchronously
- SSD optimization: Use SSDs with high write endurance
B-Tree Node Size Optimization
Section titled “B-Tree Node Size Optimization”Node Size: Affects tree height and performance.
Small Nodes (4KB):
- ✅ Shallow tree: More nodes, but fits in cache
- ✅ Cache-friendly: More nodes in memory
- ❌ More I/O: More nodes to read
Large Nodes (64KB):
- ✅ Deep tree: Fewer nodes, less I/O
- ❌ Cache-unfriendly: Fewer nodes fit in cache
- ❌ Waste: May read unused data
Production Defaults:
- PostgreSQL: 8KB pages (good balance)
- MySQL InnoDB: 16KB pages (optimized for modern SSDs)
- SQL Server: 8KB pages
Best Practice: Use database defaults unless profiling shows issues
LSM Tree: Production Tuning
Section titled “LSM Tree: Production Tuning”Compaction Strategies Comparison
Section titled “Compaction Strategies Comparison”Size-Tiered Compaction (STCS):
How it works:
- Small files merged into larger files
- Files organized by size tiers
Pros:
- ✅ Simple to understand
- ✅ Good for write-heavy workloads
- ✅ Low write amplification
Cons:
- ❌ High read amplification (many files to check)
- ❌ Space amplification (temporary duplicates)
Use case: Write-heavy, read-light workloads
Leveled Compaction (LCS):
How it works:
- Files organized into levels
- Each level is 10x larger than previous
- Files within level don’t overlap
Pros:
- ✅ Low read amplification (fewer files to check)
- ✅ Predictable space usage
- ✅ Better for read-heavy workloads
Cons:
- ❌ Higher write amplification (more rewriting)
- ❌ More complex
Use case: Read-heavy, balanced workloads
Production Example: Cassandra
- Default: Size-tiered compaction
- Alternative: Leveled compaction (tunable)
- Choice: Based on read/write ratio
LSM Tree Write Stall Problem
Section titled “LSM Tree Write Stall Problem”Problem: Compaction can’t keep up with writes.
Symptoms:
- Write latency spikes: Writes stall waiting for compaction
- Disk I/O saturation: Compaction consumes all I/O
- Throughput degradation: System slows down
Solutions:
Solution 1: Throttle Writes
1class ThrottledLSMWriter:2 def write(self, key, value):3 # Check compaction lag4 if self.compaction_lag > threshold:5 # Throttle writes6 time.sleep(0.1) # Slow down writes7 self.memtable.write(key, value)Solution 2: Increase Compaction Threads
- More threads = faster compaction
- Trade-off: More CPU/memory usage
Solution 3: Tune Compaction Parameters
- Adjust compaction thresholds
- Balance between write speed and read performance
Inverted Index: Production Optimization
Section titled “Inverted Index: Production Optimization”Index Size Management
Section titled “Index Size Management”Challenge: Inverted indexes can be larger than original data.
Example:
- Original documents: 10GB
- Inverted index: 15GB (150% of original!)
Why so large:
- Stores word → document mappings
- Posting lists (lists of document IDs)
- Term frequencies, positions
Optimization Techniques:
1. Stop Words Removal
- Remove common words (“the”, “a”, “an”)
- Reduction: 20-30% index size
2. Stemming
- Reduce words to root (“running” → “run”)
- Reduction: 10-20% index size
3. Compression
- Compress posting lists (delta encoding)
- Reduction: 50-70% index size
Production Example: Elasticsearch
- Uses compression by default
- Index size: Typically 30-50% of original data
- Trade-off: Slightly slower queries (decompression overhead)
Query Performance Optimization
Section titled “Query Performance Optimization”Challenge: Complex queries can be slow.
Optimization Techniques:
1. Boolean Query Optimization
Bad:
1# Query all documents, then filter2results = index.search("term1 AND term2 AND term3")3# Checks all documents with term1Good:
1# Start with rarest term2results = index.search("rare_term AND common_term")3# Checks fewer documents firstRule: Process terms from rarest to most common
2. Caching Frequent Queries
Pattern: Cache query results.
1class CachedSearchEngine:2 def __init__(self, index, cache):3 self.index = index4 self.cache = cache5
6 def search(self, query):7 # Check cache first8 cache_key = f"query:{hash(query)}"9 cached = self.cache.get(cache_key)10 if cached:11 return cached12
13 # Execute query14 results = self.index.search(query)15
16 # Cache results17 self.cache.set(cache_key, results, ttl=300)18 return resultsBenefit: 10-100x faster for repeated queries
Index Maintenance: Production Considerations
Section titled “Index Maintenance: Production Considerations”Index Rebuilding Strategies
Section titled “Index Rebuilding Strategies”When to Rebuild:
- Fragmentation: Index becomes fragmented (slow queries)
- Statistics outdated: Query planner uses wrong estimates
- Schema changes: Adding/removing indexes
Strategies:
1. Online Rebuild (Zero Downtime)
- PostgreSQL:
REINDEX CONCURRENTLY - MySQL: Online DDL (5.6+)
- Benefit: No downtime
- Cost: Slower, uses more resources
2. Offline Rebuild (Faster)
- PostgreSQL:
REINDEX - MySQL:
ALTER TABLE ... DROP INDEX, ADD INDEX - Benefit: Faster
- Cost: Table locked during rebuild
Production Pattern:
- Use online rebuild for production (zero downtime)
- Use offline rebuild during maintenance windows
Index Monitoring and Maintenance
Section titled “Index Monitoring and Maintenance”What to Monitor:
1. Index Usage
1-- PostgreSQL: Find unused indexes2SELECT schemaname, tablename, indexname, idx_scan3FROM pg_stat_user_indexes4WHERE idx_scan = 05ORDER BY pg_relation_size(indexrelid) DESC;2. Index Bloat
1-- PostgreSQL: Find bloated indexes2SELECT schemaname, tablename, indexname,3 pg_size_pretty(pg_relation_size(indexrelid)) as size4FROM pg_stat_user_indexes5WHERE pg_relation_size(indexrelid) > 1000000000 -- >1GB6ORDER BY pg_relation_size(indexrelid) DESC;3. Index Fragmentation
- Monitor index scan performance
- Alert on degradation
- Rebuild when fragmentation >20%
Production Automation:
1class IndexMaintenance:2 def monitor_indexes(self):3 unused = self.find_unused_indexes()4 bloated = self.find_bloated_indexes()5
6 # Alert on unused indexes7 if unused:8 self.alert(f"Unused indexes: {unused}")9
10 # Schedule rebuild for bloated indexes11 if bloated:12 self.schedule_rebuild(bloated)Performance Benchmarks: Real-World Index Performance
Section titled “Performance Benchmarks: Real-World Index Performance”B-Tree vs LSM Tree: Production Comparison
Section titled “B-Tree vs LSM Tree: Production Comparison”| Metric | B-Tree | LSM Tree |
|---|---|---|
| Read Latency (point) | 1-5ms | 5-20ms |
| Read Latency (range) | 5-10ms | 10-50ms |
| Write Latency | 5-20ms | 1-5ms |
| Write Throughput | 1K-10K ops/sec | 10K-100K ops/sec |
| Read Throughput | 10K-50K ops/sec | 5K-20K ops/sec |
| Space Amplification | 1.1x | 1.5-2x |
| Write Amplification | 3-5x | 2-10x (during compaction) |
Key Insights:
- B-Tree: Better for read-heavy workloads
- LSM Tree: Better for write-heavy workloads
- Hybrid: Some databases use both (e.g., RocksDB with B-Tree for reads)
Index Impact on Query Performance
Section titled “Index Impact on Query Performance”Benchmark: 1M row table, query by indexed column
| Scenario | Without Index | With Index | Improvement |
|---|---|---|---|
| Point lookup | 500ms | 2ms | 250x faster |
| Range query | 800ms | 5ms | 160x faster |
| Join on indexed column | 2000ms | 50ms | 40x faster |
| Order by indexed column | 1500ms | 10ms | 150x faster |
Key Insight: Indexes provide 40-250x performance improvement!
Advanced Indexing Patterns
Section titled “Advanced Indexing Patterns”Pattern 1: Partial Indexes
Section titled “Pattern 1: Partial Indexes”Pattern: Index only subset of rows.
Example:
1-- Index only active orders2CREATE INDEX idx_active_orders3ON orders(order_date)4WHERE status = 'active';Benefits:
- ✅ Smaller index (only active orders)
- ✅ Faster queries (fewer rows to scan)
- ✅ Less maintenance overhead
Use case: Queries that filter by common condition
Pattern 2: Covering Indexes
Section titled “Pattern 2: Covering Indexes”Pattern: Index contains all columns needed for query.
Example:
1-- Query: SELECT name, email FROM users WHERE country = 'USA'2-- Covering index includes all columns3CREATE INDEX idx_users_country_name_email4ON users(country, name, email);Benefits:
- ✅ Index-only scan: Don’t need to read table
- ✅ Faster queries: 2-5x faster than regular index
- ✅ Less I/O: No table access needed
Trade-off: Larger index (more columns)
Pattern 3: Expression Indexes
Section titled “Pattern 3: Expression Indexes”Pattern: Index on computed expression.
Example:
1-- Index on lowercased email (case-insensitive search)2CREATE INDEX idx_users_email_lower3ON users(LOWER(email));4
5-- Query uses index6SELECT * FROM users WHERE LOWER(email) = 'alice@example.com';Benefits:
- ✅ Enables index usage for computed queries
- ✅ Faster than full table scan
Use case: Queries with functions/expressions
Key Takeaways
Section titled “Key Takeaways”What’s Next?
Section titled “What’s Next?”Congratulations! You’ve completed the Database & Storage Systems section. You now understand:
- Relational databases (ACID, normalization, indexing)
- Isolation levels (read committed, repeatable read, serializable)
- Scaling strategies (read replicas, connection pooling)
- Sharding & partitioning (horizontal vs vertical)
- NoSQL databases (Document, Key-Value, Column-family, Graph)
- Database selection (decision framework)
- Indexing strategies (B-trees, LSM trees, inverted indexes)
Next up: Explore Caching & Performance Optimization — Learn caching strategies to make your systems even faster!