Batch Updates and Concurrency in B-trees

摘要

In many applications it is important to be able to insert (or delete) keys into aB-tree as a batch, instead of inserting them one by one. Moreover, it may be necessary to search the B-tree concurrently with the batch update. An example of this is a text database system supporting a newspaper house: all words (keys) of each article obtained from a news agency should be inserted at once, and, at the same time, searches should be allowed as efficiently as possible. We have designed two solutions to the problem of concurrent batch update. The first solution--implemented in our commercial text database system--optimizes the speed of the batch update, and the second solution optimizes the average search time during the batch update.