B-tree structured data base using sparse array bit maps to store inverted lists
First Claim
Patent Images
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.
10 Assignments
0 Petitions
Accused Products
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.
-
Citations
14 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. - View Dependent Claims (2, 3, 4)
-
-
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. - View Dependent Claims (8, 9, 10, 11)
-
-
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. - View Dependent Claims (13)
-
-
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.
-
Specification