Hi,
The README in nbtree mentions that L&Y algorithm must couple
locks when moving right during ascent for insertion. However,
it's hard to see why that's necessary. Since L&Y mostly
discussed concurrent insertions and searches, what can go wrong
if inserters only acquire one lock at a time?
The Lanin&ShaSha paper cited in README also agrees that B-link
structure allows inserts and searches to lock only one node at a
time although it's not apparent in L&Y itself.
Thanks,
Hong