Search Postgresql Archives

Re: INSERT ... ON CONFLICT DO UPDATE

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

 



On 20 July 2015 at 15:07, Alvaro Herrera <alvherre@xxxxxxxxxxxxxxx> wrote:
Not sure what type of indexes would be affected by that problem, but I
don't think Postgres' btrees would be.

I admit it's not really my area.​
 
​Take it up with Drew Blas, I guess :)


My first stab at comprehending what he means:

​Imagine if you have around a thousand entries in your index. In a sequential set, the btree could be (with each leaf containing 100 values)
                499
      299                 799
100 200 300 400    500 600 700 800 900 ​

​In a (16-bit, say) random set, the btree could be
                   33208
       21728                         45220
927 15927 ​21729 29661 33209 34917 40121 45221 49826

Inserting a new value in a sequential key is always going to go into the 900 node. When that fills, ​you can add a new node and just balance the parent branches (assuming postgres doesn't try to keep a proper balance across the nodes too?).

However in the random tree a new value could be inserted into _any_ of the leaf nodes, which means you either have to create more leaf nodes than you require (in order to leave plenty of blank space, and even if you do that you will probably end up with uneven fill, which means some searches will be slower than others) or you end up having to refactor all of your nodes every time you insert a value.

Geoff​

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Index of Archives]     [Postgresql Jobs]     [Postgresql Admin]     [Postgresql Performance]     [Linux Clusters]     [PHP Home]     [PHP on Windows]     [Kernel Newbies]     [PHP Classes]     [PHP Books]     [PHP Databases]     [Postgresql & PHP]     [Yosemite]
  Powered by Linux