Concurrency of operations on B-trees
Concurrency of operations on B-trees
复制标题
DOI：
10.1007/bf00263762
复制
发表时间：
1994-07
期刊：
影响因子：
0.6
通讯作者：
R. Bayer;M. Schkolnick
中科院分区：
文献类型：
--
作者：
R. Bayer;M. Schkolnick
B 树上的并发操作带来了确保每个操作都可以在不干扰其他用户同时执行的其他操作的情况下执行的问题。如果这些结构用于支持数据库系统的访问路径（如索引），那么这个问题可能会变得至关重要。在这种情况下，序列化对这些索引之一的访问可能会给整个系统带来不可接受的瓶颈。因此，需要一种能够确保每次访问的完整性，同时提供最大可能的并发程度的锁定协议。这些协议所要求的另一个特性是它们是无死锁的，因为解决死锁的成本可能很高。最近，有人质疑B树结构是否可以支持并发操作。在本文中，我们研究了 B 树的并发访问问题。我们提出了一个无死锁的解决方案，可以根据特定要求进行调整。提出了一种允许选择参数以满足这些要求的分析。这里提出的解决方案使用简单的锁定协议。因此，我们得出结论，B 树可以在多用户环境中有利地使用。
Concurrent operations onB-trees pose the problem of insuring that each operation can be carried out without interfering with other operations being performed simultaneously by other users. This problem can become critical if these structures are being used to support access paths, like indexes, to data base systems. In this case, serializing access to one of these indexes can create an unacceptable bottleneck for the entire system. Thus, there is a need for locking protocols that can assure integrity for each access while at the same time providing a maximum possible degree of concurrency. Another feature required from these protocols is that they be deadlock free, since the cost to resolve a deadlock may be high.Recently, there has been some questioning on whetherB-tree structures can support concurrent operations. In this paper, we examine the problem of concurrent access toB-trees. We present a deadlock free solution which can be tuned to specific requirements. An analysis is presented which allows the selection of parameters so as to satisfy these requirements.The solution presented here uses simple locking protocols. Thus, we conclude that B-trees can be used advantageously in a multi-user environment.