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)
