Asynchronous generic key/value database
Kyle R. Rose · DSpace@MIT (Massachusetts Institute of Technology) · 2000
B-Trees are ideal structures for building databases with fixed-size keys, and have been successfully extended in a variety of ways to accomodate specific key distributions; however, in the general case in which the key distribution either is unknown beforehand or is intentionally pathological, even the most time-honored B-Tree variants -- such as prefix-compressed trees -- provide sub-optimal performance; e.g., Sleepycat's poor performance on key distributions with many large keys. Insufficient generality in dealing with different key distributions makes most B-Tree variants unsuitable for general applications such as file systems. Furthermore, implementations of B-Trees are often limited to either preemptive or cooperative multithreaded operation with synchronous I/O primitives: the overhead caused by lock contention and multiple stacks makes this an insufficient solution for highly-parallel tasks. This thesis helps fill the void in these areas by introducing and analyzing the performance of a C++ implementation of the String B-Tree of Ferragina and Rossi that meets certain efficiency and exibility constraints -- such as operating within typical B+ Tree time bounds and providing good performance on long arbitrarily-distributed keys -- while requiring only asynchronous I/O primitives.