Utilization of B-trees with Inserts, Deletes and Modifies.

Theodore Johnson, Dennis Shasha: Utilization of B-trees with Inserts, Deletes and Modifies. PODS 1989: 235-246

@inproceedings{DBLP:conf/pods/JohnsonS89,
  author    = {Theodore Johnson and
               Dennis Shasha},
  title     = {Utilization of B-trees with Inserts, Deletes and Modifies},
  booktitle = {Proceedings of the Eighth ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, March 29-31, 1989, Philadelphia,
               Pennsylvania},
  publisher = {ACM Press},
  year      = {1989},
  isbn      = {0-89791-308-6},
  pages     = {235-246},
  ee        = {http://doi.acm.org/10.1145/73721.73745, db/conf/pods/JohnsonS89.html},
  crossref  = {DBLP:conf/pods/89},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

BibTeX

Abstract

The utilization of B-tree nodes determines the number of levels in the B-tree and hence its performance. Until now, the only analytical aid to the determination of a B-tree's utilization has been the analysis by Yao and related work. Yao showed that the utilization of B-tree nodes under pure inserts was 69%. We derive analytically and verify by simulation the utilization of B-tree nodes constructed from N inserts followed by M modifies (where M >> N), where each modify is a delete followed by an insert. Assuming that nodes only merge when they are empty (the technique used in most database management systems), we show that the utilization is 39% as M becomes large. We extend this model to a parametrized mixture of inserts and modifies. Surprisingly, if the modifies are mixed with just 10% inserts, then the utilization is over 62%. We also calculated the probability of splitting and merging. We derive a simple rule-of-thumb that accurately calculates the probability of splitting. We present two models for computing this utilization, the more accurate of which remembers items inserted and then deleted in a node - we call such items ghosts.

Copyright © 1989 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

Load The ACM SIGMOD Anthology, CDROM Edition, Volume 1-3, PODS '82-'98. and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
UNIX/LINUX/Mac: use mount point /pods8298/... or /cdrom/...

Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings. and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
UNIX/LINUX/Mac: use mount point /aDVD1/... or /cdrom/...

BibTeX

Printed Edition

Proceedings of the Eighth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, March 29-31, 1989, Philadelphia, Pennsylvania. ACM Press 1989, ISBN 0-89791-308-6
Contents BibTeX

Online Edition: ACM Digital Library

References

[Gupta, Srinivasan 86]: Gopal K. Gupta, B. Srinivasan: Approximate Storage Utilization of B-Trees. Inf. Process. Lett. 22(5): 243-246(1986) BibTeX
[Leung 84]: Clement H. C. Leung: Approximate Storage Utilisation of B-Trees: A Simple Derivation and Generalisations. Inf. Process. Lett. 19(4): 199-201(1984) BibTeX
[NAG]: ...
[Wright 85]: William E. Wright: Some Average Performance Measures for the B-Tree. Acta Inf. 21: 541-557(1985) BibTeX
[Yao 78]: Andrew Chi-Chih Yao: On Random 2-3 Trees. Acta Inf. 9: 159-170(1978) BibTeX

Referenced by

Vijayshankar Raman: Locality Preserving Dictionaries: Theory and Application to Clustering in Databases. PODS 1999: 337-345
Gabriel Matsliach, Oded Shmueli: A Combined Method for Maintaining Large Indices in Multiprocessor Multidisk Environments. IEEE Trans. Knowl. Data Eng. 6(3): 479-496(1994)
V. Srinivasan, Michael J. Carey: Performance of B+ Tree Concurrency Algorithms. VLDB J. 2(4): 361-406(1993)
Theodore Johnson, Dennis Shasha: The Performance of Current B-Tree Algorithms. ACM Trans. Database Syst. 18(1): 51-101(1993)
Theodore Johnson, Padmashree Krishna: Lazy Updates for Distributed Search Structure. SIGMOD Conference 1993: 337-346
Anatoly P. Pinchuk, Konstantin V. Shvachko: Maintaining Dictionaries: Space-Saving Modifications of B-Trees. ICDT 1992: 421-435
V. Srinivasan, Michael J. Carey: Performance of B-Tree Concurrency Algorithms. SIGMOD Conference 1991: 416-425
Theodore Johnson, Dennis Shasha: A Framework for the Performance Analysis of Concurrent B-tree Algorithms. PODS 1990: 273-287
Ricardo A. Baeza-Yates: An Adaptive Overflow Technique for B-trees. EDBT 1990: 16-28

BibTeX

ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]