Abstract
In main-memory resident index structures, secondary cache misses have a considerable effect on the performance of index structures. Recently, several main-memory resident index structures that consider cache have been proposed to reduce the impact of secondary cache misses. However, they still suffer from full secondary cache misses whenever visiting each level of index trees. In this paper, we propose a new index structure that minimizes the total amount of cache miss latency. The proposed index structure prefetches the grandchildren of a current node. The basic structure of the proposed index structure is from CSB+-Tree that uses the concept of the node group to increase fan-out. However the insert algorithm of the proposed index structure reduces the cost of a split significantly. Also, we show the superiority of our algorithm through performance evaluation.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Stefan Manegold, Peter A. Boncz, Martin L. Kersten.: Optimizing database architecture for the new bottleneck: memory access. In VLDB Journal 9(3) (2000) 231–246
Peter A. Boncz, Stefan Manegold, Martin L. Kersten.: Database Architecture Optimized for the New Bottleneck: Memory Access. In Proceedings of VLDB Conference (1999) 54–65
Shimin Chen, Phillip B. Gibbons, Todd C. Mowry.: Improving Index Performance through Prefetching. In Proceedings of ACM SIGMOD Conference (2001) 235–246
Jun Rao, Kenneth A. Ross.: Making B+-Trees Cache Conscious in Main Memory. In Proceedings of ACM SIGMOD Conference (2000) 475–486
Jun Rao, Kenneth A. Ross.: Cache Conscious Indexing for Decision-Support in Main Memory. In Proceedings of VLDB Conference (1999) 78–89
Philip Bohannon, Peter McIlroy, Rajeev Rastogi.: Main-Memory Index Structures with Fixed-Size Partial Keys. In Proceedings of ACM SIGMOD Conference (2001) 163–174
Intel Corporation.: IA-32 Intel□ Architecture Software Developer’s Manual. Intel Corporation Order Number 245470-007 (2002)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Hong, H.T., Pee, J.I., Song, S.I., Yoo, J.S. (2003). An Enhanced Main Memory Index Structure Employing the Level Prefetching Technique. In: Kumar, V., Gavrilova, M.L., Tan, C.J.K., L’Ecuyer, P. (eds) Computational Science and Its Applications — ICCSA 2003. ICCSA 2003. Lecture Notes in Computer Science, vol 2668. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44843-8_54
Download citation
DOI: https://doi.org/10.1007/3-540-44843-8_54
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-40161-2
Online ISBN: 978-3-540-44843-3
eBook Packages: Springer Book Archive