Cache-Conscious Index Structures for Main-Memory Databases
Vilho Raatikka · 2004
access method, cache consciousness, data locality, data structure, main-memory database The recent hardware evolution has widened the speed gap between main memory and the processor. As a consequence, in many cases memory access has become the main bottle-neck even in disk-based databases. The performance of indices is especially inuenced by cache misses; therefore new cache-conscious indices have been proposed. This the-sis surveys general methods for enhancing data locality of data structures and how those methods can be applied to database indices. The Cache-Conscious B-tree (CSB -tree) is revisited and formally dened. The worst-case space utilization of the CSB-tree is 25%. Improving the space utilization is one of the main contributions of this thesis. A new, remarkably less-memory-consuming variant of the CSB-tree called the Search-Intensive B-tree (SIB -tree) is presented. The most important cache-conscious index structures are also reviewed and a new, memory saving insertion algorithm is presented. Several methods improving the cache-consciousness of data structures are tested in isolation and as a part of the SIB-tree implementation. The search performance of the SIB-tree is compared with that of the B-tree and the compressed trie. The results show that hard-ware evolution may be disasterous to data structures with poor data locality such as tries. The cache-conscious search-tree implementation shows the best search performance in all tests.