Trie data structure with subtrie data structures

Abstract

Techniques are disclosed relating to tree data structures capable of storing information indicative of database keys. A computer system may operate a database. The computer system may store a multi-level tree data structure usable to perform key lookups for the database. In various cases, the multi-level tree data structure may be stored in system memory as a plurality of subtree data structures each comprising a set of linked nodes. A given one of the plurality of subtree data structures may be stored as a respective continuous block of information in system memory. The computer system may access the respective continuous block for a first particular subtree data structure encompassing a particular range of levels in the multi-level tree data structure. The accessing may be performed without accessing one or more other subtree data structures encompassing one or more levels within the particular range of levels.

What is claimed is: 
     
       1. A method, comprising:
 storing, by a computer system, a set of records in a file; 
 storing, by the computer system, a multi-level tree data structure that is usable to determine whether a record for a database key is not stored in the file, wherein the multi-level tree data structure is stored in a system memory of the computer system as a plurality of subtree data structures, wherein a memory size of the multi-level tree data structure does not permit the multi-level tree data structure to be loaded entirely into a system cache of the computer system, and wherein a memory size of a given subtree data structure permits the given subtree data structure to be loaded entirely into the system cache, and wherein the given subtree data structure comprises a set of linked nodes that correspond to a set of characters of database keys inserted into the multi-level tree data structure; 
 as part of a key lookup for a particular database key, the computer system fetching, into the system cache from the system memory, a first subtree data structure encompassing a particular range of levels in the multi-level tree data structure, wherein the fetching is performed without accessing one or more other subtree data structures encompassing one or more levels within the particular range of levels, and wherein the first subtree data structure includes pointer information specifying a memory size of a second subtree data structure that enables the computer system to fetch the second subtree data structure entirely; and 
 fetching, by the computer system, the second subtree data structure into the system cache using the pointer information. 
 
     
     
       2. The method of  claim 1 , wherein a first character of the particular database key corresponds to a node in the first subtree data structure and a second character of the particular database key corresponds to a node in the second subtree data structure. 
     
     
       3. The method of  claim 2 , wherein the pointer information identifies a location in the system memory where a continuous block for the second subtree data structure is stored. 
     
     
       4. The method of  claim 1 , wherein the memory size indicates a number of cache lines that the second subtree data structure consumes when stored in the system cache. 
     
     
       5. The method of  claim 1 , further comprising:
 updating, by the computer system, the multi-level tree data structure to include one or more nodes, wherein the updating includes modifying a particular one of the plurality of subtree data structures such that a particular range of levels encompassed by the particular subtree data structure is changed. 
 
     
     
       6. The method of  claim 1 , further comprising:
 receiving a request to perform a transaction that includes writing, to a database, the file that includes the set of records; and 
 performing the transaction, including generating the multi-level tree data structure, wherein the multi-level tree data structure is associated with the file. 
 
     
     
       7. The method of  claim 1 , wherein the multi-level tree data structure is stored as a continuous block of information in the system memory. 
     
     
       8. A non-transitory computer readable medium having program instructions stored thereon that are capable of causing a computer system to perform operations comprising:
 storing a set of records in a file; 
 storing a multi-level tree data structure that is usable to determine whether a record for a database key is not stored in the file, wherein the multi-level tree data structure is stored in a system memory of the computer system as a plurality of subtree data structures, wherein a memory size of the multi-level tree data structure does not permit the multi-level tree data structure to be loaded entirely into a system cache of the computer system, and wherein a memory size of a given subtree data structure permits the given subtree data structure to be loaded entirely into the system cache, and wherein the given subtree data structure comprises a set of linked nodes that correspond to a set of characters of database keys inserted into the multi-level tree data structure; and 
 as part of a key lookup for a particular database key, fetching, into the system cache from the system memory, for a first subtree data structure encompassing a particular range of levels in the multi-level tree data structure, wherein the fetching is performed without accessing one or more other subtree data structures encompassing one or more levels within the particular range of levels, and wherein the first subtree data structure includes pointer information specifying a memory size of a second subtree data structure that enables the computer system to fetch the second subtree data structure entirely; and 
 fetching the second subtree data structure into the system cache using the pointer information. 
 
     
     
       9. The non-transitory computer readable medium of  claim 8 , wherein the pointer information identifies a location in the system memory where a continuous block of the second subtree data structure is stored. 
     
     
       10. The non-transitory computer readable medium of  claim 8 , wherein the operations further comprise:
 updating the multi-level tree data structure to include a set of nodes, wherein the updating includes expanding the set of linked nodes of one of the plurality of subtree data structures to include one or more of the set of nodes. 
 
     
     
       11. The non-transitory computer readable medium of  claim 8 , wherein the operations further comprise:
 updating the multi-level tree data structure to include a set of nodes, wherein the updating includes splitting one of the plurality of subtree data structures into two or more subtree data structures. 
 
     
     
       12. A method, comprising:
 storing, by a computer system in system memory, a tree data structure that is usable to determine whether a record for a database key is not stored in a file, wherein the tree data structure comprises a plurality of subtree data structures, wherein a first subtree data structure that is connected to a second subtree data structure as part of a particular branch of the tree data structure includes pointer information having data that specifies a memory size of the second subtree data structure and a location in the system memory where the second subtree data structure is stored, wherein a memory size of the tree data structure does not permit the tree data structure to be loaded entirely into a system cache of the computer system, and wherein a memory size of the first and second subtree data structures permits the first and second subtree data structures to be loaded entirely into the system cache; and 
 performing, by the computer system using the tree data structure, a key range lookup for a particular database key that includes traversing the particular branch, wherein the performing includes:
 loading the first subtree data structure into the system cache; and 
 loading the second subtree data structure into the system cache using the pointer information included in the first subtree data structure. 
 
 
     
     
       13. The method of  claim 12 , wherein the pointer information further identifies a location in the system memory where a third subtree data structure is stored, and wherein the first subtree data structure is connected to the third subtree data structure as part of another particular branch of the tree data structure. 
     
     
       14. The method of  claim 12 , further comprising:
 updating the tree data structure to include a set of nodes, wherein the updating results in the tree data structure including one or more additional subtree data structures. 
 
     
     
       15. The method of  claim 12 , wherein the tree data structure is not stored as one continuous block of information in the system memory.