Microsoft Corporation
MANAGING SNAPSHOTTING OF A DATASET USING AN ORDERED SET OF B+ TREES

Abstract:

A dataset is represented by an ordered set of B+ trees, with each snapshot of the dataset being represented by an immutable B+ tree. An ordering of B+ trees in the ordered set logically arranges those B+ trees into layers, with the mutable B+ tree representing the current state of the dataset being logically arranged as an upper layer, and with immutable B+ trees representing snapshots of the dataset being progressively arranged as lower layers with the oldest snapshot being a lowest layer. A snapshot deletion includes merging the snapshot's corresponding B+ tree with its highest neighbor B+ tree.