A Tree for All Seasons

The performance of in-memory databases is significantly affected by the number of data blocks fetched from memory into the processor-resident cache. In recent years, various tree-based indexes have been proposed for main memory databases. A common assumption in the analysis of these indexes is that...

Full description

Saved in:
Bibliographic Details
Main Authors: Mihaila, G., Stanoi, I.
Format: Conference Proceeding
Language:English
Subjects:
Application software
Clocks
Costs
Data structures
Database systems
Indexes
Memory management
Query processing
Random access memory
Temperature dependence
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The performance of in-memory databases is significantly affected by the number of data blocks fetched from memory into the processor-resident cache. In recent years, various tree-based indexes have been proposed for main memory databases. A common assumption in the analysis of these indexes is that there is no data in the cache that can be reused between key lookups, i.e. the system has a cold cache for each lookup. In practice, though, the "temperature" of the cache is strongly dependent on the application. For example, a warm cache is typical for OLTP applications that query the same index over and over with little computation in between lookups. In this paper, we present a comparative study of the cache behavior of various B+-tree-based indexes which shows that none of them performs best in all cases. Also, we propose a lightweight technique for improving the cache behavior of any B+-tree based index that performs best in all settings
ISSN:1098-8068
DOI:10.1109/IDEAS.2006.6