[psaccounts]

The implementation seems to use Log-Structured Merge Trees.

The only paper on this data structure seems to be: http://goo.gl/CVF1l

This paper is poorly written and quite honestly not useful to implement an LSM tree. Does anyone know of a better paper than this one?

[timr]

http://labs.google.com/papers/bigtable.html

[psaccounts]

But it doesn't really describe the LSM data structure!

[timr]

It describes the approach used here (cf. all of the discussion of the tablet system). The few differences are documented:

http://code.google.com/p/leveldb/source/browse/trunk/doc/imp...

[br1]

Read "Cache-Oblivious Streaming B-trees" http://supertech.csail.mit.edu/cacheObliviousBTree.html It' LSM with faster searches.

[psaccounts]

Thanks for the pointer. Are there any known open-source implementations of the same?

[br1]

Not that I know of. Also, they have a patent, but that didn't stop Acunu from reimplementing and improving the algorithm.