System and method for a hash table and data storage and access using the same

1. A method implemented on at least one processor, a memory, and a communication platform capable of variable length storage management, comprising:

constructing a hash table including an index file having one or more slots, each of which includes one or more buckets, wherein each of the one or more buckets stores one or more types of records;

receiving a storage request associated with relevant data; and

handling the storage request based on the hash table, wherein

the one or more types of records include a direct record, an indirect record, and a forwarding record, and

a direct record stores data directly in a bucket of a slot in the index file.

2. The method of claim 1 , wherein the one or more slots include at least one base slot.

3. The method of claim 2 , wherein the one or more slots further include at least one rehashed slot.

4. The method of claim 3 , further comprising:

assessing, with respect to one or more of the at least one base slot, whether the one or more base slots, individually or collectively, need to be rehashed based on pre-determined criteria; and

rehashing a base slot when the step of assessing indicates that the base slot needs to be rehashed.

5. The method of claim 4 , wherein the step of rehashing comprises:

creating a rehashed slot for the base slot that needs to be rehashed based on at least one rehashing parameter; and

inserting a forwarding record in the base slot, wherein the forward record provides information pointing to the rehashed slot.

6. The method of claim 1 , wherein the hash table further comprises an overflow file for storing data indexed by at least some records in the index file.

7. The method of claim 6 , wherein

an indirect record is one of a short indirect record and a long indirect record, wherein

the short indirect record provides information pointing to a location in the overflow file where corresponding short indirect data are stored, and

the long indirect record provides information pointing to a location in the overflow file where corresponding long indirect data are stored.

8. The method of claim 7 , wherein

a direct record specifies a first length of a key and a second length of a value included in the direct data to enable variable-length storage management of direct data;

short indirect data provide information about a first length of a key and a second length of a value included in the short indirect data to enable variable-length storage management of short indirect data; and

long indirect data provide information about a first length of a key and a second length of a value included in the long indirect data to enable variable-length storage management of long indirect data.

9. The method of claim 6 , wherein the step of handling the storage request based on the hash table comprises:

identifying one of the one or more slots and a bucket therein for the relevant data in accordance with a hash code computed based on the relevant data;

storing, when the storage request is for storing the relevant data, the relevant data based on the identified slot and bucket; and

retrieving, when the storage request is for retrieving the relevant data, the relevant data based on the identified slot and bucket.

10. The method of claim 9 , wherein the slot for the relevant data is one of

a base slot identified using the hash code; and

a rehashed slot associated with the base slot, identified based on a forwarding record stored in the base slot.

11. The method of claim 9 , wherein the step of storing the relevant data comprises:

saving the relevant data in a direct record in the bucket of the slot when the relevant data satisfy a first condition;

saving, when the relevant data do not satisfy the first condition, the relevant data as indirect data.

12. The method of claim 11 , wherein the step of saving the relevant data as indirect data comprises:

saving, when the relevant data satisfy a second condition, the relevant data as short indirect data by

inserting a short indirect record in the bucket of the slot with information pointing to a location in the overflow file where the short indirect data are stored, and

saving the short indirect data at the location of the overflow file; and

saving, when the relevant data do not satisfy the second condition, the relevant data as long indirect data by

inserting a long indirect record in the bucket of the slot with information pointing to a location in the overflow file where the long indirect data are stored, and

saving the long indirect data at the location of the overflow file.

13. The method of claim 9 , wherein the step of retrieving the relevant data comprises:

retrieving the relevant data from a direct record stored in the bucket of the slot when the relevant data satisfy a first condition;

retrieving, when the relevant data do not satisfy the first condition, the relevant data as indirect data.

14. The method of claim 13 , wherein the step of retrieving the relevant data as indirect data comprises:

returning, when the relevant data satisfy a second condition, the relevant data as short indirect data by

obtaining a short indirect record from the bucket of the slot for information pointing to a location in the overflow file where the short indirect data are stored, and

accessing the short indirect data stored at the location of the overflow file; and

returning, when the relevant data do not satisfy the second condition, the relevant data as long indirect data by

obtaining a long indirect record from the bucket of the slot for information pointing to a location in the overflow file where the long indirect data are stored, and

accessing the long indirect data at the location of the overflow file.

