# US 10,372,917 B1 · Uniquely-represented B-trees > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 10,372,917 B1 - Document ID: US10372917B1 - Status: Granted - Kind: B1 - Application number: 15/370,731 - Filed: 2016-12-06 - Granted: 2019-08-06 - Earliest claimed: 2016-10-21 - Assignees: Google Inc. - Applicants: Google LLC - Inventors: Etienne Membrives; Przemyslaw Pietrzkiewicz; Benjamin Lerman; Despoina Vouzoukidou - Web page: https://patentgrep.com/patent/US10372917B1 ## CPC - G06F 21/602: {Providing cryptographic facilities or services} - G06F 16/9024: {Graphs; Linked lists (G06F16/9027 takes precedence)} - G06F 16/9027: {Trees} - G06F 21/64: Protecting data integrity, e.g. using checksums, certificates or signatures - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract Aspects of the disclosure relate to hierarchical data structures. A method is disclosed for storing data in a hierarchical data structure. The method may include receiving first data to be committed in a distributed database, the first data including one or more data elements. A result of the selection function may be computed, applying the selection function to each of the one or more data elements. A first node of a first hierarchical data structure may be identified based on the result of the selection function applied to a first data element. The first node of the first hierarchical data structure may be updated using the first data element. ## Claims ### Claim 1 A method, comprising: receiving, at a first computing device, first data to be committed in a distributed database, the first data including one or more data elements; computing, with one or more processors, a result of a selection function applied to each of the one or more data elements; identifying, with the one or more processors, based on the result of the selection function for a first data element, a first node of a first hierarchical data structure maintained by the first computing device, wherein the hierarchical data structure is a B-tree including a plurality of different nodes arranged in a plurality of different levels; and updating, with one or more processors, the first node of the first hierarchical data structure using the first data element; identifying, with the one or more processors, based on the result of the selection function for a second data element, a second node of the first hierarchical data structure maintained by the first computing device; updating, with one or more processors, the second node of the first hierarchical data structure using the second data element; wherein the first hierarchical data structure has the same internal nodes and node representation regardless of the order of updates of the first and second data elements. ### Claim 2 (depends on 1) The method of claim 1, wherein the selection function includes a cryptographic hash function. ### Claim 3 (depends on 2) The method of claim 2, wherein the cryptographic hash function is selected based on a probable output of the cryptographic hash function when applied to each data element. ### Claim 4 (depends on 1) The method of claim 1, wherein updating the first node of the first hierarchical data structure comprises adding the first data element. ### Claim 5 (depends on 4) The method of claim 4, wherein identifying the first node of the first hierarchical data structure further comprises: finding, with the one or more processors, a leaf node in the first hierarchical data structure where the leaf node is within a branch where the first data element is to be added; determining, with the one or more processors, based on the result of the selection function for the first data element, whether the first data element should be added to the leaf node; when the first data element should be added to the leaf node, adding the first data element to the leaf node, such that the leaf node is the first node; and when the first data element should not be added to the leaf node, adding the first data element to a parent node of the leaf node and dividing the leaf node in two separate leaf nodes when the leaf node is a grouped node. ### Claim 6 (depends on 5) The method of claim 5, further comprising: when the first data element is added to the parent node, updating the selection function for a level of the hierarchical structure that holds the parent node; determining, with one or more processors, based on an updated result of the updated selection function for the first data element, whether the first data element should be moved to a grandparent node; and when the first data element should be moved to a grandparent node, moving, with the one or more processors, the first data element to a grandparent node and dividing the parent node in two separate parent nodes when the parent node is a grouped node. ### Claim 7 (depends on 1) The method of claim 1, wherein updating the first node of the first hierarchical data structure comprises removing an existing element. ### Claim 8 (depends on 7) The method of claim 7, wherein identifying the first node of the first hierarchical data structure further comprises: searching, with the one or more processors, the existing element in the first hierarchical data structure; merging, with the one or more processors, elements of a child node of the existing element with elements of another existing child node; and removing, with the one or more processors, the existing element from the first hierarchical data structure. ### Claim 9 (depends on 8) The method of claim 8, wherein merging comprises grouping elements of the child node of the existing element together with elements of the another existing child node. ### Claim 10 (depends on 9) The method of claim 9, wherein merging further comprises additional merging of a grandchild node of the existing element with elements of another existing grandchild node. ### Claim 11 (depends on 1) The method of claim 1, further comprising: receiving, at a second computing device, the first data to be committed in the distributed database; computing, with one or more second processors at the second computing device, the result of the selection function applied to each of the one or more data elements; identifying, with the one or more second processors, based on the result of the selection function for the first data element; a first node of a second hierarchical data structure maintained by the second computing device; updating, with the one or more second processors, the first node of the second hierarchical data structure using the first data element; identifying, with the one or more second processors, based on the result of the selection function for the second data element, a second node of the second hierarchical data structure maintained by the second computing device; and updating, with one or more second processors, the second node of the second hierarchical data structure using the second data element; wherein the first hierarchical data structure and the second hierarchical data structure have the same node representation regardless of the order of insertion of the first and second data elements into each data structure. ### Claim 12 A method, comprising: receiving, with one or more processors, data including one or more data elements; and constructing, with the one or more processors, a first level of a hierarchical data structure using the one or more data elements, wherein the hierarchical data structure is a B-tree including a plurality of different nodes arranged in a plurality of different levels, the constructing comprising: placing, with the one or more processors, the one or more data elements on the first level of the hierarchical data structure; computing, with the one or more processors, a result of a selection function applied to each one of the one or more data elements; moving, with the one or more processors, based on the result of the selection function for a given data element, the given data element to a second level of the hierarchical data structure; when more than one child data elements having a value less than the given data element remain in the first level of the hierarchical data structure, grouping, in a first grouped node, the child data elements; determining, with the one or more processors, based on the result of the selection function for an additional data element on the first level, whether the additional data element should be moved to the second level of the hierarchical data structure; wherein the hierarchical data structure has the same internal nodes and node representation regardless of the order of moving the given data element and the additional data element. ### Claim 13 (depends on 12) The method of claim 12, wherein the selection function is different for each level of the hierarchical data structure. ### Claim 14 (depends on 12) The method of claim 12, wherein the selection function includes a cryptographic hash function. ### Claim 15 (depends on 12) The method of claim 12, further comprising: when the additional data element should be moved to the second level of the hierarchical data structure, then: moving, with the one or more processors, the additional data element to the second level of the hierarchical data structure; and when more than one additional child data elements having a value less than the additional data element remain in the first level of the hierarchical data structure, grouping, in an additional grouped node, the additional child data elements; and when more than one additional child data elements having a value greater than the additional data element remain in the first level of the hierarchical data structure, grouping, in another grouped node, the additional child data elements. ### Claim 16 (depends on 15) The method of claim 15, further comprising: when the additional data element should not be moved to the second level of the hierarchical data structure, then: when more than one additional child data elements having a value greater than a last data element on the second level of the hierarchical data structure remain in the first level of the hierarchical data structure, grouping, in a further grouped node, the additional child data elements. ### Claim 17 (depends on 15) The method of claim 15, further comprising: determining, with the one or more processors, whether one or more second level data elements exist on the second level of the hierarchical data structure; when the one or more second level data elements exist, then: updating, by the one or more processors, the selection function for the second level of the hierarchical data structure; computing, with the one or more processors, an updated result of the selection function applied on the one or more second level data elements; moving, with the one or more processors, based on the updated result of the updated selection function for a given second level data element, the given second level data element to a next level of the hierarchical data structure; and when more than one second level child data elements having a value less than the given second level data element remain in the second level of the hierarchical data structure, grouping, in a second level grouped node, the second level child data elements. ### Claim 18 A system, comprising: one or more memories of a first computing device storing a first hierarchical data structure, wherein the first hierarchical data structure is a B-tree including a plurality of different nodes arranged in a plurality of different levels; one or more processors in communication with the one or more memories, the one or more processors configured to: receive first data to be committed in a distributed database, the first data including one or more data elements; compute a result of a selection function applied to each of the one or more data elements; identify, based on the result of the selection function for a first data element, a first node of the first hierarchical data structure; update the first node of the first hierarchical data structure using the first data element; identify, based on the result of the selection function for a second data element, a second node of the first hierarchical data structure maintained by the first computing device; updating, with one or more processors, the second node of the first hierarchical data structure using the second data element; wherein the first hierarchical data structure has the same internal nodes and node representation regardless of the order of updates of the first and second data elements. ### Claim 19 (depends on 18) The system of claim 18, wherein the selection function is selected based on a probable output of the selection function when applied to the data elements. ### Claim 20 (depends on 18) The system of claim 18, further comprising: a second computing device, comprising: one or more second memories; one or more second processors in communication with the one or more second memories, wherein the one or more second processors are configured to: receive the first data to be committed in the distributed database; compute the result of the selection function applied to each of the one or more data elements; identify, based on the result of the selection function for the first data element; a first node of a second hierarchical data structure maintained by the second computing device; update the first node of the second hierarchical data structure using the first data element; identify, based on the result of the selection function for the second data element, a second node of the second hierarchical data structure maintained by the second computing device; and update the second node of the second hierarchical data structure using the second data element; wherein the first hierarchical data structure and the second hierarchical data structure have the same node representation regardless of the order of insertion of the first and second data elements into each data structure.