On 21.01.2016 10:14, Simon Riggs wrote:
On 21 January 2016 at 06:41, konstantin knizhnik <k.knizh...@postgrespro.ru <mailto: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).

Only if records are inserted in key ascending order...
But usually we need to maintain more than once index and and for them it is not true.

Simon Riggs http://www.2ndQuadrant.com/ <http://www.2ndquadrant.com/>
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

Konstantin Knizhnik
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

Reply via email to