While talking to various people during pgCon, I was reminded that the
nbtree README does a poor job of explaining the actual practical
advantages of L&Y from a high level. The "move right" trick is
initially mentioned only as an adjunct to a discussion of the
special-case handling of root page splits, even though it's of huge
significance. We also say this within nbtinsert.c:
/*
* If the page was split between the time that we surrendered our read
* lock and acquired our write lock, then this page may no longer be the
* right place for the key we want to insert. In this case, we need to
* move right in the tree. See Lehman and Yao for an excruciatingly
* precise description.
*/
(Why we need to say something about _bt_moveright() within
_bt_doinsert() that is equally true of both _bt_moveright() callers
isn't clear).
I think that this isn't enough. Attached patch proposes to add a small
paragraph at the top of the nbtree README, to clarify the advantages
of L&Y from a high level. I don't think it's appropriate to state the
advantages of an algorithm in a README file generally, but in this
instance it makes it easier to understand the algorithm.
--
Peter Geoghegan