Editing B-tree (section)

===Access concurrency===
Lehman and Yao<ref>{{cite journal|title=Efficient locking for concurrent operations on B-trees |year=1981 |doi=10.1145/319628.319663|last1=Lehman |first1=Philip L. |last2=Yao |first2=s. Bing |journal=ACM Transactions on Database Systems |volume=6 |issue=4 |pages=650–670 |s2cid=10756181 |doi-access=free}}</ref> showed that all the read locks could be avoided (and thus concurrent access greatly improved) by linking the tree blocks at each level together with a "next" pointer. This results in a tree structure where both insertion and search operations descend from the root to the leaf. Write locks are only required as a tree block is modified. This maximizes access concurrency by multiple users, an important consideration for databases and/or other B-tree-based [[ISAM]] storage methods. The cost associated with this improvement is that empty pages cannot be removed from the btree during normal operations. (See reference 18<ref>{{Cite web |last=Wang |first=Paul |date=1 February 1991 |title=An In-Depth Analysis of Concurrent B-tree Algorithms |url=http://www.dtic.mil/cgi-bin/GetTRDoc?AD=ADA232287&Location=U2&doc=GetTRDoc.pdf |url-status=dead |archive-url=https://web.archive.org/web/20110604175423/http://www.dtic.mil/cgi-bin/GetTRDoc?AD=ADA232287&Location=U2&doc=GetTRDoc.pdf |archive-date=4 June 2011 |access-date=21 October 2022 |website=dtic.mil}}</ref> for various strategies to implement node merging, and reference 19<ref>{{cite web |title=Downloads - high-concurrency-btree - High Concurrency B-Tree code in C - GitHub Project Hosting |url=https://github.com/malbrain/Btree-source-code |access-date=2014-01-27 |website=[[GitHub]]}}</ref> for source code strategies).

United States Patent 5283894, granted in 1994, appears to show a way to use a 'Meta Access Method'<ref>{{Cite web|url=https://www.freepatentsonline.com/5283894.html|title=Lockless concurrent B-tree index meta access method for cached nodes}}</ref> to allow concurrent B+ tree access and modification without locks. The technique accesses the tree 'upwards' for both searches and updates by means of additional in-memory indexes that point at the blocks in each level in the block cache. No reorganization for deletes is needed and there are no 'next' pointers in each block as in Lehman and Yao.