B-Tree Based Data Model for File Systems
Methods and systems for organizing data are provided. An example method includes providing an object store to store objects. Each of the objects represents fragments of the data is are associated with an address. The method further allows associating a B-tree with the object store. The B-tree includes nodes, wherein each of the nodes includes keys, and wherein each of the keys is associated with at least one object from the object store. Values for each of the keys are generated based at least partially on objects from the object store. If the size of an object from the object store is less than a pre-determined size, a value of the object is stored in a particular node of the B-tree, with the particular nodes including a particular key associated with the object. Otherwise, the method includes storing the address associated with the object in the particular node of the B-tree.
1 . A computer-implemented method for organizing data, the method comprising:
providing an object store to store objects, each of the objects representing a fragment of the data and being associated with an address;
associating a B-tree with the object store, the B-tree including nodes, wherein each of the nodes includes keys, wherein each of the keys is associated with at least one object from the object store; and
generating, based at least partially on objects from the object store, values for each of the keys.
2 . The method of claim 1 , wherein the address of an object in the object store is based on content of the fragment of the data.
3 . The method of claim 1 , further comprising:
determining that a size of an object from the object store is less than a pre-determined size;
if a result of the determination is positive, storing a value of the object in a particular node of the B-tree, the particular node including a particular key associated with the object; and
if a the result of the determination is negative, storing the address of the object in the particular node of the B-tree.
4 . The method of claim 1 , wherein each of the objects includes at least one of the following:
a metadata object storing at least a number of references to further objects from the data objects and an identification number associated with a file or a directory; and
a data object representing at least one of the following: a continuous fragment of the file or a directory entry.
5 . The method of claim 4 , wherein the key associated with the metadata object includes at least a first field including an indication of the metadata object, a second field including the identification number, and a third field including a metadata index representing a distinct type of the metadata object.
6 . The method of claim 5 , wherein the type of the metadata object includes at least one of the following: attributes associated with the file or the directory, a symbolic link to the file or the directory, and an extended file attribute associated with the file or the directory.
7 . The method of claim 4 , wherein the key associated with the fragment of the file includes at least a first field including an indication of the data object, a second field including the identification number, and a third field including an offset of the continuous fragment of the file from a beginning of the file.
8 . The method of claim 4 , wherein the key associated with the directory entry includes at least a first field including an indication of the data object, a second field including the identification number, and a third field including a hash calculated based on a literal name of the directory entry.
9 . The method of claim 8 , wherein calculating the hash includes:
applying a hash function to the literal name to obtain a preliminary hash, the hash function including at least one of the following: crc32c, SipHash, and SipHash-order3; and
shifting the preliminary hash by a pre-determined base number to obtain the hash.
10 . The method of claim 9 , further comprising:
determining that the hash matches an existing hash; and
based on the determination, incrementing the hash by 1.
11 . A system for organizing data, the system comprising:
at least one processor; and
a memory communicatively coupled to the at least one processor, the memory storing instructions, which, when executed by the at least one processor, perform a method comprising:
providing an object store to store objects, each of the objects representing a fragment of the data and associated with an address;
associating a B-tree with the object store, the B-tree including nodes, wherein each of the nodes includes keys, wherein each of the keys is associated with at least one object from the object store; and
generating, based at least partially on objects from the objects, values for each of the keys.
12 . The system of claim 11 , wherein the address of an object in the object store is based on content of the fragment of the data.
13 . The system of claim 11 , wherein the method further comprising:
determining that a size of an object from the object store is less than a pre-determined size;
if a result of the determination is positive, storing a value of the object in a particular node of the B-tree, the particular node including a particular key associated with the object; and
if a the result of the determination is negative, storing the address of the object in the particular node of the B-tree.
14 . The system of claim 11 , wherein each of the objects includes at least one of the following:
a metadata object storing at least a number of references to further objects from the data objects and an identification number associated with a file or a directory; and
a data object representing at least one of the following: a continuous fragment of the file or a directory entry.
15 . The system of claim 14 , wherein the key associated with the metadata object includes at least a first field including an indication of the metadata object, a second field including the identification number, and a third field including a metadata index representing a distinct type of the metadata object.
16 . The system of claim 15 , wherein the type of the metadata object includes at least one of the following: attributes associated with the file or the directory, a symbolic link to the file or the directory, and an extended file attribute associated with the file or the directory.
17 . The system of claim 14 , wherein the key associated with the fragment of the file includes at least a first field including an indication of the data object, a second field including the identification number, and a third field including an offset of the continuous fragment of the file from beginning of the file.
18 . The system of claim 14 , wherein the key associated with the directory entry includes at least a first field including an indication of the data object, a second field including the identification number, and a third field including a hash calculated based on a literal name of the directory entry.
19 . The system of claim 18 , wherein calculating the hash includes:
applying a hash function to the literal name to obtain a preliminary hash, the hash function including at least one of the following: crc32c, SipHash, and SipHash-order3;
shifting the preliminary hash by a pre-determined base number to obtain the hash;
determining that the hash matches an existing hash; and
based on the determination, incrementing the hash by 1.
20 . A non-transitory computer-readable storage medium having embodied thereon instructions, which, when executed by one or more processors, perform a method for organizing data, the method comprising:
providing an object store to store objects, each of the objects representing a fragment of the data and associated with an address;
associating a B-tree with the object store, the B-tree including nodes, wherein each of the nodes includes keys, wherein each of the keys is associated with at least one object from the object store;
generating, based at least partially on objects from the objects, values for the each of the keys;
determining that a size of an object from the object store is less than a pre-determined size;
if a result of the determination is positive, storing a value of the object in a particular node of the B-tree, the particular node including a particular key associated with the object; and
if a result of the determination is negative, storing the address of the object in the particular node of the B-tree.