hesela.devB-link tree
A B-link tree augments an ordered search tree with high keys and right-sibling links so searches can recover from concurrent node splits.
A stale parent route may reach the left half of a newly split node. If the sought key exceeds that node's high key, the search follows a right link toward the correct range. Lehman and Yao's model assumes private page copies and allows reads without acquiring its update locks; section 6.4 explicitly leaves livelock possible. [1]
PostgreSQL adapts the algorithm to shared buffers and uses page-level read locks. The paper's no-read-lock property must not be restated as a lock-free PostgreSQL guarantee. These links solve index-navigation races, not MVCC visibility or crash recovery by themselves. [2]
Relations
Citations
- Lehman and Yao (1981), Efficient Locking for Concurrent Operations on B-Trees, TODS 6(4), 650-670; DOI 10.1145/319628.319663
- PostgreSQL REL_16_15: Btree Indexing, algorithm and shared-buffer differences
Sources & caveats
- Source review of the 1981 algorithm and PostgreSQL REL_16_15 implementation notes; no concurrent workload or speedup was measured.