Lecture Notes: Partially Persistent B-tree

Usually, a data structure is ephemeral, namely, once updated (with an insertion or a deletion), the structure has changed into a new version, such that its previous version (before the update) is lost permanently. In this lecture, we will discuss an interesting technique called partial persistence which allows us to preserve all the previous versions of a B-tree that has undergone a sequence of insertions and deletions. Formally, we consider the following problem. Let S be a set of elements from the real domain R. S is initially empty, and then modified by updates, each of which either inserts a new element into S or deletes an existing element from S. For convenience, we say that the i-th update happens at timestamp i. We denote by S(i) the version of S at timestamp i (after performing the i-th update). Given a timestamp t and a value q ∈ R, a timestamp predecessor query reports the predecessor of q in S(t), namely, the largest element in S(t) not exceeding q. The goal is to design a structure that consumes small space, can be updated efficiently along with S, and can answer timestamp predecessor queries efficiently. We will refer to the above as the persistent predecessor problem. Naively, one can solve this problem by creating a B-tree on every S(i) for all i = 1, 2,..., N, where N is the total number of updates. Each query can be trivially answered in O(logB N) I/Os. However, the space consumption and update overhead are terrible: all these B-trees can use O(N2/B) space, and creating a new B-tree for the next update may cost O(N/B) I/Os. On the other hand, notice that two B-trees at consecutive timestamps share considerable common information. Thus, a natural question to ask is whether we can leverages such sharing to reduce the space and update cost. Next, we will see that this is indeed possible. In fact, we will lower the space all the way to the optimal bound of O(N/B) (note that Ω(N/B) blocks are clearly needed to store N updates), and guarantee that each update be handled in O(logB N) I/Os. Even better, we are still able to answer a query in O(logB N) I/Os. Henceforth, we will assume that B ≥ 128 is a multiple of 16.