On 21 January 2016 at 06:41, konstantin knizhnik <k.knizh...@postgrespro.ru> wrote:
> 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/ <http://www.2ndquadrant.com/> PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services