Hierarchical Data Storage

Patent metadata

Field	Value
Publication number	US-2016335299-A1
Application number	US-201514833015-A
Country	US
Kind code	A1
Filing date	Aug 21, 2015
Priority date	May 11, 2015
Publication date	Nov 17, 2016
Grant date	—

Abstract

System, method, and computer program product key compression and cached-locking are described. A computer system can store database files or operating system files in a tree data structure. The system can store data or metadata as key-value pairs in nodes of the tree data structure. The keys in the key-value pairs can have a hierarchical structure, which may or may not correspond to the tree data structure. The system can compress the keys by reducing duplicated storage of shared portions of the keys. The system can use an index in a tree node to represent the hierarchical structure of the key-value pairs stored in that tree node. To access a value in a key-value pair, the system can identify the tree node to search, query the index in that tree node to locate the value, and then access the value at the indexed location.

First claim

What is claimed is:

1 . A method comprising:
receiving a set of key-value pairs, each key-value pair comprising a key associated with a value, each key comprising a plurality of sub-keys each located in the key at a respective sub-key level; storing the set of key-value pairs in a tree data structure including internal nodes and leaf nodes, the tree data structure having tree levels that are different from the sub-key levels, wherein each leaf node stores one or more key-value pairs of the set of key-value pairs, wherein in each node, one or more sub-keys are compressed and indexed in a slot table in the node, the slot table having slot level arrays corresponding to the sub-key levels; receiving a query providing a query key for accessing a value corresponding to the query key; and accessing the value in response to the query by traversing the tree data structure to identify a leaf node storing the value using the slot tables in the internal nodes and leaf nodes, wherein the method is performed by one or more processors, and the tree data structure is stored in a non-transitory storage device coupled to the one or more processors.

2 . The method of claim 1 , wherein the set of key-value pairs are content in an operating system file or a database file, the tree data structure is a B+ tree.

3 . The method of claim 1 , wherein each sub-key is a portion of the key, each sub-key level corresponds to a location of a corresponding portion of the key, wherein a portion of the key that is located to the left has a higher sub-key level than a portion of the key that is located next to the right, the portion of the key that is located next to the right being designated as a child sub-key of the portion of the key that is located to the left.

4 . The method of claim 1 , wherein each slot level array of the slot table comprises one or more elements, each element including a data tuple corresponding to a sub-key of a key-value pair stored in a node in which the slot table is located, each data tuple including a first reference to a location of the corresponding sub-key in the node, each data tuple including a second reference to a location of a child sub-key, the location of the child sub-key being an index of a left most child of the sub-key represented by the data tuple as represented in a next level slot level array.

5 . The method of claim 4 , wherein each slot level array is stored in memory, wherein a modification of the value in memory triggers a conversion of each slot level array into a respective linked list, and a subsequent flush of the value from the memory to disk triggers a conversion of each linked list into a respective slot level array.

6 . The method of claim 4 , wherein each sub-key is stored and referenced once in each node.

7 . A method comprising:
receiving a set of key-value pairs, each key-value pair comprising a key associated with a value, each key comprising a plurality of sub-keys each located at a respective sub-key level; storing the set of key-value pairs in a tree data structure including a root node and leaf nodes, the tree data structure having tree levels that are different from the sub-key levels, wherein each leaf node stores one or more key-value pairs of the set of key-value pairs; receiving a query providing a query key for accessing a value corresponding to the query key; before locking the root node of the tree data structure to search for the value corresponding to the query key, locking a node referenced by an anchor, the anchor indicating that the node has been previously accessed; searching in the locked node for the value using the query key while other nodes remain unlocked; and locking the root node of the tree data structure only upon determining that the query key is out of range of keys in the node referenced by the anchor, wherein the method is performed by one or more processors.

8 . The method of claim 7 , wherein the set of key-value pairs are content in an operating system file or a database file, the tree data structure is a B+tree.

9 . The method of claim 7 , wherein the anchor comprises a prefix and a suffix, the prefix including a portion of a key that is represented at a higher level in a slot table, the suffix including a portion of the key that is represented at a lower level in the slot table, the anchor further comprises a page number and slot number of the prefix identifying, respectively, the node and the slot corresponding to the prefix, the anchor further comprises a page number and slot number of the suffix identifying, respectively, the node and the slot corresponding to the suffix.

10 . The method of claim 7 , wherein accessing the value comprises adding content to the value, wherein the adding causes a split of nodes in the tree data structure only upon determining, by the processor, that free space in the leaf node is insufficient for adding the content.

11 . The method of claim 7 , wherein searching for the value using the query key comprises searching a slot table of the locked node, the slot table indexing compressed keys stored in the locked node.

12 . 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 perform operations comprising:
receiving a set of key-value pairs, each key-value pair comprising a key associated with a value, each key comprising a plurality of sub-keys each located in the key at a respective sub-key level;
storing the set of key-value pairs in a tree data structure including internal nodes and leaf nodes, the tree data structure having tree levels that are different from the sub-key levels, wherein each leaf node stores one or more key-value pairs of the set of key-value pairs, wherein in leaf node, one or more sub-keys are compressed and indexed in a slot table in the leaf node, the slot table having slot level arrays corresponding to the sub-key levels;
receiving a query providing a query key for accessing a value corresponding to the query key; and
accessing the value in response to the query by traversing the tree data structure to identify a leaf node storing the value using the slot tables in the internal nodes and leaf nodes.

13 . The system of claim 12 , wherein the set of key-value pairs are content in an operating system file or a database file, the tree data structure is a B+ tree.

14 . The system of claim 12 , wherein each sub-key is a portion of the key, each sub-key level corresponds to a location of a corresponding portion of the key, wherein a portion of the key that is located to the left has a higher sub-key level than a portion of the key that is located next to the right, the portion of the key that is located next to the right being designated as a child sub-key of the portion of the key that is located to the left.

15 . The system of claim 12 , wherein each slot level array of the slot table comprises one or more elements, each element including a data tuple corresponding to a sub-key of a key-value pair stored in a node in which the slot table is located, each data tuple including a first reference to a location of the corresponding sub-key in the node, each data tuple including a second reference to a location of a child sub-key, the location of the child sub-key being an index of a left most child of the sub-key represented by the data tuple as represented in a next level slot level array.

16 . The system of claim 15 , wherein each slot level array is stored in memory, wherein a modification of the value in

Assignees

• Apple Inc

Inventors

• Vemulapati Murali
• Qiu James
• Lu Frank

Classifications

• G06F16/2291

  User-Defined Types; Storage management thereof · CPC title

• G06F16/2246 Primary

  Trees, e.g. B+trees · CPC title

• G06F17/30342

  Physics · mapped topic

• G06F17/30327 Primary

  Physics · mapped topic

• G06F17/30132

  Physics · mapped topic