Systems and methods for efficiently locating object names in a large index of records containing object names
First Claim
1. A method of tracking a plurality of file system objects being stored, wherein the plurality of objects is associated with a saveset, comprising:
- providing a bitmap;
applying a hash function to a name of each file system object to generate a hash value k;
setting the kth bit in the bitmap to ON; and
storing the bitmap as a hint in an index, wherein the hint is associated with the saveset, wherein the index contains at least a second hint stored as a second bitmap and associated with a second saveset, wherein the bitmap and the second bitmap are identical; and
wherein the saveset and the second saveset are different.
9 Assignments
0 Petitions
Accused Products
Abstract
A method, article of manufacture, and apparatus for tracking a plurality of objects being stored are disclosed. In an embodiment, this comprises computing the hash value of the name of each object being stored, setting the corresponding bits in a bitmap, and storing the bitmap as a hint in an index. The size of the bitmap is determined by the space available for storing the hint, and the range of hash values is determined by the size of the bitmap. The range may be determined by choosing a prime number smaller than the space available for storing the bitmap. Either the hint or the longest pathname containing the objects can be stored, and this may be selected based on the application.
70 Citations
19 Claims
-
1. A method of tracking a plurality of file system objects being stored, wherein the plurality of objects is associated with a saveset, comprising:
-
providing a bitmap; applying a hash function to a name of each file system object to generate a hash value k; setting the kth bit in the bitmap to ON; and storing the bitmap as a hint in an index, wherein the hint is associated with the saveset, wherein the index contains at least a second hint stored as a second bitmap and associated with a second saveset, wherein the bitmap and the second bitmap are identical; and
wherein the saveset and the second saveset are different. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13)
-
-
14. A method of tracking a plurality of file system objects being stored, wherein the plurality of objects is associated with a saveset, comprising:
-
providing a bitmap; applying a hash function to a name of each file system object to generate a hash value k; setting the kth bit in the bitmap to ON; and storing in an index, the bitmap as a hint or a longest pathname containing the plurality of objects, wherein the hint is associated with the saveset, wherein the index contains at least a second hint stored as a second bitmap and associated with a second saveset, wherein the bitmap and the second bitmap are identical; and
wherein the saveset and the second saveset are different. - View Dependent Claims (15, 16, 17, 18)
-
-
19. A computer program product for tracking a plurality of file system objects being stored, wherein the plurality of objects is associated with a saveset, comprising a non-transitory computer usable medium having machine readable code embodied therein for:
-
providing a bitmap; applying a hash function to a name of each file system object to generate a hash value k; setting the kth bit in the bitmap to ON; and storing the bitmap as a hint in an index, wherein the hint is associated with the saveset, wherein the index contains at least a second hint stored as a second bitmap and associated with a second saveset, wherein the bitmap and the second bitmap are identical; and
wherein the saveset and the second saveset are different.
-
Specification