"""B-Link-Trees: Lehman and Yao’s paper actually discusses an innovation they researched related to concurrency and locking when multiple threads are using the

"""B-Link-Trees: Lehman and Yao’s paper actually discusses an innovation they researched related to concurrency and locking when multiple threads are using the same B-Tree. Remember, Postgres’s code and algorithms need to be multithreaded because many clients could be searching or modifying the same index at the same time. By adding another pointer from each B-Tree node to the next sibling node — the so-called “right arrow” — one thread can search a tree even while a second thread is splitting a node without locking the entire index""" The big innovation of Lehman and Yao was that their right link technique obviates the need for "latch coupling", or in Postgres terms the crabbing of buffer locks. In other words, the Postgres implementation need only lock one page/buffer at a time as an index scan descends the B-Tree, rather than alternately locking a single page, then its child, then unlocking the parent, and once again locking the child (the grandchild of the original page). Certain other B-Tree implementations must do this until their descent reaches a leaf page, and locking multiple pages at once just to service index scans can hurt concurrency a lot (I think that they might need to be exclusive locks for writes, which is particularly poor). These low-level locks are not to be confused with lock manager locks that have deadlock detection and so on. They're low-level Readers–writer locks, and are far more lightweight (hence the Postgres term "LWLock"). The basic idea of Lehman and Yao is that index scans of all types may detect and recover from a concurrent page split my following a right-link (having found that the page high key is logically less than the scankey value). It won't matter that the parent page was observed to not have the new downlink that is inserted after a page split, except that we need to look right.