note: Bw-Tree: A B-tree for New Hardware Platforms

In paper, they proposed lock-free version b+tree, especially optimized for cutting-edge flash storage.

They use “delta” to maintain the updating to the pages. Suppose the old page is P, and the updating D, and the page mapping is holding P. D has a link to P. They CAS page mapping to D (CAS(page mapping, P, D)). And it support multiple deltas form a chain, so we can continue to update this page without compact the pages and delta.

“Deltas” technique is also used in bw-tree structure modification, like split/merge.


All the delta contains LSN, that allows updating BwTree before the WAL flush. Because even the system fails, they can recover and erase the deltas which LSN is larger than ESL(end of stable LSN).

They can consolidate the deltas for many reasons. But it must guarantee all the consolidated pages is not larger than RSSP (Redo scan start point).

This approach is an application of Deuteronomy. I think that paper is also worth to read.