License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.05421.3
URN: urn:nbn:de:0030-drops-7632
Go to the corresponding Portal

Graefe, Goetz

B-tree indexes for high update rates

05421.GraefeGoetz.Paper.763.pdf (0.05 MB)


In some applications, data capture dominates query processing. For example, monitoring moving objects often requires more insertions and updates than queries. Data gathering using automated sensors often exhibits this imbalance. More generally, indexing streams apparently is considered an unsolved problem.
For those applications, B-tree indexes are reasonable choices if some trade-off decisions are tilted towards optimization of updates rather than of queries. This paper surveys techniques that let B-trees sustain very high update rates, up to multiple orders of magnitude higher than tradi-tional B-trees, at the expense of query processing performance. Perhaps not surprisingly, some of these techniques are reminiscent of those employed during index creation, index rebuild, etc., while others are derived from other well known technologies such as differential files and log-structured file systems.

BibTeX - Entry

  author =	{Graefe, Goetz},
  title =	{{B-tree indexes for high update rates}},
  booktitle =	{Data Always and Everywhere - Management of Mobile, Ubiquitous, Pervasive, and Sensor Data},
  pages =	{1--7},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{5421},
  editor =	{Gustavo Alonso and Christian S. Jensen and Bernhard Mitschang},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{},
  URN =		{urn:nbn:de:0030-drops-7632},
  doi =		{10.4230/DagSemProc.05421.3},
  annote =	{Keywords: B-tree, high update rates}

Keywords: B-tree, high update rates
Collection: 05421 - Data Always and Everywhere - Management of Mobile, Ubiquitous, Pervasive, and Sensor Data
Issue Date: 2006
Date of publication: 08.11.2006

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI