Part 2 of 8 · 2 min read
Two ways to keep sorted data on disk
Fixed pages updated in place, against sorted files that are only appended and merged.
Think of two ways to keep a sorted address book. The first is a ring binder with a page for each letter range. To add a name, the owner finds the right page and writes it in, and when a page is full, it is split into two. The second is a stack of small booklets. New names go into a new booklet. From time to time, the owner merges booklets into one larger sorted booklet.
These are the two designs.
Storage engine
A storage engine is the part of a database that decides how data is laid out on disk, how it is written and how it is found again.
Example: InnoDB is the storage engine of MySQL. RocksDB is a storage engine used inside many other databases.
The book "Designing Data-Intensive Applications" separates the two families.
- Page-oriented engines, such as the B-tree. The data is broken into fixed-size blocks called pages, traditionally 4 KB, and one page is read or written at a time. This fits the way disks are built.
- Log-structured engines, such as the LSM-tree. The data is broken into variable-size segments of several megabytes or more, and each segment is written in one sequential go.
Both keep keys in sorted order, which allows fast lookups of one key and fast range queries. Their ideas about writing are opposite: the B-tree overwrites pages in place, and the log-structured engine never modifies a file after writing it.
Sequential and random writes
A sequential write adds data right after the previous data on disk. A random write goes to a place far from the last one.
Example: adding a line at the end of a file is sequential. Changing 4 KB in the middle of a large file is random.
On a magnetic disk, the book notes, sequential writes are much faster than random ones, because the disk head does not need to move. On solid-state disks the gap is smaller, though a log-structured pattern still helps.
Read it as
B-tree: find the place and change it there. LSM-tree: write at the end now and tidy up later.
Check yourself:
- Which design never modifies a file after it is written?
- Why do sequential writes matter on a magnetic disk?