4 ms·
If we're replacing blog links with arXiv abstract links, note that there are actually two papers linked, both interesting. "Stratified B-trees and versioning d
by jholman 16y ago
If we're replacing blog links with arXiv abstract links, note that there are actually two papers linked, both interesting.
"Stratified B-trees and versioning dictionaries"
http://arxiv.org/abs/1103.4282 http://arxiv.org/abs/1103.4282
This is actually the newer paper, and presents the "Stratified B-Tree" data structure itself. It also explicitly mentions SSDs and appending, by the way.
"Optimal query/update tradeoffs in versioned dictionaries"
http://arxiv.org/abs/1103.2566 http://arxiv.org/abs/1103.2566
This is a longer and more, shall I say, academic paper. It appears to be incompletely finished, though, because it has a TODO, and also a marginal FIXME.
- andytwigg 16y agoThanks for that. The second paper you reference contains more details of the data structure. I have submitted an updated version of the second paper - it will probably appear on arxiv in 2 days. We have a much improved version of it, though, which I hope to post sometime next week. For more information about append-only B-trees and SSDs, see http://www.acunu.com/2011/04/log-file-systems-and-ssds-made-for-each-other/ http://www.acunu.com/2011/04/log-file-systems-and-ssds-made-...
- leef 16y agoThanks. The paper mentioned an open-source project for this. Does that exist yet?
- andytwigg 16y agoThe core kernel code will be released in the next few weeks, along with a community site, probably code.acunu.com. We hope to post an announcement when that happens.
- crux_ 16y agoI don't suppose there's a chance of seeing the O'Caml implementation released as well, is there? It's neat to see it being used for what (IMO) is a really underutilized sweet spot for the language. (That & the fact that a code release is an invaluable road map for anyone looking to follow in your footsteps.)
- andytwigg 16y agoThe OCaml implementation is what we use internally to test implementations of complicated new data structures, and as such, it's quite unreadable to anyone else! We will probably talk at CUFP about our experiences of OCaml. It definitely has some upsides, but is not without some fairly major downsides (concurrency, serialization, lack of consistently-named library functions, ...) . As such, we're rewriting our basic data structures in Scala - this seems like it keeps most of the benefits but without some of the major problems. Now we know how to implement the structures, we might be able to do a clean implementation which can be released!