Modeling splits in file structures

DOI10.1007/BF00289146MaRDI QIDQ1105353zbMATH OpenOpenAlexFDO

Authors Ricardo Baeza-Yates

Publication date 1989

Published in Acta Informatica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf00289146

zbMATH Keywords

analysis of algorithmsB-treesdynamic hashingfile structuresoverflowssplitting

Mathematics Subject Classification ID

Data structures (68P05) Searching and sorting (68P10)

Review text

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 wich 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.

Recommendations

• Performance analysis of file organizations that use multi-bucket data leaves
• Linear-density hashing with dynamic overflow sharing
• File organizations with shared overflow blocks for variable length objects
• Single access hashing with overflow separators for dynamic files
• A simple bounded disorder file organization with good performance

Cites work

• Dense multiway trees
• scientific article; zbMATH DE number 3863589 (Why is no real title available?)
• scientific article; zbMATH DE number 3653523 (Why is no real title available?)
• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 3303654 (Why is no real title available?)
• Kantorovich-Type Inequalities
• On random 2-3 trees
• Organization and maintenance of large ordered indexes
• Space utilization and access path length in B-trees
• The Analysis of an Improved Symmetric Binary B-tree Algorithm
• The theory of fringe analysis and its application to 23 trees and b-trees

Cited in

(6)

• Bounded disorder: The effect of the index
• Fast string matching in stationary ergodic sources
• The average height of a node in the BANG abstract directory tree
• scientific article; zbMATH DE number 3883590 (Why is no real title available?)
• Analysis of bounded disorder
• Performance analysis of file organizations that use multi-bucket data leaves

This page was built for publication: Modeling splits in file structures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1105353)