3
$\begingroup$

Alright, I'm not sure if this is more of a stack overflow question, but I'm going to try here because you folks seem more suited.

CouchDB makes an interesting claim about using an "append only" B+ tree to index its documents. Specifically...

"In a B-tree, data is kept only in leaf nodes. CouchDB B-trees append data only to the database file that keeps the B-tree on disk and grows only at the end. Add a new document? The file grows at the end. Delete a document? That gets recorded at the end of the file."

and

"CouchDB is actually using a B+ tree, which is a slight variation of the B-tree that trades a bit of (disk) space for speed. When we say B-tree, we mean CouchDB’s B+ tree."

SOURCE: CouchDB Documentation

This paper, describes the problem with an "append only" or "copy on write" implementation of a B+ tree. It suggests that such optimistic concurrency strategies are only available to a standard B tree. Specifically...

"In a regular b-tree leaves are chained together. This is used for tree rebalancing and range lookups. In a b-tree that is updated using copy-on- write leaves cannot be linked together. For example, Figure 2 shows a tree whose rightmost leaf node is C and where the leaves are linked from left to right. If C is updated the entire tree needs to be shadowed. Without leaf-pointers only C, B, and A require shadowing."

SOURCE: Rodeh O.

So the actual question...

Is possible to implement a copy-on-write B+ tree?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

Yes it is. The trick is to use the size of file (where is the tree stored) as the means of calculating offset of the new root. In other words, when one modifies a leaf, most of the tree wont change and the blocks which do change get appended at the end, with root coming last.

More here: http://www.bzero.se/ldapd/btree.html

Improve this answer
$\endgroup$
4
  • $\begingroup$ So in that example, the leaves do not have pointers to the next leaf, which I thought was a defining characteristic of a B+ tree. Without these pointers, a range query requires backtracking and it becomes more expensive to satisfy a query like "all keys > x" or "all keys between x and y". $\endgroup$
    – Eric Rini
    Commented Jan 7, 2016 at 17:46
  • $\begingroup$ "B+" tree means that the inner nodes don't contain data, only the leaf are. Inner nodes are just proxies for keys. The linked list inside the leafs is just a optimization and I fail to see how else one updates it if all there is is copy-on-write. $\endgroup$
    – Ecir Hana
    Commented Jan 7, 2016 at 17:49
  • $\begingroup$ Yeah, fair enough. We've reached the same conclusion then. $\endgroup$
    – Eric Rini
    Commented Jan 7, 2016 at 17:54
  • $\begingroup$ @Eric I agree that the linked list is useful for enumerating all the leafs. But it is not much "more expensive to satisfy a [range] query" since you are touching all the leafs anyway and the very majority of all the nodes are precisely leafs. That's because of the great fanout of B+ trees, which also means that the amount of stack needed to recursively traverse the tree is lower than with BST, for example. $\endgroup$
    – Ecir Hana
    Commented Jan 8, 2016 at 9:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.