> > So yes, the benefits of the patch go down with higher number of clients, but > it does not entirely vanish.
What if you implement my suggestion?
That should improve the multi-client case considerably.
Yes, I will try that next - it seems like a good idea. So the idea would be: check if the block is still the rightmost block and the insertion-key is greater than the first key in the page. If those conditions are satisfied, then we do a regular binary search within the page to find the correct location. This might add an overhead of binary search when keys are strictly ordered and a single client is inserting the data. If that becomes a concern, we might be able to look for that special case too and optimise for it too.
