boltdb/bolt — pull request #148 by benbjohnson (2014-05-02 20:06:06+00:00)
Title: Refactor split/spill

This commit refactors the split/spill functionality. The previous implementation attempted to avoid additional allocations by doing some fancy depth sorting and looping trickery but it was really hard to follow/debug/extend.

The new implementation adds a `node.children` slice that is populated with in-memory child nodes. This makes the `split()` and `spill()` code a simple recursive algorithm and will make #94 easy to fix. This refactor is also required to make inline buckets (#124) possible.

Although there is an extra allocation required for branch nodes, I would expect it to amortize well over transactions. I'll add line notes to the PR for further explanation.

Note: This has no effect on the file format or the API. It's just an internal change.

/cc @snormore @mkobetic