Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2000-06-05
2003-12-02
Vu, Kim (Department: 2172)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C711S112000, C711S145000, C711S154000, C711S156000, C711S170000, C711S211000
Reexamination Certificate
active
06658437
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates generally to space management systems and, more particularly to bit representations of the allocation status of data space in relational database systems.
2. Description of the Related Art
Computer systems have significantly improved in their ability to store and access large quantities of data. Advances in computer data space management systems have made it possible to manipulate increasingly large blocks of data stored in data storage devices.
One computer data space management technique, known as the binary buddy system, is a high performance space management system that can operate on blocks of data of a wide range of sizes, allocating and freeing the blocks with great efficiency. The binary buddy system manages blocks, or memory segments, whose sizes correspond to powers of two. In the binary buddy system, the data space in which data values are contained includes a buddy space that has a size that is a power of two units large. For example, a buddy space might comprise four megabytes (4 MB) of storage locations, which corresponds to 4×1,024,000 bytes or 2
12
bytes. The entire buddy space is divided into segments (known as buddy segments). In this example, if the buddy space were divided into the largest possible segments there would be two segments, each 2 MB in size. Each of these two buddy segments could be further subdivided into two smaller buddy segments—and so on until a minimal buddy segment size is reached. That is, the buddy space can be comprised of multiple buddy segments, all of different sizes, all being powers of two. The minimal segment size that the system can allocate might be, for example, one kilobyte (1 KB) of data storage locations.
When a request to store a data value of a certain size is received by the binary buddy system, a space allocator of the buddy system allocates a buddy segment for the data value. In attempting to allocate a buddy segment, the space allocator either finds a segment of the correct power-of-two size, or finds a larger segment (starting with up to 4 MB in the above example) and splits it down repeatedly to the desired size. Thus, buddy segments might be allocated in storage blocks of size 1 KB, 2 KB, 4 KB, 8 KB, . . . 512 KB, 1 MB, and so on, up to the buddy space size limit of the computer system in which the database is installed. When a data value is removed from a buddy segment, the space allocator automatically joins that segment with its buddy, if the buddy is free. Similarly, that resulting larger segment is joined with its buddy if the buddy is free—and so on until the maximum possible size segment again is reached.
Implementations of the buddy system space management technique generally have two main components: the space allocation information and the data space itself. The space allocation information includes the status of the buddy spaces with respect to subdivisions into buddy segments and the assignment of the buddy segments to data values. The computer system uses the allocation information to manage the allocation and freeing of storage locations for data values. When used to manage a computer memory space, the space allocation information is represented as a large main-memory data structure. When used to manage large amounts of disk storage, the space allocation information is represented as disk-resident data structures. A binary buddy space management system which overcomes the single disk page limitation is described in U.S. Pat. No. 5,732,402 entitled, “System and Method for Data Space Management Using Buddy system Space Allocation”, the entire contents of which are incorporated herein by reference. This patent describes a hierarchical relational database management system which stores and retrieves large data objects (LOBs) from database storage that utilizes a data manager that maintains LOB data space allocation with two types of allocation pages. The first type of allocation page, called a regular buddy space (RBS) page, controls distinct buddy spaces comprising equal-size areas of the LOB data space in which LOB buddy segments are stored. The second type of allocation page, called a super buddy space (SBS) page, controls the RBS pages.
The binary buddy space management system allows much more space to be tracked from a single allocation space because a single SBS page can control numerous RBS allocation pages. For example, in an embodiment disclosed in U.S. Pat. No. 5,732,402, a single SBS page can manage a 64-gigabyte sized data space, thus, only a single disk access is needed to search the 64-gigabyte space and allocate any SBS-size segment. In this way the number of access operations necessary to store LOBs is reduced. Also, the SBS page structure is a compact representation that only requires taco bits of allocation space per minimum disk block size and hence does not take excessive main memory to track very large (terabytes) of disk space. Moreover, the SBS page structure can be integrated with an existing buddy space allocation structure without restructuring the data space.
There are limitations on the efficiency of the above-described space allocation system due to the amount of space required for allocation information. If less space were required for allocation information, more allocation information could be searched per block of allocation data retrieved from disk. As a result, searches could go faster and less memory would be required. Also, the space presently used for allocation could be used for storing other kinds of control information.
From the discussion above, it should be apparent that there is a need for a data space management system that requires less space to store allocation information in order to increase the increase the speed of disk access operations in allocating, storing, and retrieving data values, and also to free up space for use in other control functions.
SUMMARY OF THE INVENTION
In accordance with the invention a space, management system stores and retrieves large data objects (LOBs) from a computer system storage device. The computer system storage device contains a LOB data space having LOB data values. The space management system permits a computer system user to generate requests for access to LOBs of a database and includes a plurality of allocation units for storing data. each having, an address. The allocation units are grouped into a plurality of blocks, each block including at least two allocation units. The space management system includes first and second types of space allocation maps, where each space allocation map has a predetermined number of bits. The first type space allocation map represents blocks of allocation units below a predetermined size. Each bit in the first type space allocation map represents the allocation status of a corresponding one of the allocation units at a particular address. The space allocation map of the second type represents blocks of allocation units equal to. or greater than. the predetermined size. The entire second type space allocation map represents the status and size of a single block of allocation units. The space management system also includes a controller unit for interpreting the space allocation map and for executing requests to store or retrieve information in the allocation units. The use of an efficient space allocation map allows faster data access and frees up space for use in other control functions.
REFERENCES:
patent: 5490274 (1996-02-01), Zbikowski et al.
patent: 5732402 (1998-03-01), Lehman
Publication: “The Starburst Long Field Manager” Report RJ-6899. pps. 1-14. IBM Almaden Research Center. San Jose, CA. Published Jun. 1989.
Pham Hung
Rogitz John L.
Vu Kim
LandOfFree
System and method for data space allocation using optimized... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for data space allocation using optimized..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for data space allocation using optimized... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3121045