boltdb/bolt — pull request #19 by benbjohnson (2014-02-09 06:25:40+00:00)
Title: Rebalance after deletion.

## Overview

Added rebalancing which will combine pages as needed after a key is removed. I also refactored the `node` type to allow sibling traversal.

## How it works

Rebalancing follows some fairly simple rules:

1. A node is a candidate for rebalancing if it is below a "fill threshold" (25%) or it doesn't have the minimum required number of keys (1 for leafs, 2 for branches).

2. If the node is the root node and it's a branch with only one key then collapse the child so it becomes the new root.

3. If the adjacent node has more than enough keys then just move one over.

4. If the adjacent node doesn't have more than the minimum number of keys then merge the two nodes. The reference to one of the nodes will be removed from the parent which will trigger a rebalance on that node.

## Caveats

Currently deletion seems to be dog slow. Not sure why yet but I haven't profiled it yet. Also, I added C-style assertion statements that I'm going to remove before the release. It just helps to track down dumb bugs during development.