T-treap and cache performance of indexing data structures. http://www.cs.berkeley.edu/ ravenben/research/CS252/252Paper.pdf

As memory becomes cheaper and larger in capacity, more and more databases are being stored entirely in main memory. Furthermore, there is an increasing latency gap between on-chip caches and main memory. As a result, how main memory indexing data structures perform, especially with respect to local cache, is becoming an increasingly important factor in database performance. One of these data structures is the treap, a binary tree using a Cartesian key pair to provide probabilistic self-balancing properties. The Cartesian keys in treaps have a great potential to be exploited for faster memory accesses. In this paper, we describe efforts to extend the treap to a multivalue node data structure called the T-treap, in an effort to improve the pointer to data ratio and overall performance. We study several indexing data structures as well as our new data structure in a simulation environment. We derive some general results of the T-treap and also show that the relative performance of cache-conscious indexing structures is increasing with memory latency. In addition, we analyze the T-treap results, and propose optimizations to the T-treap. Finally, we show that top-down algorithms for maintaining these structures reduce the total instruction count, leading to a modest improvement in execution time over the corresponding bottom-up algorithms. 1