Efficient filename storage and retrieval

Patent metadata

Field	Value
Publication number	US-11016991-B2
Application number	US-201715858192-A
Country	US
Kind code	B2
Filing date	Dec 29, 2017
Priority date	Dec 28, 2017
Publication date	May 25, 2021
Grant date	May 25, 2021

Abstract

The disclosed technology relates to a system configured to detect a modification to a node in a tree data structure. The node is associated with a content item managed by a content management service as well as a filename. The system may append the filename and a separator to a filename array, determine a location of the filename in the filename array, and store the location of the filename in the node.

First claim

What is claimed is:

1. A computer-implemented method comprising:
detecting a modification to a node in a tree data structure, wherein the node is associated with a content item managed by a content management service and wherein the node is associated with a filename;
determining that the filename does not already exist in a filename array;
appending the filename and a separator to the filename array;
determining a location of the filename in the filename array; and
storing the location of the filename in the node, wherein accessing the filename in the node uses the stored location to lookup the filename in the filename array.

2. The computer-implemented method of claim 1 , further comprising:
storing the location of the filename in a hash index.

3. The computer-implemented method of claim 2 , further comprising:
hashing the filename to determine a position in the hash index, wherein the location of the filename is stored at the position in the hash index.

4. The computer-implemented method of claim 2 , further comprising:
hashing the filename to determine a position in the hash index;
determining that the position in the hash index is occupied; and
storing the location of the filename in a next position in the hash index.

5. The computer-implemented method of claim 1 , wherein the modification is one of an add of the node to the tree data structure or an edit of the filename of the node.

6. The computer-implemented method of claim 1 , further comprising:
checking whether the filename already exists in the filename array.

7. The computer-implemented method of claim 6 , wherein the checking of whether the filename already exists in the filename array comprises:
performing a hash function on the filename to obtain a position in a hash index;
retrieving, from the position in the hash index, location information;
retrieving, from the filename array using the location information, a string; and
comparing the string with the filename, wherein the filename already exists in the filename array when the string matches the filename.

8. The computer-implemented method of claim 1 , wherein the tree data structure is at least one of a remote tree, a sync tree, or a local tree stored at a client device.

9. A non-transitory computer-readable medium comprising instructions, the instructions, when executed by a computing system, cause the computing system to:
detect a modification to a node in a tree data structure, wherein the node is associated with a content item managed by a content management service and wherein the node is associated with a filename;
determine that the filename does not already exist in a filename array;
append the filename and a separator to the filename array;
determine a location of the filename in the filename array;
store the location of the filename in the node;
access the location of the filename of the content item managed by the content management service, wherein the location is stored in a node of a tree data structure; and
retrieve the filename of the content item from a filename array at the location stored in the node.

10. The non-transitory computer-readable medium of claim 9 , wherein the instructions further cause the computing system to:
initiate a read of the filename from the filename array, wherein the read begins from the location specified in the node; and
complete the read of the filename when a separator his reached.

11. The non-transitory computer-readable medium of claim 10 , wherein the separator is a null character.

12. A system comprising:
a processor; and
a non-transitory computer-readable medium storing instructions that, when executed by the processor, cause the processor to:
detect a modification to a node in a tree data structure, wherein the node is associated with a content item managed by a content management service and wherein the node is associated with a filename;
store the location information of the filename in the node;
generate a position in a hash index by performing a hash function on the filename;
receive a query for the location information of the filename;
in response to the query, retrieve, from the position in the hash index, location information of the filename, wherein the location information is associated with a filename array; and
provide the location information of the filename.

13. The system of claim 12 , wherein the modification is one of an add of the node to the tree data structure or an edit of the filename of the node.

14. The system of claim 12 , wherein the tree data structure is at least one of a remote tree, a sync tree, or a local tree stored at a client device.

15. The system of claim 12 , wherein the instructions further cause the processor to:
retrieve, from the filename array using the location information, a string; and
compare the string with the filename, wherein the location information of the filename is confirmed when the string and the filename match.

16. The system of claim 15 , wherein the instructions further cause the processor to:
replace the location information of the filename with content retrieved from a next position in the hash index;
retrieve, from the filename array using the content retrieved from the next position, a second string; and compare the second string with the filename; and
replace the location information with the content retrieved from the next position when the string and the filename match.

17. The system of claim 12 , wherein the filename array and the hash index are stored in random access memory.

18. The system of claim 12 , wherein the instructions further cause the processor to load the filename array and the hash index are stored into random access memory on startup.

Assignees

• Dropbox Inc

Inventors

• Jayakar Sujay

Classifications

• G06F16/27 Primary

  Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor · CPC title

• G06F16/11 Primary

  File system administration, e.g. details of archiving or snapshots (error detection or correction of the data by redundancy in operations G06F11/14) · CPC title

• H04L67/01

  Protocols · CPC title

• H04L63/0853

  using an additional device, e.g. smartcard, SIM or a different communication terminal (cryptographic mechanisms or cryptographic arrangements for entity authentication involving additional secure or trusted devices H04L9/3234) · CPC title

• H04L63/101

  Access control lists [ACL] · CPC title