Database Indexing: B-Trees vs LSM-Trees
Optimize query read latencies using balanced search trees or log-structured merge-tree write buffers.
💡 Why It Matters
Without indexes, searching 10,000,000 rows requires scanning every byte on disk. Indexes keep sorted pointers in memory/disk structures.
🌐 Real-World Production Usages & Examples
PostgreSQL B-Tree Index
Scenario: Finding user by email out of 5,000,000 users.
Outcome: Query latency drops from 450ms to 0.4ms.
✓ When to Use
- •High-cardinality foreign keys and primary keys.
- •Range queries on timestamp or numerical columns.
✕ When NOT to Use
- •Low-cardinality boolean columns (e.g. is_active).
- •Tables with massive write-only volume where index update overhead slows ingestion.
🔑 Core Architecture & Rules
- 1B+ Trees store key-pointer pairs in self-balancing nodes; leaf nodes form a doubly-linked list for fast range scans.
- 2LSM-Trees buffer writes in a MemTable (RAM) and write sequential SSTables to disk, compacting periodically.
⚖️ Architectural Trade-Off Analysis
Write Amplification
PROB-Trees offer fast point lookup.
CONLSM-Trees provide 10x higher write ingestion speed.
⚠️ Failure Modes & Mitigations
Index Fragmentation
Random updates leave empty page gaps.
Mitigation: Run periodic REINDEX / VACUUM FULL operations.
🛠️ Example Usages
Reviewed practical implementations and concrete code walkthroughs for Database Indexing: B-Trees vs LSM-Trees.
algorithm walkthroughexecutable tested
LSM-Tree MemTable Flush & Compaction Trace
Step-by-step trace showing RAM write buffering in MemTable flushing sequentially to disk SSTable files.
⬡Explore Related Concepts & Guides
Curated technical reading and direct concept relationships.
📖Core Implementation Guides & Patterns(14 resources)
ArticleChoosing the Right Database: CAP Theorem and Practical Use Cases
Read Article →ArticleAzure Cosmos DB API Modes Explained: NoSQL, MongoDB, Cassandra, PostgreSQL, Gremlin, and Table
Read Article →ArticleAzure Cosmos DB Consistency Levels Explained: Strong, Bounded Staleness, Session, Consistent Prefix, and Eventual
Read Article →🔗 Related Concepts
Explore full connection graph →⚡ Next Step · Apply Concept
Ready to apply Database Indexing: B-Trees vs LSM-Trees?
Test your understanding with a short scenario about real system constraints and trade-offs.