Compressed data structure for a database

• US 20040148301A1
• Filed: 01/24/2003
• Published: 07/29/2004
• Est. Priority Date: 01/24/2003
• Status: Abandoned Application

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Company (HP Inc.)
• Inventors: Skillcorn, Steven, Douvikas, James G., McKay, Christopher W.T.
• Application Number:
  US10/350,326
• Publication Number:
  US 20040148301A1
• Time in Patent Office: Days
• US Class Current: 707/101
• CPC Class Codes: G06F 16/25 Integrating or interfacing systems involving database management systems
• CPC Class Codes: G06F 16/972 Access to data in other repository systems, e.g. legacy data or dynamic Web page generation

Abstract

A method of and computer-readable medium containing instructions for storing data in a compressed data structure. The data is stored in compressed form in one or more uniquely identified data pages along with configuration information stored in at least one configuration file. Index information is stored in one or more uniquely identified index pages. The index information includes pointers to data in the uniquely identified data pages and data from one or more fields of data from the uniquely identified data pages. The index information in the index pages is ordered based on the stored index information data from one or more fields of data from the data pages and the ordering basis is stored in configuration information in the one or more configuration files.

Claims

1. A method of storing data in a compressed data structure comprising:

storing data in compressed form in one or more uniquely identified data pages;

storing configuration information in compressed form in one or more configuration files;

storing index information in compressed form in one or more uniquely identified index pages, wherein the index information includes (1) pointers to data in the uniquely identified data pages and (2) data from one or more fields of data from the uniquely identified data pages;

ordering the index information in the one or more uniquely identified index pages based on (2) and storing the ordering basis in configuration information in the one or more configuration files.

2. The method of claim 1, wherein the configuration information comprises fieldname information, index information, smartsearch information, and version information.

3. The method of claim 1, further comprising the step of:

performing a seek using a searched for value and the index.

4. The method of claim 1, further comprising the step of:

storing index page information in compressed form in a page keys file.

5. The method of claim 4, wherein the index page information includes a number of keys, key name, number of index pages, and an index value of a last entry on each index page.

6. The method of claim 1, wherein the index information pointer is a compressed pointer.

7. The method of claim 6, wherein the compressed pointer identifies the data page and page offset of the referred to data.

8. The method of claim 2, wherein the smartsearch information includes at least one of a match property, a value property, an index property, a label property, a filter property, an order property, and a listOrder property.

9. A computer-readable medium comprising:

a data structure for a compressed database comprising;

one or more uniquely identified data pages;

one or more configuration files; and

one or more uniquely identified index pages, wherein the index pages includes (1) a pointer field for pointers to data in the one or more uniquely identified data pages and (2) a data field for data from one or more fields of data from the uniquely identified data pages;

at least one sequence of machine executable instructions in machine form, wherein execution of the instructions by a processor cause the processor to;

store data in the one or more uniquely identified data pages.

10. The medium of claim 9, further comprising instructions which, when executed by the processor, cause the processor to:

store index information in compressed form in the one or more uniquely identified index pages.

11. The medium of claim 10, wherein the instructions to store index information further comprise instructions which, when executed by the processor, cause the processor to:

order the index information in the one or more uniquely identified index pages based on the data field value.

12. The medium of claim 11, wherein the instructions to store index information further comprise instructions which, when executed by the processor, cause the processor to:

store the ordering basis in the one or more configuration files.

13. The medium of claim 9, wherein the one or more configuration files is structured to store fieldname information, index information, smartsearch information, and version information.

14. The medium of claim 9, further comprising instructions which, when executed by the processor, cause the processor to:

store index page information in compressed form in a page keys file.

15. The medium of claim 14, wherein the index page information includes a number of keys, key name, number of index pages, and an index value of a last entry on each index page.

16. The medium of claim 9, wherein the index information pointer is a compressed pointer.

17. The medium of claim 16, wherein the compressed pointer identifies the data page and page offset of the referred to data.

18. A method of searching for data in a compressed data structure, wherein the compressed data structure includes (1) data stored in compressed form in one or more uniquely identified data pages, (2) configuration information stored in compressed form in one or more configuration files, (3) index information stored in compressed form in one or more uniquely identified index pages, and (4) index page information stored in compressed form in a page keys file, wherein the index information includes pointers to data in the uniquely identified data pages and data from one or more fields of data from the uniquely identified data pages, and wherein the index page information include an index value of a last entry on each index page, the method comprising the following steps:

decompressing the index page information from the page keys file;

searching for a searched for key in the decompressed index page information;

if the searched for key is found, determining the index page having the searched for key and decompressing the determined index page;

searching for a searched for value in the decompressed index page;

if the searched for value is found, determining the data page having the searched for value and decompressing the determined data page; and

locating the data in the determined data page.

19. The method of claim 18, wherein the determined data page is determined using the index information from the value found in the determined index page.

20. The method of claim 19, wherein the determined data page is determined using the pointer to the data in the data pages corresponding to the value found in the determined index page.