Two Access Methods Using Compact Binary Trees

W. de Jonge, A.S. Tanenbaum, R.P. van de Riet

Research output: Contribution to JournalArticleAcademicpeer-review

96 Downloads (Pure)

Abstract

It is shown how a highly compact representation of binary trees can be used as the basis of two access methods for dynamic files, called BDS-trees and S-trees, respectively. Both these methods preserve key-order and offer easy and efficient sequential access. They are different in the way the compact binary trees are used for searching. With a BDS-tree the search is a digital search using binary digits. Although the S-tree search is performed on a bit-by-bit basis as well, it will appear to be slightly different. Actually, with S-trees the compact binary trees are used to represent separators at low storage costs. As a result, the fan-out, and thus performance, of a B-tree can beimproved by using within each index page an S-tree for representing separators efficiently. Copyright © 1987 by the Institute of Electrical and Electronics Engineers, Inc.
Original languageEnglish
Pages (from-to)799-810
Number of pages12
JournalIEEE Transactions on Software Engineering
VolumeSE-13
Issue number7
DOIs
Publication statusPublished - 1987

Keywords

  • Access method
  • B-tree
  • file
  • searching
  • tree

Fingerprint

Dive into the research topics of 'Two Access Methods Using Compact Binary Trees'. Together they form a unique fingerprint.

Cite this