Concurrency Control and I/O-Optimality in Bulk Insertion

摘要

In a bulk update of a search tree a set of individual updates (insertions or deletions) is brought into the tree as a single transaction. In this paper, we present a bulk-insertion algorithm for the class of (a, b)-trees (including B~+-trees). The keys of the bulk to be inserted are divided into subsets, each of which contains keys with the same insertion place. From each of these sets, together with the keys already in the insertion place, an (a, b)-tree is constructed and substituted for the insertion place. The algorithm performs the rebalancing task in a novel manner minimizing the number of disk seeks required. The algorithm is designed to work in a concurrent environment where concurrent single-key actions can be present.