Semantically consistent schedules for efficient and concurrent B-tree restructuring

A concurrent B-tree algorithm can achieve more parallelism than a standard concurrency control method. The author presents a semantically based method for B-tree restructuring which allows efficient and concurrent traversals and fetches. The concurrent operations compare favorably with earlier solutions because they avoid wasted input/output (I/O). In addition, the concurrent B-tree algorithms considerably reduce the need to repeatedly traverse the tree in order to recover from the effect of in-progress restructuring. The method increases the performance of a high-volume database management system