An efficient B+-tree design for main-memory database systems with strong access locality
Journal
Information Sciences
Journal Volume
232
Pages
325-345
Date Issued
2013
Author(s)
Abstract
This paper is motivated by the strong demands of many main-memory database applications with strong locality in data access, such as front-end logistical systems. We propose to adopt an auxiliary-tree approach with an tree-merging algorithm to efficiently handle bursty data insertions with keys in a small range and avoid significant overheads in tree rebalancing. A range-based deletion algorithm is then proposed to process data deletions with strong access locality in a batch fashion. The capability of the proposed approach is evaluated by a series of experiments with a wide range of workloads and a variety of locality patterns, where different tree index structures are compared in terms of the performance and memory space requirements. © 2013 Elsevier Inc. All rights reserved.
Type
journal article