Partially persistent B-trees with constant worst-case update time

We present two solutions for achieving a partially persistent B-tree with a worst case constant update time, in the case that the position of the update is given. The motivation for this work came from the observation that a known, general approach, which reduces the update cost of partially persistent data structures to a constant, has an inherent weakness concerning partially persistent B-trees, because it creates big nodes that cannot be retrieved from secondary memory in a constant time. Due to this, the I/O complexity of the resulting partially persistent B-tree is affected. Thus, we attack this specific problem, i.e. we do not develop a general approach for all partially persistent data structures. For our objectives, we add partial persistence to an ephemeral B-tree with constant worst case update time, by applying two known general methods, the fat-node and the node-copying method, that transform an ephemeral data structure into a partially persistent. The solution based on node-copying is asymptotically optimal.

Graphical abstractFigure optionsDownload full-size imageDownload as PowerPoint slideHighlights► We present partially persistent B-trees with O(1) worst-case update time. ► For adding partial persistence we use the fat-node and the node-copying method. ► The two resulting structures have different time complexities for searching a key. ► We only cover insertions and use standard techniques for incorporating deletions.