Patent ID: 7685181
Filing Date: 2010-03-23
Classification: G06F

Abstract:
1. A method for utilizing a hierarchical bitmap structure to represent deleted data in databases, comprising: allocating by a processor a first level bitmap having size equal to a register on a processor, each bit in the first level bitmap representing a plurality of blocks of data in a database; allocating by a processor a second level bitmap, said each bit in the first level bitmap corresponding to a plurality of bits in the second level bitmap; allocating by a processor one or more pointers corresponding to said plurality of bits in the second level bitmap, said one or more pointers being allocated to point to a sub bitmap generated after a data block is deleted but before the index corresponding to the data block is cleaned; each of the levels in the hierarchical bitmap structure being of size which fits in a corresponding level of memory hierarchy associated with a machine running the processor; and each bit in the first level bitmap representing x/n blocks of data, wherein x is total number of blocks and n is the size of the first level bitmap, and wherein m number of sub bitmaps can be generated, each sub bitmap size equal to round((x/m)+0.5) bits; allocating a temporary hierarchical bitmap structure corresponding to one or more local data deletes; and merging the temporary hierarchical bitmap structure with a master hierarchical bitmap structure.