3 ms·
The implementation seems to use Log-Structured Merge Trees. The only paper on this data structure seems to be: http://goo.gl/CVF1l http://goo.gl/CVF1l This pa
by psaccounts 15y ago
The implementation seems to use Log-Structured Merge Trees.
The only paper on this data structure seems to be: http://goo.gl/CVF1l 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 15y agohttp://labs.google.com/papers/bigtable.html http://labs.google.com/papers/bigtable.html
- psaccounts 15y agoBut it doesn't really describe the LSM data structure!
- timr 15y agoIt 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/impl.html http://code.google.com/p/leveldb/source/browse/trunk/doc/imp...
- br1 15y agoRead "Cache-Oblivious Streaming B-trees" http://supertech.csail.mit.edu/cacheObliviousBTree.html http://supertech.csail.mit.edu/cacheObliviousBTree.html It' LSM with faster searches.
- psaccounts 15y agoThanks for the pointer. Are there any known open-source implementations of the same?
- br1 15y agoNot that I know of. Also, they have a patent, but that didn't stop Acunu from reimplementing and improving the algorithm.