Thanks 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-...
I 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.)
Re:Copy-on-write B-tree finally beaten.
by andytwigg on Wednesday April 20, 2011 @07:16AM
(#2466122)
The 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!
Thanks. The paper mentioned an open-source project for this. Does that exist yet?
"Stratified B-trees and versioning dictionaries" 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 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.