Heap-based mechanism for efficient garbage collection block selection

摘要

N page counters are associated with N blocks in the flash subsystem. Each of the N page counters indicates a count of invalid pages in each corresponding block in the N blocks. A max heap structure is formed over the N page counters. At least one of the N page counters is updated each time the count changes. The max heap structure is updated each time the at least one of the N page counters is updated.;A maximum value is retrieved from a highest level of the max heap structure. The max heap structure is traversed down to lowest level using the maximum value at each level until reaching the lowest level. The lowest level corresponds to N page counters. One of the N blocks having associated page counter corresponds to the maximum value is identified as a candidate for block erasure.