B-Tree vs LSM-Tree Indexing

Database engines rely on specialized index structures to speed up reads, but choose different architectures depending on read vs write ratios.

📊 B-Tree Index (Read-Optimized)

Used in relational databases like PostgreSQL, MySQL, and SQLite.

• Structure: A self-balancing search tree mapping sorted data pages.
• Trade-off: Fast O(log N) random reads and writes, but updates require random disk I/O.

                  [ Root Node ]
                 /      |      \
         [ Internal ] [ Internal ] [ Internal ]
          /    |   \    /   |   \    /   |   \
        [Leaf][Leaf][Leaf]... Page Data (On Disk)

📊 LSM-Tree Index (Write-Optimized)

Used in NoSQL databases like Cassandra, RocksDB, and DynamoDB.

• Structure: Append-only writes to an in-memory buffer (MemTable), which are flushed periodically to sorted, immutable on-disk files (SSTables).
• Trade-off: Blazing fast write throughput, but reads are slower due to compaction and checking multiple files.