Modeling splits in file structures

Summary We analyze the expected behaviour of file structures where splits are used to handle overflows. Two cases are analyzed. The first model is of a file with an index on top of the data structure. We analyze the effect of unbalanced splits, and the effect of splitting in more than two buckets. T... Ausführliche Beschreibung

1. Person: Baeza-Yates, Ricardo A.
Quelle: in Acta informatica Vol. 26 (1989), p. 349-362
Weitere Artikel
Format: Online-Artikel
Sprache: English
Veröffentlicht: 1989
Beschreibung: Online-Ressource
Online Zugang: Online
Volltext
Tags: Hinzufügen
Keine Tags. Fügen Sie den ersten Tag hinzu!
Anmerkung: Copyright: Copyright 1989 Springer-Verlag
Zusammenfassung: Summary We analyze the expected behaviour of file structures where splits are used to handle overflows. Two cases are analyzed. The first model is of a file with an index on top of the data structure. We analyze the effect of unbalanced splits, and the effect of splitting in more than two buckets. The second model is of an ideal hash file, in which the probability of insertion remains the same for every bucket, regardless of how many times the bucket has been split. The result is an upper bound in any dynamic hashing method that uses splitting and does not allow overflow records. In both cases, the effect of using partial expansions is included.
ISSN: 1432-0525

Ähnliche Einträge

Keine ähnlichen Titel gefunden

Privacy Notice Ask a Librarian New Acquisitions