Unbalanced multiway trees improved by partial expansions
type: Item
instance of: scholarly article
title: Unbalanced multiway trees improved by partial expansions
zbMATH Open document ID: 0769.68016
DOI: 10.1007/BF01193577
author: Ricardo Baeza-Yates
author: Walter Cunto
published in: Acta Informatica
publication date: 1993-02-16T00:00:00Z
review text: Unbalanced multiway trees are generally impractical external data structures because of their poor space performance. In order to avoid this handicap, we have adapted the technique of partial expansions to these trees. Compared to partially expanded \(B^ +\)-trees in terms of average performance, the method proposed is faster, has more compact indices, and shows the same almost-optimal asymptotic space performance at the data bucket level.
Mathematics Subject Classification ID: 68P05
zbMATH DE Number: 120176
zbMATH Keywords: unbalanced multiway trees
zbMATH Keywords: external data structures
zbMATH Keywords: partial expansions
zbMATH Keywords: almost-optimal asymptotic space performance
MaRDI profile type: Publication
cites work: Q3331506
cites work: Organization and maintenance of large ordered indexes
cites work: Transforming unbalanced multiway trees into a practical external data structure
cites work: The theory of fringe analysis and its application to 23 trees and b-trees
cites work: Q4057549
cites work: The analysis of a fringe heuristic for binary search trees
cites work: On random 2-3 trees
full work available at URL: https://doi.org/10.1007/bf01193577
OpenAlex ID: W1989488431
description: scientific article; zbMATH DE number 120176