System and method for a hash table and data storage and access using the same
The present teaching relates to method, system, medium, and implementations for storage management. A hash table is constructed, having an index file having one or more slots, each of which includes one or more buckets. Each bucket stores one or more types of records, including a direct record, an indirect record, and a forwarding record. A direct record stores data directly in a bucket of a slot of the index file. When a storage request is received related to some relevant data, the request is handled based on the constructed hash table.
1. A hash table constructed for facilitating data storage and management, comprising:
an index file, generated by a hash table constructor implemented using a processor, having one or more slots, each of which includes one or more buckets, wherein each of the one or more buckets in each of the one or more slots is configured to stores one or more types of records, wherein
the one or more types of records include a direct record, an indirect record, and a forwarding record,
a direct record stores data for subsequent access directly in a bucket of a slot in the index file as direct data which satisfies a first condition,
an indirect record stores information pointing to a storage location where data for subsequent access is stored, and
a forwarding record in a slot indicates that the slot has been rehashed.
2. The hash table of claim 1 , wherein the one or more slots include at least one base slot.
3. The hash table of claim 2 , wherein the one or more slots include at least one rehashed slot, wherein each of the at least one rehashed slot is associated with a corresponding base slot and is created when the corresponding base slot is rehashed.
4. The hash table of claim 3 , wherein a forwarding record is stored in at least some of the one or more buckets of a base slot that has been rehashed, pointing to a rehashed slot created for the base slot.
5. The hash table of claim 3 , wherein whether rehashing is to be performed is determined, by a hash table slot rehashing unit implemented using a processor, with respect to one or more of the at least one base slot individually or collectively based on corresponding pre-determined criteria.
6. The hash table of claim 1 , wherein the direct record specifies a first length of a key and a second length of a value included in the direct data so that storage management for direct data is variable-length enabled.
7. The hash table of claim 1 , further comprising an overflow file for storing data indexed by at least some indirect records in the index file.
8. The hash table of claim 7 , wherein the storage location pointed to by an indirect record corresponds to a location in the overflow file where indirect data are stored.
9. The hash table of claim 7 , wherein an indirect record is one of a short indirect record and a long indirect record.
10. The hash table of claim 9 , wherein
a short indirect record provides information pointing to a location in the overflow file where corresponding short indirect data are stored, wherein the short indirect data satisfy a second condition; and
a long indirect record provides information pointing to a location in the overflow file where corresponding long indirect data are stored.
11. The hash table of claim 10 , wherein
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 so that storage management for short indirect data is variable-length enabled; 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 so that storage management for long indirect data is variable-length enabled.
12. The hash table of claim 1 , wherein a forwarding record in a slot further stores information pointing to a storage location to which the slot has been rehashed.