15. Machine readable and non-transitory medium having information stored thereon for variable length storage management, wherein the information, when read by the machine, causes the machine to perform the following steps:

constructing a hash table including an index file having one or more slots, each of which includes one or more buckets, wherein each of the one or more buckets stores one or more types of records;

receiving a storage request associated with relevant data; and

handling the storage request based on the hash table, wherein

the one or more types of records include a direct record, an indirect record, and a forwarding record, and

a direct record stores data directly in a bucket of a slot in the index file.

16. The medium of claim 15 , wherein the one or more slots include at least one base slot.

17. The medium of claim 16 , wherein the one or more slots further include at least one rehashed slot.

18. The medium of claim 17 , further comprising:

assessing, with respect to one or more of the at least one base slot, whether the one or more base slots, individually or collectively, need to be rehashed based on pre-determined criteria; and

rehashing a base slot when the step of assessing indicates that the base slot needs to be rehashed.

19. The medium of claim 18 , wherein the step of rehashing comprises:

creating a rehashed slot for the base slot that needs to be rehashed based on at least one rehashing parameter; and

inserting a forwarding record in the base slot, wherein the forward record provides information pointing to the rehashed slot.

20. The medium of claim 15 , wherein the hash table further comprises an overflow file for storing data indexed by at least some records in the index file.

21. The medium of claim 20 , wherein

an indirect record is one of a short indirect record and a long indirect record, wherein

the short indirect record provides information pointing to a location in the overflow file where corresponding short indirect data are stored, and

the long indirect record provides information pointing to a location in the overflow file where corresponding long indirect data are stored.

22. The medium of claim 21 , wherein

a direct record specifies a first length of a key and a second length of a value included in the direct data to enable variable-length storage management of direct data;

short indirect data provide information about a first length of a key and a second length of a value included in the short indirect data to enable variable-length storage management of short indirect data; and

long indirect data provide information about a first length of a key and a second length of a value included in the long indirect data to enable variable-length storage management of long indirect data.

23. The medium of claim 20 , wherein the step of handling the storage request based on the hash table comprises:

identifying one of the one or more slots and a bucket therein for the relevant data in accordance with a hash code computed based on the relevant data;

storing, when the storage request is for storing the relevant data, the relevant data based on the identified slot and bucket; and

retrieving, when the storage request is for retrieving the relevant data, the relevant data based on the identified slot and bucket.

24. The medium of claim 23 , wherein the slot for the relevant data is one of

a base slot identified using the hash code; and

a rehashed slot associated with the base slot, identified based on a forwarding record stored in the base slot.

25. The medium of claim 23 , wherein the step of storing the relevant data comprises:

saving the relevant data in a direct record in the bucket of the slot when the relevant data satisfy a first condition;

saving, when the relevant data do not satisfy the first condition, the relevant data as indirect data.

26. The medium of claim 25 , wherein the step of saving the relevant data as indirect data comprises:

saving, when the relevant data satisfy a second condition, the relevant data as short indirect data by

inserting a short indirect record in the bucket of the slot with information pointing to a location in the overflow file where the short indirect data are stored, and

saving the short indirect data at the location of the overflow file; and

saving, when the relevant data do not satisfy the second condition, the relevant data as long indirect data by

inserting a long indirect record in the bucket of the slot with information pointing to a location in the overflow file where the long indirect data are stored, and

saving the long indirect data at the location of the overflow file.

27. The medium of claim 23 , wherein the step of retrieving the relevant data comprises:

retrieving the relevant data from a direct record stored in the bucket of the slot when the relevant data satisfy a first condition;

retrieving, when the relevant data do not satisfy the first condition, the relevant data as indirect data.

28. The medium of claim 27 , wherein the step of retrieving the relevant data as indirect data comprises:

returning, when the relevant data satisfy a second condition, the relevant data as short indirect data by

obtaining a short indirect record from the bucket of the slot for information pointing to a location in the overflow file where the short indirect data are stored, and

accessing the short indirect data stored at the location of the overflow file; and

returning, when the relevant data do not satisfy the second condition, the relevant data as long indirect data by

obtaining a long indirect record from the bucket of the slot for information pointing to a location in the overflow file where the long indirect data are stored, and

accessing the long indirect data at the location of the overflow file.