Optimizing multidimensional index trees for main memory access

摘要: Recent studies have shown that cache-conscious indexes such as the CSB+-tree outperform conventional main memory T-tree. The key idea of these is to eliminate most child pointers from a node increase fanout tree. When size chosen in order cache block size, this pointer elimination effectively reduces tree height, and thus improves behavior index. However, cannot be directly applied multidimensional index structures R-tree, where key, typically, an MBR (minimum bounding rectangle), much larger than pointer. Simple four-byte does not help pack more entries node.This paper proposes version R-tree called CR-tree. To node, CR-tree compresses keys, which occupy almost 80% data two-dimensional case. It first represents coordinates relatively lower left corner its parent leading O's relative coordinate representation. Then, it quantizes with fixed number bits further cut off trailing less significant bits. Consequently, becomes significantly wider smaller ordinary R-tree. Our experimental analytical study shows performs search up 2.5 times faster while maintaining similar update performance consuming about 60% space.