Modeling splits in file structures (Q1105353)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 4058831
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Modeling splits in file structures |
scientific article; zbMATH DE number 4058831 |
Statements
Modeling splits in file structures (English)
0 references
1989
0 references
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.
0 references
file structures
0 references
overflows
0 references
splitting
0 references
dynamic hashing
0 references
analysis of algorithms
0 references
B-trees
0 references
0.7622706890106201
0 references
0.7444801330566406
0 references
0.7444801330566406
0 references
0.7358800172805786
0 references
0.7292193174362183
0 references
