Storage Engines

How a database lays data out on disk and in memory: pages, B-trees, heaps and clustered indexes, the buffer pool, LSM-trees and compaction, and the read, write and space costs of each design.

Overview

A storage engine is the part of a database that decides how rows are laid out on disk, how they are cached in memory, and how they are found again. The query planner decides what to read; the storage engine decides what that read costs.

Two main designs cover most of the databases in use. A B-tree engine keeps data in fixed-size pages sorted by key and updates those pages in place. PostgreSQL and MySQL's InnoDB work this way. A log-structured merge tree (LSM-tree) never updates in place: it buffers writes in memory, writes them out as sorted, immutable files, and merges those files in the background. RocksDB, LevelDB and Cassandra work this way.

Neither design is better in every case. A B-tree gives predictable reads and pays on writes. An LSM-tree turns random writes into sequential ones and pays on reads and in background merging. Interviewers ask about storage engines to see whether you can connect a workload to that cost.

What you will be able to do

  • Walk through a point lookup and an insert in a B-tree, including a page split, and estimate the tree's height.
  • Explain the difference between a heap table with separate indexes (PostgreSQL) and a clustered index (InnoDB).
  • Explain what a buffer pool caches, how it chooses what to evict, and how large to make it.
  • Walk through the write and read paths of an LSM-tree, and explain what compaction and Bloom filters are for.
  • Compare the two designs with read, write and space amplification, and pick one for a workload.

Key concepts

  • Pages
  • B-tree engines
  • Heap vs clustered index
  • Buffer pool
  • LSM-trees
  • Memtables and SSTables
  • Compaction
  • Bloom filters
  • Write, read and space amplification

Interview questions

  • Walk me through a point lookup and an insert in a B-tree.
  • How does an LSM-tree handle writes and reads, and what is compaction for?
  • You are storing billions of sensor readings per day and mostly reading the last hour. B-tree or LSM-tree?
  • What is write amplification, and where does it come from in each design?
  • How does a buffer pool work, and how big should it be?
  • How does InnoDB's clustered index differ from PostgreSQL's heap, and why does it matter for the primary key?

Sign up free to read the full topic

More Databases & SQL topics

Start free on Cariara · Coding problems · System design studio