The Mechanical Reality of Disk and Memory Access
At their core, database indexing algorithms are optimizations designed to minimize disk I/O and cache misses. When a relational database performs a sequential table scan, it reads every block on disk sequentially. An index creates an auxiliary data structure that reduces lookup complexity from O(N) to O(log N).
B-Trees vs. LSM-Trees: Tradeoffs Decoded
| Characteristic | B-Tree (PostgreSQL, MySQL, SQLite) | LSM-Tree (RocksDB, Cassandra, LevelDB) |
|---|---|---|
| Read Latency | Low and predictable (1-3 pointer hops) | Higher (requires checking memtable & SSTables) |
| Write Throughput | Moderate (random writes to pages) | Extremely high (sequential log appends) |
| Storage Overhead | Higher fragmentation over time | Compact due to periodic compaction passes |
The Leftmost Prefix Rule in Composite Indexes
When creating a multi-column index such as CREATE INDEX idx_users_org_role ON users (org_id, role, created_at);, column order is paramount. The database can efficiently resolve queries filtering on:
org_idorg_id AND roleorg_id AND role AND created_at
However, querying on role or created_at alone bypasses the index entirely because the search tree was branched primarily on org_id.