As the speed gap between main memory and modern processors continues to widen, the cache behavior becomes more important for main memory database systems （MMDBs）. Indexing technique is a key component of MMDBs. Unfo...As the speed gap between main memory and modern processors continues to widen, the cache behavior becomes more important for main memory database systems （MMDBs）. Indexing technique is a key component of MMDBs. Unfortunately, the predominant indexes -B^＋-trees and T-trees -- have been shown to utilize cache poorly, which triggers the development of many cache-conscious indexes, such as CSB^＋-trees and pB^＋-trees. Most of these cache-conscious indexes are variants of conventional B^＋-trees, and have better cache performance than B^＋-trees. In this paper, we develop a novel J^＋-tree index, inspired by the Judy structure which is an associative array data structure, and propose a more cacheoptimized index -- Prefetching J^＋-tree （pJ^＋-tree）, which applies prefetching to J^＋-tree to accelerate range scan operations. The J^＋-tree stores all the keys in its leaf nodes and keeps the reference values of leaf nodes in a Judy structure, which makes J^＋-tree not only hold the advantages of Judy （such as fast single value search） but also outperform it in other aspects. For example, J^＋-trees can achieve better performance on range queries than Judy. The pJ^＋-tree index exploits prefetching techniques to further improve the cache behavior of J^＋-trees and yields a speedup of 2.0 on range scans. Compared with B^＋-trees, CSB^＋-trees, pB^＋-trees and T-trees, our extensive experimental Study shows that pJ^＋-trees can provide better performance on both time （search, scan, update） and space aspects.展开更多
With the development of wireless communications and positioning technologies, tracking the positions of moving objects has increased necessary. This paper proposes a Cache-Conscious TPR -Link tree called CTPR Link tre...With the development of wireless communications and positioning technologies, tracking the positions of moving objects has increased necessary. This paper proposes a Cache-Conscious TPR -Link tree called CTPR Link tree which store in main memory. To satisfy continuous movement, the QRMBR definition is modified. The compression leads to the reduction of the tree height, which improves the cache behavior of the index and reduces the memory access time. In order to achieve high concurrency control, optimistic dynamic versioning and sibling-link scheme is presented, which not only enable read-only transactions not to fail with latch-free but also reduce cache misses during index updates.展开更多
基金supported by a grant from HP Lab China,and the National Natural Science Foundation of China under Grant Nos.60496325 and 60573092
文摘As the speed gap between main memory and modern processors continues to widen, the cache behavior becomes more important for main memory database systems （MMDBs）. Indexing technique is a key component of MMDBs. Unfortunately, the predominant indexes -B^＋-trees and T-trees -- have been shown to utilize cache poorly, which triggers the development of many cache-conscious indexes, such as CSB^＋-trees and pB^＋-trees. Most of these cache-conscious indexes are variants of conventional B^＋-trees, and have better cache performance than B^＋-trees. In this paper, we develop a novel J^＋-tree index, inspired by the Judy structure which is an associative array data structure, and propose a more cacheoptimized index -- Prefetching J^＋-tree （pJ^＋-tree）, which applies prefetching to J^＋-tree to accelerate range scan operations. The J^＋-tree stores all the keys in its leaf nodes and keeps the reference values of leaf nodes in a Judy structure, which makes J^＋-tree not only hold the advantages of Judy （such as fast single value search） but also outperform it in other aspects. For example, J^＋-trees can achieve better performance on range queries than Judy. The pJ^＋-tree index exploits prefetching techniques to further improve the cache behavior of J^＋-trees and yields a speedup of 2.0 on range scans. Compared with B^＋-trees, CSB^＋-trees, pB^＋-trees and T-trees, our extensive experimental Study shows that pJ^＋-trees can provide better performance on both time （search, scan, update） and space aspects.
基金This workis supported by Ministry of Information and Communication( MIC) Korea,under the Information Technology Research Center(ITRC) +1 种基金sup-port programsupervised by the Institute of Informationtechnology Assessment(IITA) Sino-Korea GIS Research Center ,China.
文摘With the development of wireless communications and positioning technologies, tracking the positions of moving objects has increased necessary. This paper proposes a Cache-Conscious TPR -Link tree called CTPR Link tree which store in main memory. To satisfy continuous movement, the QRMBR definition is modified. The compression leads to the reduction of the tree height, which improves the cache behavior of the index and reduces the memory access time. In order to achieve high concurrency control, optimistic dynamic versioning and sibling-link scheme is presented, which not only enable read-only transactions not to fail with latch-free but also reduce cache misses during index updates.
