Simon Riggs <[EMAIL PROTECTED]> 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. > IMHO the performance figures show this to be true. *What* performance figures? You have shown none. We did do performance testing of this algorithm when we adopted it, and it worked fine --- though as I say, I don't think we tested with any very wide keys. regards, tom lane ---------------------------(end of broadcast)--------------------------- TIP 6: Have you searched our list archives? http://archives.postgresql.org