Concurrency in B-trees and tries : search and insert

Multiuser database systems require concurrency control in order to perform correctly. B-trees have become the standard data structure for storing indices that aid in data retrieval and there have been many algorithms published to enable concurrent operations for B-trees. Tries are another data structure useful for storing index data, particularly for text and spatial databases. Significant data compression can be achieved by using a trie to store index values. However, there have been no algorithms published to support concurrent trie operations.We present algorithms that enable concurrent searches and inserts for tries with pointerless representation. We also measure the performance of our algorithms and compare with that of the best B-tree algorithms. In order to measure trie concurrency, we survey a number of studies that have been made for B-tree concurrency. Using these published studies, we build a simulation model to measure the concurrency of our algorithms