A cache-conscious version of the R-tree, called the CR-tree, is disclosed. To pack more entries in a node, the CR-tree compresses MBR keys, which occupy substantial part of the index data. It first represents the coordinates of an MBR key relatively to the lower left corner of its parent MBR to eliminate the leading 0's from the relative coordinate representation. Then, it quantizes the relative coordinates with a fixed number of bits to further cut off the trailing less significant bits. Consequently, the CR-tree becomes significantly wider and smaller than the ordinary R-tree. The experimental and analytical results show that the two-dimensional CR-tree performs search faster than the ordinary R-tree while maintaining similar update performance and consuming less memory space.