Testing BerkeleyDB JE I found strange thing: random fetching from collection of 100000 elements appears to be several times faster than from collection of 140000 elements.
Since I first asked it on StackOverflow, I would not crosspost details, but will provide a link:
Here is my source code.
If I skip the second test and start random fetching immediately after insertion, then the difference is even more significant - 8 seconds for 100000 elements and 3 minutes for 140000 elements. I am definitely missing something, but I could not find out what.