Unbalanced multiway trees improved by partial expansions (Q1203601)

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.