boltdb/bolt — pull request #181 by benbjohnson (2014-06-02 21:33:03+00:00)
Title: (wip) Allow split nodes to be merged with the next node.

> _NOTE: This is a work-in-progress. Do not merge!_

This commit changes the node.split() functionality to check if the next node has available space and, if so, it will merge the newly split keys into the next node.

Previously, keys could be continually put into the left side of a split causing that first half to split off small right side nodes. This was especially problematic with databases with a high fill percent.

This commit also changes the split so that it can only split into 2 nodes instead of any number of nodes. This makes the split functionality much simpler and easier to understand. The downside is that a lot of large inserts into the same node can cause it to split in an unbalanced way. This, however, typically only happens initially when a DB is bulk loaded into and it will work itself out as the the unbalanced node gets touched again and re-split.

/cc @snormore @mkobetic