B+Trees are an old technique, fairly traditional by now. Next-leaf links never did make much sense - as Ohad Rodeh's PDF explains, they don't help you prefetch in parallel. (By the way, Microsoft patented previous-leaf links!) Omitting them is cheap if you have enough memory to keep all blocks on the path from leaf to root in memory, which we certainly do these days - the path is bounded by tree depth and so quite small. Like all tree structures with only child links, copy-on-write is straightforward: Functional programming languages have always implemented copy-on-write for tree structures. What the PDF calls lazy reference counting (compared with, say, WAFL's method), would be called ordinary reference counting when describing a simple tree data structure in memory.
Btrfs is clearly a big step forward in Linux filesystems, and there is undoubtedly a lot of other design in it which is not covered by the academic papers. I'm looking forward to using it, especially the reflink feature and snapshots.
But I'm really surprised that the underlying tree structure and algorithms turn out to be new, or at least not well described in open literature already.
Copyright © 2017, Eklektix, Inc.
Comments and public postings are copyrighted by their creators.
Linux is a registered trademark of Linus Torvalds