Groom seems to have forgotten to mention the "merge" part of "log-structured merge" trees, and consequently the "log-structured" part too. He does talk about a "compaction process," but he sort of just doesn't mention the process of selecting what to compact when, or why the compaction process can use purely sequential I/O, which are the crucial aspects of LSM-tree performance.

My unfinished attempt from 02014 to explain LSM-trees (and, in particular, full-text search engines using them) with an implementation in 250 lines of Python 2 is at https://github.com/kragen/500lines/tree/master/search-engine. I think it's a more complete explanation (except for tombstones), but it's longer (half an hour of reading) and there aren't as many illustrations.

On the plus side, you can actually run it:

    $ make
    ./handaxeweb.lua index.py < README.md > index.py
    $ python2 index.py index ../newindex .
    $ python2 index.py grep ../newindex refactor
    README.md:1173:            # XXX refactor chunk reading?  We open_gzipped in three places now.
    index.py:220:        # XXX refactor chunk reading?  We open_gzipped in three places now.
    $ 

I, uh, wouldn't recommend trying to run a high-performance service on my didactic database. It has both zlib and urllib.quote in the inner loop, and its merges are blocking.

I think there are a couple of things in Groom's article that are not really part of LSM-trees per se. Like, bloom filters, or red-black trees, or caching sparse indices (skip files) in RAM. But that's true of mine too, which mixes the LSM-tree with the implementation of a full-text search engine!