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

Abstract:

A current state of a dataset is represented by a mutable B+ tree, while each snapshot of the dataset is 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. Each B+ tree stores dataset records with a strong or a weak reference state; strong records are independent of any lower-layer record, while weak records are dependent on at least one lower-layer record. A snapshot deletion includes merging the snapshot's corresponding B+ tree with its highest neighbor B+ tree, including merging overlapping records based on their weak vs. strong reference state.