Expected behaviour of \(B^+\)-trees under random insertions

DOI10.1007/BF00289146zbMath0648.68024OpenAlexW2057082976MaRDI QIDQ1105354

Ricardo A. 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

performance measuresconcurrencyinsertion algorithmrandom insertionsoverflowB-trees\(B^+\)-treesfringe analysis

Mathematics Subject Classification ID

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

Related Items (6)

A uniform model for the storage utilization of B-tree-like structures ⋮ Bounded disorder: The effect of the index ⋮ Variance of storage requirements for B+-trees ⋮ Analysis of bounded disorder ⋮ \(B\)-trees with inserts and deletes: Why free-at-empty is better than merge-at-half ⋮ The SB-tree: An index-sequential structure for high-performance sequential access

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Space utilization and access path length in B-trees
• On random 2-3 trees
• Organization and maintenance of large ordered indexes
• The Analysis of an Improved Symmetric Binary B-tree Algorithm
• Dense multiway trees
• Kantorovich-Type Inequalities
• The theory of fringe analysis and its application to 23 trees and b-trees

This page was built for publication: Expected behaviour of \(B^+\)-trees under random insertions