×

Method and system for utilizing a hierarchical bitmap structure to provide a fast and reliable mechanism to represent large deleted data sets in relational databases

  • US 7,685,181 B2
  • Filed: 02/26/2007
  • Issued: 03/23/2010
  • Est. Priority Date: 02/26/2007
  • Status: Active Grant
First Claim
Patent Images

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.

View all claims
  • 3 Assignments
Timeline View
Assignment View
    ×
    ×