Fine, I'll Play With Skiplists

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.

I don't know how Rockdb handles this, but this is a very very non-trivial problem in Cassandra.

Let's say your update spans a row of data that is stored across multiple sstables (the row of data, that is a set of column values, was formed in multiple updates that spanned multiple flushes of the mentable to disk/sstables.

So either as part of your update you will be compacting that is rewriting multiple SS tables of unknown size, possibly very large into a new SS table with the new updates, or you must employ some means of time stamping the individual values or in the case of deletes employing something like tombstones or delete markers or timestamps

Then your reed engine needs to be able to read multiple SS tables and apply update ordering in order to find the most recent actual value.

This results in Io stress and reduced performance in the read path.

Lsms exist to scale writes to large indexes. Essentially what you were doing is you are queuing up the updates for a future process (compaction) to clean up.