B-tree structured data base using sparse array bit maps to store inverted lists

• US 4,606,002 A
• Filed: 08/17/1983
• Issued: 08/12/1986
• Est. Priority Date: 05/02/1983
• Status: Expired due to Term

• Current Assignee: Wang Laboratories Incorporated
• Original Assignee: Wang Laboratories Incorporated
• Inventors: Weiss, Andrew M., Waisman, Amnon
• Primary Examiner(s): Springborn, Harvey E.
• Assistant Examiner(s): WILLIAMS JR, ARCHIE E
• Application Number:
  US06/523,527
• Time in Patent Office: 1,091 Days
• Field of Search: 364/200, 364/900, 364/300, 340/347 DD
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/319 Inverted lists
• CPC Class Codes: G06F 16/902 using more than one table in sequence, i.e. systems with three or more layers
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

Variable length data (e.g., for hospital patients) is embedded in a B-tree type index structure of a relational data base. A logically related inverted B-tree index is used to access the original index. Access time, and storage space for the inverted lists, are decreased by data compression techniques and by encoding certain inverted list parameters in sparse array bit maps.

Claims

1. A method of storing and retrieving data in a data base system comprising the steps of:

providing a plurality of data tables, each data table including a plurality of records;

identifying each data table by assigning a unique record index value to each data table;

assigning each record within a data table a record serial number unique to that record within the data table;

dividing the record serial numbers of each data table into ranges, each range including a predetermined number of record serial numbers, and each range being assigned a consecutive range value;

dividing the records in each data table into a plurality of fields wherein each field within a data table is identified by a field index value and wherein each field within a data table contains data values of a selected type;

providing a plurality of inverted list tables, each inverted list table being associated with a respective one of the data tables, including the steps of;

creating a plurality of keys, each key being associated with a particular field and representing the occurance of a particular data value in that field;

providing one or more pointers associated with each key and representative of the record serial numbers of the records which contain the data value represented by the associated key, each pointer including a range value and a sparse array bit map representative of record serial numbers;

identifying the records in a selected data table having a specified data value stored in a selected field, including the steps of;

determining the key which is associated with the selected field and which represents the specified data value; and

searching the inverted list table associated with the selected data table to find the determined key; and

retrieving the data in the records represented by the pointers associated with the determined key.

2. The method of claim 1 wherein the step of providing one or more pointers which include a sparse array bit map includes the steps of:

determining a plurality of bottom level bytes, each byte having an equal plurality of bottom level bits, wherein the number of bottom level bits in said bottom level bytes is equal to the number of record serial numbers in each range and wherein each bottom level bit is associated with a respective one of said record serial numbers in each range;

encoding the presence of each record serial number within a range by setting the bottom level bit which is associated with each such record serial number;

determining a plurality of upper level bytes, including a top level byte and a plurality of bytes on one or more intermediate levels such that the total number of bits in the bytes in each level is equal to the number of bytes in the next lower level, each bit in each upper level byte being associated with a respective one of the bytes on the next lower level;

setting the bits in the upper level bytes whose associated byte in the next lower level contains at least one set bit; and

storing the bottom level and upper level bytes which contain one or more set bits.

3. The method of claim 2 wherein the step of determining a plurality of upper level bytes includes the steps of:

providing a top level byte having n bits; and

providing one intermediate level having n bytes including n² bits, whereby n³ record serial numbers within a range are represented by the sparse array.

4. The method of claim 2 wherein the step of providing a plurality of upper level bytes includes the step of providing a top level byte having eight bits and one intermediate level having eight bytes of eight bits each.

5. A method of storing data in a data base comprising the steps of:

providing a plurality of data tables, each data table including a plurality of records;

identifying each data table by assigning a unique record index variable to each data table;

assigning each record within a data table a record serial number unique to that record within the data table;

dividing the record serial numbers of each data table into ranges, each range including a predetermined number of record serial numbers, and each range being assigned a consecutive range value;

dividing the records in each data table into a plurality of fields wherein each field within a data table is identified by a field index variable and wherein each field within a data table contains data values of a selected type;

providing a plurality of inverted list tables equal in number to the number of data tables, each inverted list table being associated with a respective one of the data tables, including the steps of;

creating a plurality of keys, each key being associated with a particular field and representing the occurrance of a particular data value in the associated field; and

creating one or more pointers associated with each key and representative of the record serial numbers of the records which contain the data value represented by the associated key, each pointer including a range value representative of the occurrence in the inverted list table of one or more record serial numbers within the range and a sparse array bit map associated with each range value and representative of which record serial numbers within the associated range occur in the inverted list table;

providing within a first data table from among said plurality of data tables a designated field representative of a relationship between each of the records in the first data table and selected records from a second data table; and

storing said relationship in the data base by storing in the designated field data representative of the record serial numbers of said selected records from the second data table, said representative data including the range values of the record serial numbers of the selected records and a sparse array bit map associated with each range value and representative of the record serial numbers of the selected records.

6. A method of storing an inverted list of record serial numbers in a data base system including the steps of:

