JISE


  [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24]


Journal of Information Science and Engineering, Vol. 27 No. 1, pp. 143-161


Making T-Trees Cache Conscious on Commodity Microprocessors

IG-HOON LEE1,3, SANG-GOO LEE1 AND JUNHO SHIM2,+
1School of Computer Science and Engineering 
Seoul National University 
Seoul, 151-742 Korea 
E-mail: {ihlee; sglee}@europa.snu.ac.kr 
2Department of Computer Science 
Sookmyung Women’s University 
Seoul, 140-742 Korea 
E-mail: jshim@sookmyung.ac.kr

    Recent research shows that the database performance can be significantly improved by the effective cache utilization of the conventional microprocessors. Researchers have modified existing index structures into ones optimized for CPU cache performance in main memory database environments. A Cache Sensitive B+-Tree 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 performance study which shows that our Cache Sensitive T-Trees can outperform the original T-Trees and Cache Sensitive B+-Trees on commodity microprocessors.

Keywords: main memory, index structure, cache, CST-tree, microprocessor, T-tree

  Retrieve PDF document (JISE_201101_10.pdf)