Concurrent operations on B-trees with overtaking
Concurrent operations on B-trees with overtaking
复制标题
带超车的 B 树并发操作
DOI：
--
复制
发表时间：
1985
期刊：
影响因子：
--
通讯作者：
Y. Sagiv
中科院分区：
文献类型：
--
作者：
Y. Sagiv
出现了B ∗ -Trees上的并发操作算法（即搜索，插入和删除）。 ，由于插入过程只能随时仅锁定一个节点（与同时同时锁定两个或三个节点相反。由于某些删除，压缩了树是通过与其他操作同时运行的过程，可以定期扫描整个树。这些压缩过程可能会与其他操作同时运行，并且它们仅扫描必须压缩的节点。
Algorithms for concurrent operations (i.e., searches, insertions, and deletions) on B∗-trees are presented. These algorithms improve those given by Lehman and Yao (ACM Trans. Database Systems 6, No. 4 (1981), 650–670), since an insertion process has to lock only one node at any time (as opposed to locking simultaneously two or three nodes in ibid. Another improvement is the ability to compress the tree when some nodes become too sparse as a result of some deletions. Compressing the tree is done by a process that periodically scans the whole tree while running concurrently with the other operations. Alternatively, it is possible to initiate a compression process after each deletion that leaves a node less than half full. These compression processes may run concurrently with the other operations, and they scan only the nodes that have to be compressed. Each compression process has to lock simultaneously three nodes.