| 摘要 |
PURPOSE: High speed tree flattening for a system with an NVM(Non-Volatile Memory) is provided to reduce the number of data fragments in the NVM, thereby flattening a part of tree. CONSTITUTION: It is detected whether or not the amount of memory used for a tree is less than a threshold value(804). Sliding windows are moved across the tree(806). When the sliding windows are moved across the tree, minimal spans are maintained corresponding to the sliding windows(808). Completion of movement that the sliding windows intersect the tree is determined(810). A group of entries of the tree is selected based on comparison between the minimal spans(812). [Reference numerals] (802) Start; (804) Detecting than an amount of memory currently available for a tree is below a predetermined threshold, where the tree store a logical-physical mapping between a logical space and physical addresses of an NVM; (806) Moving at least two sliding windows across the tree; (808) Maintaining at least two minimum spans corresponding to the at least two sliding windows as the at least two sliding windows move across the tree; (810) Determining that the at least two sliding window have finished moving across the tree; (812) Selecting to flatten a set of entries of the tree based at least in part on a comparison between the at least two minimum spans; (814) End |
