On Thu, 2005-04-14 at 11:15 -0400, Tom Lane wrote:
> Simon Riggs <simon@2ndquadrant.com> writes:
> > The move right only occurs when the page is full, so the chance of
> > moving right is not 0.99^250, but 0.99, since the previous 249 inserts
> > would not cause a page split.
>
> Sure, but given that we have a full page, the probability that 250
> successive insertions *all* decide to move right rather than split
> that page is 0.99^250. And it only takes one decision to split to
> maintain the constant-time behavior. So I still think your analysis
> is incorrect.
OK... point accepted. Darn, but also thank goodness it performs.
P(N) > 0.999 for W byte keys, at...
N W Mean blocks read/insert
3 4 bytes 1.1
5 8 bytes 1.4
11 16 bytes 2.1
22 32 bytes 3.6
43 64 bytes 6.7
83 128 bytes 12.5
lots 256 bytes 23
> > IMHO the performance figures show this to be true.
>
> *What* performance figures?
The figures shown on PERFORM recently, with graphs. We still have a
performance issue with insertion rate for large indexes.
Best Regards, Simon Riggs
