Apple Inc.
System and method for maintaining a multi-level data structure

Abstract:

Disclosed herein is a technique for merging a batch of intermediate trees into a base tree stored in a storage device. The batch of intermediate trees is stored in a storage device and each intermediate tree in the batch represents a tree that was previously moved from memory to the storage device. When the number of intermediate trees in the batch satisfies a threshold, the batch of intermediate trees is collectively merged into the base tree within the storage device.