> It's generally my view that from a bird's eye view LSMs are simpler than on-disk Btrees, largely because they are more composable and a lot more of their data is immutable.

I dunno about this. On-disk B-trees can actually be pretty dang simple! Both conceptually and in implementation.

In concept, for an on-disk B-tree "table", you've got:

1. one growable file, or a sequence of fixed-size split files, abstracted over into a "vector of pages" type that you can 1. find the base pointer of, 2. overwrite a full page of, or 3. extend;

2. a "metapage" type, that works like the world's most trivial filesystem: it owns a "freelist" of page numbers, and keeps a pointer to the live root of the B-tree; and it embeds its own hash, and a version number.

3. a mechanism for discovering/choosing the newest live+valid metapage, essentially making this trivial "filesystem" into a trivial "journalling" filesystem. (in e.g. LMDB, you just have two metapages in pages 0 and 1, that are alternately written to, sort of like double-buffering; on DB open, the newer of the two by version is chosen if it's valid by hash; otherwise the older is used.)

4. a readers-writer lock (which doesn't need to be persisted to disk, because the on-disk file is never in a volatile/dirty state. You can just OS-advisory-lock the file — those locks disappear when the creator process dies, which is what you want here);

5. read-only transactions, that take a reader lock, discover the newest live metapage, dereference the B-tree root, and pass that pointer off to the user, letting them have at it, reading the B-tree arbitrarily as if it were an in-memory data structure;

6. read-write transactions, that take a writer lock, discover the newest live metapage, dereference the b-tree root, set up an in-memory dirtied pages map, and then let you read arbitrarily + write arbitrarily (with reads indirected through the dirtied-pages map, acting as an overlay);

7. Copy-on-Write updates to "clean" pages during rw txs, by cloning the clean page contents onto free[listed] pages, dirtying the clone with the update, and adding the dirty version of the page to the dirtied pages map, to overlay the original page;

8. a read-write tx commit op that "propagates" the changes from dirty pages, by Copy-on-Write rewriting the B-tree ancestors of the parent pages to point to the new dirty page numbers, until you derive a new B-tree root page — which you then create a new metapage for, fsync the file, and then write the metapage.

(Note that this last bit means that a read-write transaction will effectively implicitly "roll back" on crash/power cut — the data is written before the "journal entry" for it, so if the "journal" doesn't make it to disk, then the data updates — including the updated freelist — are "lost". All a failed tx has done is update free pages.)

Sure, that's eight things you need to implement. But none of them are complicated or unintuitive, the way that a "lock free concurrent skiplist" is. You could whiteboard any one of those abstractions above with a junior programmer, and they could probably figure out a basically-correct implementation just from the descriptions above.

And that means that the implementations of on-disk B-trees are usually pretty short-and-sweet.

LMDB, for example, is one C file (https://github.com/LMDB/lmdb/blob/mdb.master/libraries/liblm...) with ~8k of actual code (according to https://github.com/AlDanial/cloc).

Postgres's durable B-tree implementation (https://github.com/postgres/postgres/tree/master/src/backend...) is 22kloc, and ~10kloc of actual code.