@michaelcahill: here are the changes that I believe resolve WT-596.

They've only been lightly tested, but appear to do what we expected; results from pixiebob:

 0 additional prefix bytes: old  3.73, new 3.27 (2.68%)
 5 additional prefix bytes: old  4.55, new 3.67 (19.34%)
10 additional prefix bytes: old  5.41, new 3.95 (26.99%)
25 additional prefix bytes: old  7.67, new 4.55 (40.68%)
50 additional prefix bytes: old 11.83, new 5.51 (53.42%)

I also swapped the meanings of skiphigh and skiplow in the code, it made a little more sense to me to update skiphigh when the search key was smaller than the tree key, please check me on that, though.

I didn't see anywhere else we should change, let me know if there are other places to think about.