2017/12/13 by Brown, Trevor
#Data Structures and Algorithms (cs.DS) #Distributed #FOS: Computer and information sciences #Parallel #and Cluster Computing (cs.DC)
paper · doi:10.48550/arxiv.1712.05020
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(logb n), where b is the maximum node degree. Updates can be performed in O(log\frac b 2 n) amortized time. A relaxed balance version, which is well suited for concurrent implementation, is also presented.