Efficient deletion of leaf node items within tree data structure

摘要

Leaf node items within a tree data structure are efficiently deleted. A leaf node item of a leaf node of the tree data structure is marked for deletion. The leaf node is marked as containing leaf node items that have been marked for deletion. A flag for a region encompassing the leaf node within a linear representation of the tree data structure is set. The linear representation of the tree data structure has a number of regions, each of which encompass one or more of the leaf nodes and that have a corresponding flag. Periodically, the tree data structure is cleaned. Each region of the linear representation for which the corresponding flag is set is scanned for leaf nodes that have been marked as containing leaf node items that have been marked for deletion. Each such leaf node item that within each such leaf node is found is deleted.