Comparison
B-tree indexvsLSM tree
B-tree index
you add an index and the query that was scanning ten million rows starts answering in a millisecond by walking a sorted tree.
The default index structure in relational databases: a balanced, sorted tree giving logarithmic lookups and cheap range scans in key order. It is excellent for reads and mediocre for write-heavy workloads, because every insert may split pages in place. Each index you add is another structure every write has to maintain.
Full entry →LSM tree
writes go to an in-memory table and an append-only log, and a background process keeps merging the files on disk behind you.
The storage engine behind Cassandra, RocksDB and friends: buffer writes in memory, flush them as immutable sorted files, and compact those files in the background. It turns random writes into sequential ones, which is why it beats B-trees on write throughput. The bill arrives as read amplification and as compaction that competes with your traffic for disk and CPU at the worst possible time.
Full entry →