dividing the list of possible record serial numbers into ranges having a predetermined number of record serial numbers, each range being assigned a consecutive range value;

storing the range values for each range which contains at least one record serial number which occurs in the inverted list; and

encoding the position in each stored range of each record serial number in the inverted list by means of a sparse array bit map.

7. A data base system comprising:

a plurality of data tables, each data table having a unique record index value to identify each data table;

each data table including a plurality of records;

each record within a data table being identified by a record serial number unique to that record within the data table;

the records in each data table including a plurality of fields wherein each field within a data table is identified by a field index value and wherein each field within a data table contains data values of a selected type;

means for dividing the record serial numbers of each data table into ranges, each range including a predetermined number of record serial numbers, and each range being assigned a consecutive range value;

a plurality of inverted list tables, for providing a means of rapid access to selected data values, equal in number to the number of data tables, each inverted list table being associated with a respective one of the data tables, including

a plurality of keys, each key being associated with a particular field and representing the occurance of a particular data value in that field;

one or more pointers associated with each key and representative of the record serial numbers of the records which contain the data value represented by the associated key, each pointer including a range value and a sparse array bit map.

8. The data bas system of claim 7 wherein the data values are stored in the data tables in the form of a B-tree index having a plurality of levels and wherein the data values stored in the data base are stored within the B-tree as entries in the bottom level of the B-tree;

and wherein each data entry includes a key part and an associated data value, the key part including the record identifier value, the record serial number, and the field index value of the associated data value; and

wherein each data value in the data base is stored immediately following the associated key, whereby each key provides a logical address of its associated data value.

9. The data base system of claim 8 wherein the sparse array bit map includes:

a plurality of bottom level bytes, each byte having an equal plurality of bottom level bits, wherein the number of bottom level bits in said bottom level bytes is equal to the number of record serial numbers in each range and wherein each bottom level bit is associated with a respective one of said record serial numbers in each range;

wherein the data base system includes means for encoding the presence of each record serial number within a range by setting the bottom level bit which is associated with each such record serial number;

a plurality of upper level bytes, including a top level byte and a plurality of bytes on one or more intermediate levels such that the number of bits in the bytes in each level is equal to the number of bytes in the next lower level, each bit in each upper level byte being associated with a respective one of the bytes on the next lower level;

and where in the data base system further includes means for setting the bits in the upper level bytes whose associated byte in the next lower level contains at least one set bit; and

means for storing the sparse array bit map bytes which contain one or more set bytes.

10. The data base system of claim 9 wherein the plurality of upper level bytes include:

a top level byte having n bits; and

one intermediate level having n bytes including n² bits, whereby n³ record serial numbers within a range are represented by the sparse array.

11. The data base system of claim 9 wherein the plurality of upper level bytes include a top level byte having eight bits and one intermediate level having eight bytes of eight bits each.

12. A data base system comprising:

means for providing a plurality of data tables, each data table including a plurality of records;

means for identifying each data table by assigning a unique record index variable to each data table;

means for assigning each record within a data table a record serial number unique to that record within the data table;

means for dividing the record serial numbers of each data table into ranges, each range including a predetermined number of record serial numbers, and each range being assigned a consecutive range value;

means for dividing the records in each data table into a plurality of fields wherein each field within a data table is identified by a field index variable and wherein each field within a data table contains data values of a selected type;

means for providing a plurality of inverted list tables equal in number to the number of data tables, each inverted list table being associated with a respective one of the data tables, each inverted list table including;

a plurality of keys, each key being associated with a particular field and representing the occurance of a particular data value in the associated field; and

one or more pointers associated with each key and representative of the record serial numbers of the records which contain the data value represented by the associated key, each pointer including a range value representative of the occurance in the inverted list table of one or more record serial numbers within the range and a sparse array bit map associated with each range value and representative of which record serial numbers within the associated range occur in the inverted list table;

means for providing within a first data table from among said plurality of data tables a designated field representative of a relationship between each of the records in the first data table and selected records from a second data table; and

means for storing said relationship in the data base by storing in the designated field data representative of the record serial numbers of said selected records from the second data table, said representative data including the range values of the record serial numbers of the selected records and a sparse array bit map associated with each range value and representative of the record serial numbers of the selected records.

13. The data base system of claim 12, further comprising:

means for creating a B-tree having a plurality of levels and wherein the data values stored in the data base system are stored within the B-tree as data entries in the bottom level of the B-tree;

wherein each data entry includes a key part and an associated data value, the key part including the record identifier value, the record serial number, and the field index value of the associated data value; and

wherein each data value in the data base is stored immediately following the associated key, whereby each key provides a logical address of its associated data value.

14. A system for storing an inverted list representing record serial numbers in a data base system, comprising;

means for dividing the list of possible record serial numbers into ranges having a predetermined number of record serial numbers, each range being assigned a consecutive range value;

means for selecting the range values for each range which contains at least one record serial number which occurs in the inverted list; and

means for encoding the position in each selected range of each record serial number in the inverted list by means of a sparse array bit map.