In recent years, as the performance of central process unit (CPU) is improved greatly and the speed gap between CPU and memory becomes larger, in many cases memory access has become the main bottleneck of processing. Cache is a kind of small-amount and high-speed static RAM memory, residing between CPU and memory. Cache supplies the processor with the most frequently requested data and instructions so that it can reduce the wait time of CPU. The higher Cache hit ratio is, the greater performance CPU can get. The Cache hit ratio has important influence upon the performance of index structures of database, especially main memory database. Accordingly, it is significant to improve the Cache hit ratio and reduce the data exchange times between CPU and memory so that it can provide efficient support for real-time application while processing in main memory database.This thesis surveys many cache-conscious methods and analyses current MMDB indices. We propose an indexing structure called "Cache Sensitive T-Tree" (CST-Tree) for efficient processing of real time applications under main memory database systems. The size of a T-Tree's node is generally larger than that of a cache line so that it can not be hit completely by Cache once. CST-Tree is a variant of T-Tree modified according to the Cache-Conscious structure definition. Based on the frequency of access, a T-Tree's node is divided into "hot" segment and "cold" segment. The "hot" segment is kept inside the node while the "cold" segment is kept outside. Therefore, CST-Tree can obtain more cache hit ratio without using extra space because of it's node size is always smaller than that of a cache line. The performance test results indicate that CST-Tree can provide better overall performance than T-Tree in main memory database under most circumstances. When comparing with another efficient MMDB index, CSB+-tree, CST-tree performs almost as well as the best form of CSB+-tree, FULL-CSB+-Tree and saves more space than FULL-CSB+-Tree at the same time. |