© Springer-Verlag Berlin Heidelberg 2007 CST-Trees: Cache Sensitive T-Trees

Abstract. Researchers have modified existing index structures into ones opti-mized for CPU cache performance in main memory database environments. A Cache Sensitive B+-Tree is one of them. It is designed to minimize the impact of cache misses for B+-Trees and it has been known to be more effective than other types of main memory index structure including T-Trees. In this paper, we introduce a Cache Sensitive T-Tree (CST-Tree) and show how T-Trees can also be redesigned to be cache sensitive. We present an experimental perform-ance study which shows that our Cache Sensitive T-Trees can outperform the original T-Trees and Cache Sensitive B+-Trees on average 65 percent and 17 percent, respectively.