wiredtiger/wiredtiger.github.com — Issue #141: Calculate the midpoint of a tree
Author: wiredtiger
Created: 2012-01-31 19:07:18+00:00
State: open

- maintain a persistent count for each internal node of the number of records in its subtree.
- also maintain an in-memory count of the variation (number of inserts - number of deletes)
- when writing a page, propagate the count to the parent
- to calculate the midpoint of a tree, take half the count of the total numbers in the tree
- search to a leaf page with that count, return the first key.
- may want to combine the calculation with the drop operation to ensure we are dropping on a page boundary.