On 21 January 2016 at 06:41, konstantin knizhnik <k.knizh...@postgrespro.ru>
> Certainly for B-Tree we can organize insert buffer (or pending list) as
> sorted array or also as a tree.
> But in both case complexity of search in this buffer will be O(log(N)),
> not O(1).
You are right; search within this buffer is O(log(N)). But we can test
whether we need to search in the buffer at all with O(1).
Simon Riggs http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services