Faster inserts with mostly-monotonically increasing values

Here is a patch that implements the idea. If the last insert happens to be in the rightmost block of an index, then we cache the block and check that first for the next insert. For the cached block to be usable for the insert, it should still be the rightmost, the to-be-inserted key should go into the cached block and there is enough free space in the block. If any of these conditions do not meet, we fall back to the regular code path, i.e. descent down the index from the top.

I benchmarked the patch by creating a simple table with just one bigint column and a btree index on it. Here are the results:

So as the size of the index increases, the benefits of the patch also tend to increase. This is most likely because as the index becomes taller and taller, the costs associated with index descent becomes higher.

Patch credit: this work is based on Simon Riggs's original ideas and research.

Thanks,

Pavan