On Tue, Mar 13, 2012 at 5:50 PM, Bob Dionne <dio...@dionne-associates.com> 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 purity. > 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 <rnew...@apache.org> 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. >
