I believe when next or prev is called using our current cursor bounds, we always do a key comparison between the returned value and the bound. (e.g. next would compare against upper bound).

I think we could do better by keeping a hint about the bounds key. For example, if we enter the next function for a leaf page, and the upper key is set, and the upper_bound_cell (a new field in the cursor – our hint) is not set, then we could do a quick binary search of the upper bound key to find the upper_bound_cell number. This is the number where we know that all cells below are within bounds. We'd need to account for the fact that new key inserts appear between/before/after cells. As we iterate with next calls, if the cell we are returning (or in between cells) is less than upper_bound_cell number then we don't have to do a bounds comparison.

We'd need to invalidate upper_bound_cell in the cursor in various cases - if we observe that the page has been reconciled since it was computed (so the numbering of keys to cells is completely different), or if we step into a new page, or calls to search/search_near.

A key comparison is probably a pretty significant chunk of time relative to the next() call. If we could replace that by an integer comparison in most cases, this would be a good win.