NDLI: Prefetching J$^{+}$-Tree: A Cache-Optimized Main Memory Database Index Structure

Content Provider	Springer Nature Link
Author	Luan, Hua Du, Xiao Yong Wang, Shan
Copyright Year	2009
Abstract	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 cache-optimized 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.
Starting Page	687
Ending Page	707
Page Count	21
File Format	PDF
ISSN	10009000
Journal	Journal of Computer Science and Technology
Volume Number	24
Issue Number	4
e-ISSN	18604749
Language	English
Publisher	Springer US
Publisher Date	2009-09-11
Publisher Place	Boston
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	index structure pJ$^{+}$-tree prefetching cache conscious main memory database Information Systems Applications (incl.Internet) Artificial Intelligence (incl. Robotics) Data Structures, Cryptology and Information Theory Theory of Computation Software Engineering Computer Science
Content Type	Text
Resource Type	Article
Subject	Theoretical Computer Science Computational Theory and Mathematics Computer Science Applications Software Hardware and Architecture

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Flash-Optimized B+-Tree

Cache-Conscious Data Cube Computation on a Modern Processor

Dynamic interval index structure in constraint database systems

A Unified Buffering Management with Set Divisible Cache for PCM Main Memory

Taxonomy of Data Prefetching for Multicore Processors

The Value of a Small Microkernel for Dreamy Memory and the RAMpage Memory Hierarchy

Dynamic data prefetching in home-based software DSMs

Next High Performance and Low Power Flash Memory Package Structure

Runtime Engine for Dynamic Profile Guided Stride Prefetching

Prefetching J$^{+}$-Tree: A Cache-Optimized Main Memory Database Index Structure

Similar Documents

Flash-Optimized B+-Tree

Cache-Conscious Data Cube Computation on a Modern Processor

Dynamic interval index structure in constraint database systems

A Unified Buffering Management with Set Divisible Cache for PCM Main Memory

Taxonomy of Data Prefetching for Multicore Processors

The Value of a Small Microkernel for Dreamy Memory and the RAMpage Memory Hierarchy

Dynamic data prefetching in home-based software DSMs

Next High Performance and Low Power Flash Memory Package Structure

Runtime Engine for Dynamic Profile Guided Stride Prefetching

Prefetching J$^{+}$-Tree: A Cache-Optimized Main Memory Database Index Structure