Re: Stating the significance of Lehman & Yao in the nbtree README

On Tue, Jul 22, 2014 at 10:49 PM, Peter Geoghegan <pg@heroku.com> wrote:
>> Basically I think it will be better if you can explain in bit more detail
>> that
>> how does "right-links at all levels and high-key" helps to detect and
>> recover from concurrent page splits.
>
> You might be right about that - perhaps I should go into more detail.

I've gone into more detail on what a high key is, and how we arguably
do not follow Lehman & Yao to the letter because we still have read
locks. L&Y's assumption of atomic page reads/writes, and cursory
handling of deletion kind of make it inevitable that read locks are
used, which I now imply. So nbtree isn't a substandard L&Y
implementation - it's a realistic one, which only needs to hold a
single read lock at a time when servicing index scans (or when finding
a place for insertion). I guess Lehman & Yao preferred to put forward
the claim "no read locks" rather than "only one read lock at a time on
internal pages, even for insertion" because there might be some uses
of their algorithm where that is actually realistic. It is really a
sympathetic way of spinning things to say that *no* read locks are
used, though.

--
Peter Geoghegan