0600: Atomic Updates

Right now, our DB is log + in-memory array. It’s an in-memory DB with durability. Data size is limited by memory, so we need disk-based data structures. An array is the simplest structure. We will design a format to save the sorted in-memory array to disk.

But array is not a practical data structure, because inserts and deletes are O(N). There are only 2 practical choices: B+Tree and LSM-Tree. Both can evolve from simple arrays, so we can progress in tiny steps, making the full ideas easier to grasp.

We’ll explore the challenges of updating disk-based data structures and their solutions, including copy-on-write, double buffering, physical logging, LSM-Tree. This is chapter is included in the full book.