Cache Sensitive T-tree Main Memory Index for Range Query Search
Sang-Jun Choi, Jong-Hak Lee · Journal of Korea Multimedia Society · 2009
Recently, advances in speed of the CPU have for out-paced advances in memory speed. Main-memory access is increasingly a performance bottleneck for main-memory database systems. To reduce memory access speed, cache memory have incorporated in the memory subsystem. However cache memories can reduce the memory speed only when the requested data is found in the cache. We propose a new cache sensitive T-tree index structure called as -tree for range query search. The -tree reduces the number of cache miss occurrences by loading the reduced internal nodes that do not have index entries. And it supports the sequential access of index entries for range query by connecting adjacent terminal nodes and internal index nodes. For performance evaluation, we have developed a cost model, and compared our -tree with existing CST-tree, that is the conventional cache sensitive T-tree, and -tree, that is conventional the range query search T -tree, by using the cost model. The results indicate that cache miss occurrence of -tree is decreased by 20~30% over that of CST-tree in a single value search, and it is decreased by 10~20% over that of -tree in a range query search.