I strongly prefer links to the abstract: http://arxiv.org/abs/1103.4282v2

This lets you: (a) read the abstract before deciding whether or not to read the paper (b) easily find earlier (or later) versions of the paper (c) easily search for other papers the authors have on the arxiv.

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 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.

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.)

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?

The 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.

Hmm, that looks like a different paper. Try this: http://arxiv.org/PS_cache/arxiv/pdf/1103/1103.4282v2.pdf