Re: Batch update of indexes - Mailing list pgsql-hackers

On 21 January 2016 at 06:41, konstantin knizhnik <k.knizhnik@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/
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

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