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
