Abstract: As the speed gap between main memory and modern processors continues to widen, memory access has be- come the main bottleneck of processing, so the cache behavior becomes more important for main memory database sys- tans (MMDI3s). Indexing technique is a key component of MMDBs. We proposed a cachcoptimized index-Prefetching I=tree (pI=tree) based on a novel CST-tree index, which applies prefetching to CST-tree to accelerate search opera- dons. p T-tree uses prefetching to effectively create wider nodes which arc larger than the natural data transfer size. These wider nodes reduce the height of the CST Tree, thereby decreasing the number of expensive misses when going from parent to child. The experimental performance study shows that our pT-Trees can provide better search perfor- mance than I3+-Trees,T-Trees,CST-Trees and Cache Sensitive I3+-Trees.

Key words: Index structure, p T-tree, Prefetching, Main memory database