Efficient filename storage and retrieval

Patent metadata

Field	Value
Publication number	US-11704336-B2
Application number	US-202117204208-A
Country	US
Kind code	B2
Filing date	Mar 17, 2021
Priority date	Dec 28, 2017
Publication date	Jul 18, 2023
Grant date	Jul 18, 2023

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 already exists in a filename array when a query for a reference location of the filename in the filename array returns the reference location of the filename in the filename array and not adding to the filename array when the filename already exists in the filename array;
based on the query returning the reference location, storing the reference location of the filename in the node; and
accessing the filename of the content item associated with the node by using the stored reference location in the node to look up the filename in the filename array, wherein
the reference location to the filename in the filename array includes an integer value that represents an offset, location, or position of the filename in the filename array.

2. The computer-implemented method of claim 1 , wherein the modification to the node includes renaming the node or adding the node as a new node to the tree data structure, and wherein the computer-implemented method further comprises:
storing the reference location in the new or renamed node.

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

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

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

6. The computer-implemented method of claim 4 , further comprising:
receiving a query for the reference location of the filename;
in response to the query, retrieving, from the position in the hash index, the reference location of the filename, wherein the reference location is associated with the filename array; and
provide the reference location of the filename.

7. The computer-implemented method of claim 6 , further comprising:
retrieving, from the filename array using the reference location, a string; and
comparing the string with the filename, wherein the reference location of the filename is confirmed when the string and the filename match.

8. 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 already exists in a filename array when a query for a reference location of the filename in the filename array returns the reference location of the filename in the filename array and not adding to the filename array when the filename already exists in the filename array;
based on the query returning the reference location, store the reference location of the filename in the node; and
access the filename of the content item associated with the node by using the stored reference location in the node to look up the filename in the filename array, wherein
the reference location to the filename in the filename array includes an integer value that represents an offset, location, or position of the filename in the filename array.

9. The non-transitory computer-readable medium of claim 8 , wherein the modification to the node includes renaming the node or adding the node as a new node to the tree data structure, and wherein the instructions, when executed by the computing system, cause the computing system to:
storing the reference location in the new or renamed node.

10. The non-transitory computer-readable medium of claim 8 , wherein the instructions, when executed by the computing system, cause the computing system to:
store the reference location of the filename in a hash index.

11. The non-transitory computer-readable medium of claim 10 , wherein the instructions, when executed by the computing system, cause the computing system to:
hash the filename to determine a position in the hash index, wherein the reference location of the filename is stored at the position in the hash index.

12. The non-transitory computer-readable medium of claim 11 , wherein the instructions, when executed by the computing system, cause the computing system to:
determine that the position in the hash index is occupied; and
store the reference location of the filename in a next position in the hash index.

13. The non-transitory computer-readable medium of claim 11 , wherein the instructions, when executed by the computing system, cause the computing system to:
receive a query for the reference location of the filename;
in response to the query, retrieve, from the position in the hash index, the reference location of the filename, wherein the reference location is associated with the filename array; and
provide the reference location of the filename.

14. The non-transitory computer-readable medium of claim 13 , wherein the instructions, when executed by the computing system, cause the computing system to:
retrieve, from the filename array using the reference location, a string; and
compare the string with the filename, wherein the reference location of the filename is confirmed when the string and the filename match.

15. A system comprising:
one or more processors; and
a non-transitory computer-readable medium storing instructions that, when executed by the one or more processors, cause the one or more processors 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 already exists in a filename array when a query for a reference location of the filename in the filename array returns the reference location of the filename in the filename array and not adding to the filename array when the filename already exists in the filename array;
based on the query returning of the reference location, store the reference location of the filename in the node; and
access the filename of the content item associated with the node uses the stored reference location in the node to look up the filename in the filename array, wherein
the reference location to the filename in the filename array includes an integer value that represents an offset, location, or position of the filename in the filename array.

16. The system of claim 15 , wherein the modification to the node includes renaming the node or adding the node as a new node to the tree data structure, and wherein the instructions, when executed by the one or more processors, cause the one or more processors to:
store the reference location in the new or renamed node.

17. The system of claim 15 , wherein the instructions, when executed by the one or more processors, cause the one or more processors to:
store the reference location of the filename in a hash index.

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

• G06F21/10

  Protecting distributed programs or content, e.g. vending or licensing of copyrighted material (protection in video systems or pay television H04N7/16) {; Digital rights management [DRM]} · CPC title

• G06F1/04

  Generating or distributing clock signals or signals derived directly therefrom · CPC title

• G06F3/065

  Replication mechanisms · CPC title