System and method for data space allocation using optimized bit representation

A method of managing the allocation of data values in the data space of a database having a plurality of allocation units for storing data, each allocation unit having an address, the allocation units being grouped into a plurality of blocks, each block including at least two allocation units, the method comprising the steps of:

• receiving a user request for access to the data space for storage of data values;
• providing first and second types of space allocation maps, each space allocation map having a predetermined number of bits, said first type space allocation map representing blocks of allocation units below a predetermined size, wherein one and only one bit in the first type space allocation map represents the allocation status of a corresponding one of the allocation units at a particular address, said space allocation map of the second type representing blocks of allocation units equal to, or greater than, the predetermined size, wherein the entire second type space allocation map represents the status and size of a single block of allocation units;
• examining each bit in the first type space allocation map to determine the allocation status of at least one allocation unit at each allocation unit address to identify a block of free allocation units;
• allocating the identified block of free allocation units for storage of data values if it is an appropriate size;
• and
• updating the allocation map to indicate the identified block of allocation units as being allocated.

A program storage device readable by a processor machine, tangibly embodying a program of instructions executable by the processor machine to perform method steps for managing storage allocation for storage of data values in a relational database having a plurality of allocation units for storing data, each allocation unit having an address, the allocation units being grouped into a plurality of blocks, each block including at least two allocation units, the method steps performed by the processor machine comprising the steps of:

• receiving a user request for access to the data space for storage of data values;
• providing first and second types of space allocation maps, each space allocation map having a predetermined number of bits, said first type space allocation map representing blocks of allocation units below a predetermined size, wherein one and only one bit in the first type space allocation map represents the allocation status of a corresponding one of the allocation units at a particular address, said space allocation map of the second type representing blocks of allocation units equal to, or greater than, the predetermined size, wherein the entire second type space allocation map represents the status and size of a single block of allocation units;
• examining each bit in the first type space allocation map to determine the allocation status of at least one allocation unit at each allocation unit address to identify a block of free allocation units;
• allocating the identified block of free allocation units for storage of data values if it is an appropriate size;
• and
• updating the allocation map to indicate the identified storage locations as being allocated.

A computer system comprising:

• a central processor unit;
• a memory unit;
• at least one storage device for the storage of data values of a data type corresponding to large data objects (LOBs), the storage device containing a LOB data space having LOB data values of a database;
• a space management system that permits a computer system user to generate requests for access to LOBs of a database, the system including:
• a plurality of allocation units for storing data, each having an address, the allocation units being grouped into a plurality of blocks, each block including at least two allocation units;
• first and second types of space allocation maps, each space allocation map having a predetermined number of bits, said first type space allocation map representing blocks of allocation units below a predetermined size, wherein one and only one bit in the first type space allocation map represents the allocation status of a corresponding one of the allocation units at a particular address;
• said space allocation map of the second type representing blocks of allocation units equal to, or greater than, the predetermined size, wherein the entire second type space allocation map represents the status and size of a single block of allocation units;
• and
• a controller unit for interpreting the space allocation map, the controller unit including means for executing requests to store information in said allocation units.