Previous [ 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 (January 2011)

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

Full Text (¥þ¤åÀÉ) Retrieve PDF document (201101_10.pdf)

Received April 29, 2009; revised August 17, 2009; accepted June 1, 2010.
Communicated by Pen-Chung Yew.
* This research was supported by the MKE (The Ministry of Knowledge Economy), Korea, under the ITRC (Information Technology Research Center) support program supervised by the NIPA (National IT Industry Promotion Agency) under Grant No. NIPA-2010-C1090-1031-0002.
+ Corresponding author. 3 Ig-Hoo Lee is the first author.