B-slack trees: space efficient B-trees

DOI10.1007/978-3-319-08404-6_11MaRDI QIDQ3188888zbMATH OpenOpenAlexFDO

Authors Trevor Brown

Publication date 2 September 2014

Published in Algorithm Theory – SWAT 2014 (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1712.05020

Mathematics Subject Classification ID

Data structures (68P05)

Abstract: B-slack trees, a subclass of B-trees that have substantially better worst-case space complexity, are introduced. They store $n$ keys in height $O(lo{g}_{b}n)$, where $b$ is the maximum node degree. Updates can be performed in $O(lo{g}_{fracb2}n)$ amortized time. A relaxed balance version, which is well suited for concurrent implementation, is also presented.

Recommendations

• EFFICIENT REBALANCING OF B-TREES WITH RELAXED BALANCE
• scientific article; zbMATH DE number 1830753
• Space saving generalization of \(B\)-trees with \(2/3\) utilization
• Variants of (a,b)-trees with relaxed balance
• Relaxed multi-way trees with group updates.

Cited in

(2)

• \(B\)-trees with lazy parent split
• Space saving generalization of \(B\)-trees with \(2/3\) utilization

This page was built for publication: B-slack trees: space efficient B-trees

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