Bob's description is exactly my understanding as well. Though I think we came to the same conclusion together on IRC if memory serves, so this may just be a confirmation that we can both remember a conversation from a few months ago.
Pau On Tue, Jan 12, 2010 at 7:49 AM, Robert Dionne <[email protected]> wrote: > I don't think so, perhaps I misspoke. What I meant was the comment, "a > balancing condition", implied that it was balanced and was merely missing a > particular case. It's not balanced in the textbook sense of having an order n > that determines lower and upper bounds on the number of nodes at each level. > > The amount of branching is determined by a "chunkify" function that write out > chunks of a constant size and so will depend on the key size of kv nodes and > the reductions for the kp nodes. > > So when deletions occur it will be unbalanced in the sense that compaction > results in a different b-tree which requires the reductions to be computed > again. I believe the intent of #224 is that if the b-tree is balanced in the > text book sense that compaction can just be a copy of the nodes. > > I haven't looked at this in some time, and it requires a very detailed > analysis to see if it might in fact be improved, particularly with respect to > views. I'd love to hear Damien's or Jan's or Paul's opinion on this. When I > looked at this last summer I noted there been considerable research in trees > used in databases in recent years. > > > > > On Jan 12, 2010, at 4:02 AM, Brian Candler wrote: > >> On Mon, Jan 11, 2010 at 07:58:10AM -0500, Robert Dionne wrote: >>> jira-224 makes an odd claim that it misses "a balancing condition", it >>> doesn't balance at all so I'm not sure what this means. >> >> If it's not balanced at all, does that mean there are degenerate cases which >> could end up with having to do a linear search through the nodes? >> >> . >> |||| >> \ >> |||| >> \ >> |||| >> \ >> |||| >> >> Could inserting with strictly sequential ids cause that condition to occur? >> (As would be the case with utc_random) > >
