Guide word paged hash table

1. A method for accessing data comprising:

storing, on disk, a plurality of pages, each page comprising a plurality of entries;

storing, in memory, a plurality of page headers, each page header corresponding to a respective page of the plurality of pages, each page header comprising a page number identifying the respective page, a first guide word, and a second guide word, wherein the first and second guide words define minimum and maximum name values, respectively, of entries on the respective page;

upon a request to determine if an entry associated with a name value exists, scanning the first and second guide words of the plurality of page headers stored in memory;

identifying a particular page number in a particular page header when, based on the scan, the name value is between first and second guide words of the particular page header;

checking in memory pages for a page identified by the particular page number;

upon determining that the page is not in memory, locating the page on disk and loading, subject to a page replacement algorithm, the page into memory; and

examining the page loaded into memory to determine whether the entry exists on the page.

2. The method of claim 1 wherein the plurality of entries identify items previously backed up, an existing entry thereby indicating that an item identified by the existing entry has been previously backed up, and the examining the page comprises:

if the entry does not exist on the page, transmitting the item to a backup server for a backup.

3. The method of claim 1 wherein the plurality of entries identify items previously backed up, an existing entry thereby indicating that an item identified by the existing entry has been previously backed up, and the examining the page comprises:

if the entry does exist on the page, transmitting a reference to the backup server for the backup.

4. The method of claim 1 comprising:

not examining pages of the plurality of pages where the name value falls outside first and second guide words of page headers corresponding to the pages.

5. The method of claim 1 wherein the plurality of page headers are sorted according to the first and second guide words.

6. The method of claim 1 wherein a subset of the plurality of pages are associated with a backup and the method comprises:

checking with a backup server that the backup is valid; and

if the backup is not valid, excluding the subset of pages associated with the backup from the examination.

7. A system for accessing data, the system comprising:

a processor-based system executed on a computer system and configured to:

store, on disk, a plurality of pages, each page comprising a plurality of entries;

store, in memory, a plurality of page headers, each page header corresponding to a respective page of the plurality of pages, each page header comprising a page number identifying the respective page, a first guide word, and a second guide word, wherein the first and second guide words define minimum and maximum name values, respectively, of entries on the respective page;

upon a request to determine if an entry associated with a name value exists, scan the first and second guide words of the plurality of page headers stored in memory;

identify a particular page number in a particular page header when, based on the scan, the name value is between first and second guide words of the particular page header;

check in memory pages for a page identified by the particular page number;

upon a determination that the page is not in memory, locate the page on disk and load, subject to a page replacement algorithm, the page into memory; and

examine the page loaded into memory to determine whether the entry exists on the page.

8. The system of claim 7 wherein the plurality of entries identify items previously backed up, an existing entry thereby indicating that an item identified by the existing entry has been previously backed up, and the processor-based system is configured to:

if the entry does not exist on the page, transmit the item to a backup server for a backup.

9. The system of claim 7 wherein the plurality of entries identify items previously backed up, an existing entry thereby indicating that an item identified by the existing entry has been previously backed up, and the processor-based system is configured to:

if the entry does exist on the page, transmit a reference to the backup server for the backup.

10. The system of claim 7 wherein the processor-based system is configured to:

not examine pages of the plurality of pages where the name value falls outside first and second guide words of page headers corresponding to the pages.

11. The system of claim 7 wherein the plurality of page headers are sorted according to the first and second guide words.

12. The system of claim 7 wherein a subset of the plurality of pages are associated with a backup, and the processor-based system is configured to:

check with a backup server that the backup is valid; and

if the backup is not valid, exclude the subset of pages associated with the backup from the examination.

13. A computer program product, comprising a non-transitory computer-readable medium having a computer-readable program code embodied therein, the computer-readable program code adapted to be executed by one or more processors to implement a method comprising:

storing, on disk, a plurality of pages, each page comprising a plurality of entries;

storing, in memory, a plurality of page headers, each page header corresponding to a respective page of the plurality of pages, each page header comprising a page number identifying the respective page, a first guide word, and a second guide word, wherein the first and second guide words define minimum and maximum name values, respectively, of entries on the respective page;

upon a request to determine if an entry associated with a name value exists, scanning the first and second guide words of the plurality of page headers stored in memory;

identifying a particular page number in a particular page header when, based on the scan, the name value is between first and second guide words of the particular page header;

checking in memory pages for a page identified by the particular page number;

upon determining that the page is not in memory, locating the page on disk and loading, subject to a page replacement algorithm, the page into memory; and

examining the page loaded into memory to determine whether the entry exists on the page.

14. The computer program product of claim 13 wherein the plurality of entries identify items previously backed up, an existing entry thereby indicating that an item identified by the existing entry has been previously backed up, and the examining the page comprises:

if the entry does not exist on the page, transmitting the item to a backup server for a backup.

15. The computer program product of claim 13 wherein the plurality of entries identify items previously backed up, an existing entry thereby indicating that an item identified by the existing entry has been previously backed up, and the examining the page comprises:

if the entry does exist on the page, transmitting a reference to the backup server for the backup.

16. The computer program product of claim 13 wherein the method comprises:

not examining pages of the plurality of pages where the name value falls outside first and second guide words of page headers corresponding to the pages.

17. The computer program product of claim 13 wherein the plurality of page headers are sorted according to the first and second guide words.

18. The computer program product of claim 13 wherein a subset of the plurality of pages are associated with a backup and the method comprises:

checking with a backup server that the backup is valid; and

if the backup is not valid, excluding the subset of pages associated with the backup from the examination.