Kvs tree

Abstract

A KVS tree and operations thereon are described herein. A key-value set (kvset) is received to store in a key-value data structure on at least one machine readable medium. The kvset includes a mapping of unique keys to values with the keys and the values of the kvset being immutable. The key-value data structure is organized as a tree with nodes of the tree including a temporally ordered sequence of kvsets. The kvset, once received, is written to a sequence of kvsets of a root-node of the tree.

What is claimed is: 
     
         1 . A key-value data structure, organized as a tree, on at least one non-transitory machine readable medium, the key-value data structure comprising:
 a multiple of nodes, a node from the multiple of nodes comprising:
 a temporally ordered sequence of key-value sets, the temporally ordered sequence comprising an oldest key-value set at one end of the temporally ordered sequence and a newest key-value set at another end of the temporally ordered sequence; and 
 a determinative mapping for a key-value pair, in a key-value set of the temporally ordered sequence of key-value sets, to any one child node of the node, the determinative mapping providing a rule that any key-value pair maps to a specific path through the tree to a specific child node at any level of the tree without regard to node content of the tree. 
   
     
     
         2 . The key-value data structure of  claim 1 , wherein the determinative mapping comprises a portion of a hash of a portion of a key. 
     
     
         3 . The key-value data structure of  claim 2 , wherein the hash comprises a multiple of non-overlapping portions comprising the portion of the hash. 
     
     
         4 . The key-value data structure of  claim 3 , wherein each of the multiple of non-overlapping portions corresponds to a level of the tree. 
     
     
         5 . The key-value data structure of  claim 4 , wherein the portion of the hash is determined from the multiple of non-overlapping portions by a level of the node. 
     
     
         6 . The key-value data structure of  claim 5 , wherein a maximum number of child nodes for the node is defined by a size of the portion of the hash. 
     
     
         7 . The key-value data structure of  claim 1 , wherein the key-value set comprises a key-tree to store key entries of key-value pairs of the key-value set. 
     
     
         8 . The key-value data structure of  claim 1 , wherein key entries of the key-value set are stored in a set of key-blocks comprising a primary key-block and zero or more extension key-blocks, members of the set of key-blocks corresponding to media blocks for a storage medium, each key-block comprising a header to identify it as a key-block; and
 wherein values are stored in a set of value-blocks, members of the set of value-blocks corresponding to media blocks for the storage medium, each value-block comprising a header to identify it as a value-block.   
     
     
         9 . The key-value data structure of  claim 8 , wherein a value-block comprises storage section to one or more values without separation between values. 
     
     
         10 . The key-value data structure of  claim 8 , wherein the primary key-block comprises a list of media block identifications for one or more extension key-blocks of the key-value set. 
     
     
         11 . The key-value data structure of  claim 8 , wherein the primary key-block comprises a list of media block identifications for value-blocks in the set of value-blocks. 
     
     
         12 . The key-value data structure of  claim 8 , wherein the primary key-block comprises a copy of a lowest key in a key-tree of the key-value set, the lowest key determined by a pre-set sort-order of the tree. 
     
     
         13 . The key-value data structure of  claim 8 , wherein the primary key-block comprises a copy of a highest key in a key-tree of the key-value set, the highest key determined by a pre-set sort-order of the tree. 
     
     
         14 . The key-value data structure of  claim 8 , wherein the primary key-block comprises a header to a key-tree of the key-value set. 
     
     
         15 . The key-value data structure of  claim 8 , wherein the primary key-block comprises a list of media block identifications for a key-tree of the key-value set. 
     
     
         16 . The key-value data structure of  claim 8 , wherein the primary key-block comprises a bloom filter header for a bloom filter of the key-value set. 
     
     
         17 . The key-value data structure of  claim 8 , wherein the primary key-block comprises a list of media block identifications for a bloom filter of the key-value set. 
     
     
         18 . The key-value data structure of  claim 8 , wherein the primary key-block comprises a set of metrics for the key-value set. 
     
     
         19 . A system comprising processing circuitry to perform operations comprising:
 receiving a key-value set to store in a key-value data structure, organized as a tree, on at least one machine readable medium, the key-value data structure comprising a multiple of nodes, a node from the multiple of nodes comprising:
 a temporally ordered sequence of key-value sets, the temporally ordered sequence comprising an oldest key-value set at one end of the temporally ordered sequence and a newest key-value set at another end of the temporally ordered sequence; and 
 a determinative mapping for a key-value pair, in a key-value set of the temporally ordered sequence of key-value sets, to any one child node of the node, the determinative mapping providing a rule that any key-value pair maps to a specific path through the tree to a specific child node at any level of the tree without regard to node content of the tree; and 
   writing the key-value set to a temporally ordered sequence of key-value sets of a root-node of the key-value data structure.   
     
     
         20 . At least one non-transitory machine readable medium comprising instructions that, when executed by processing circuitry, cause a machine to perform operations comprising:
 receiving a key-value set to store in a key-value data structure, organized as a tree, on at least one machine readable medium, the key-value data structure comprising a multiple of nodes, a node from the multiple of nodes comprising:
 a temporally ordered sequence of key-value sets, the temporally ordered sequence comprising an oldest key-value set at one end of the temporally ordered sequence and a newest key-value set at another end of the temporally ordered sequence; and 
 a determinative mapping for a key-value pair, in a key-value set of the temporally ordered sequence of key-value sets, to any one child node of the node, the determinative mapping providing a rule that any key-value pair maps to a specific path through the tree to a specific child node at any level of the tree without regard to node content of the tree; and 
   writing the key-value set to a temporally ordered sequence of key-value sets of a root-node of the key-value data structure.