B-slack Trees: Space Efficient B-Trees
Loading...
Date
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Springer International Publishing
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(log_b n), where b is the maximum node degree. Updates can be performed in O(log_{b/2} n) amortized time. A relaxed balance version, which is well suited for concurrent implementation, is also presented.
Description
Accepted author manuscript of the SWAT 2014 paper, 12 pages. This peer-reviewed manuscript is not the Version of Record and excludes publisher production changes. The published edition is copyright 2014 Springer International Publishing Switzerland. Final authenticated version: https://doi.org/10.1007/978-3-319-08404-6_11. Use is subject to Springer Nature’s accepted-manuscript terms: https://www.springernature.com/gp/open-research/policies/accepted-manuscript-terms. Also includes the expanded 19-page manuscript, arXiv:1712.05020v2 (2017-12-15), which is not separately peer reviewed. PDFs unchanged; no new Creative Commons licence assigned.