couchdb-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Paul Davis <>
Subject Re: Fundamentals Question on CoucheDB's append only b+tree.
Date Wed, 14 Mar 2012 02:10:34 GMT
On Tue, Mar 13, 2012 at 5:50 PM, Bob Dionne
<> wrote:
> That's largely correct, though couchdb's btree is neither fish nor fowl.
> It doesn't have an order (B-trees generally do) and it does store values in the inner
nodes (B+trees do not)

The lack of order is the big thing. Though I'd slightly disagree with
the no values in inner nodes assessment. Strictly speaking, I would
say they do not as to get a key's value you have to read through to a
leaf node. I would guess that you're referring to the reduction values
stored on internal nodes, and while they are "values" technically,
they aren't the "value" of the "key/value" type. Specifically, they
don't have a 1:1 mapping to keys.

IOW, the internal storage of reductions directly in the inner-nodes is
an extension to the b+tree algorithm that could be done perfectly
validly in a textbook example of b+trees.

OTOH, I definitely agree about the lack of order. Sadly each time I've
tried to enforce that I end up making the whole thing considerably
slower so in this case engineering pragmatism wins over theoretical

> As Paul might say it's a B~tree
> On Mar 13, 2012, at 3:31 PM, Randall Leeds wrote:
>> On Tue, Mar 13, 2012 at 10:40, Robert Newson <> wrote:
>>> There's no linked list running between the leafs. A b+tree doesn't
>>> require one, though it's a common addition. The b+tree algorithm is a
>>> revision over a binary tree (where inner nodes point strictly at one
>>> left and one right item). To be a b+tree you need to hold many
>>> pointers on an inner node.
>> I thought being a B-tree was to have many pointers in inner nodes, being a
>> B+tree was to have *only* pointers in inner nodes and the values all at the
>> leaf nodes.
>> Whatever it's called, the latter is what CouchDB has.

View raw message