Distributed indexes

Abstract

Methods are provided of optimizing a tree-structured distributed-index with tree-nodes including data-elements and parent-child relations between tree-nodes. The distributed-index is stored in distributed system including computer-nodes each storing tree-nodes and a tree-map structurally describing the distributed-index. The methods include: inspecting the tree-map in first computer-node to determine whether the distributed-index is imbalanced due to a first tree-node in first computer-node and, in said case: notifying to other computer-nodes that first tree-node is replicable, to provoke that any request from other computer-nodes of inserting a data-element in first-tree-node includes inserting the data-element in corresponding child-node of first-tree-node; and verifying whether the other computer-nodes have been notified and, in said case, replicating data-elements stored in first tree-node into children-nodes thereof. Methods of inserting into and/or querying such distributed indexes or similar are also provided, along with computer programs and (computing) systems that are suitable for performing said optimizing, inserting and querying methods.

The invention claimed is: 
     
       1. A method of optimizing a distributed index having a tree structure comprising a plurality of tree-nodes including a root node, a plurality of non-root nodes and parent-child relations between the tree-nodes;
 the root node covering a D-dimensional space, and each of the non-root nodes covering a part of the D-dimensional space such that each of the non-root nodes with same parent node covers a partition of the whole or part of the D-dimensional space or domain covered by said parent node; 
 at least some of the tree-nodes storing one or more data-elements each having space-coordinates within the whole or part of the D-dimensional space or domain covered by the tree-node in which the data-element is stored; 
 the distributed index being disposed in a distributed system including a plurality of computer-nodes, and each of at least some of the tree-nodes is stored at one of the computer-nodes along with an in-memory map structurally describing the distributed index; the method comprising: 
 inspecting, by a first computer-node in the plurality of computer-nodes, the in-memory map stored at the first computer-node and determining that the distributed index satisfies a storage imbalance condition caused by at least a first tree-node stored in the first computer-node and, in response, triggering a reorganization method including: 
 notifying, by the first computer-node, to the other computer-nodes in the plurality of computer-nodes that the first tree-node is to be replicated, to enforce or provoke that any request from any of the other computer-nodes of inserting a data-element in the first-tree-node further includes inserting the data-element in a child node of the first-tree-node, depending on the space-coordinates of said data-element and the part of the D-dimensional space or domain covered by said child node; and 
 verifying, by the first computer-node, that the other computer-nodes have been notified and, in response, replicating the data-elements stored in the first tree-node into children nodes of the first tree-node depending on the space-coordinates of each of said data-elements and the part of the D-dimensional space or domain covered by each of said children nodes. 
 
     
     
       2. A method according to  claim 1  the space-coordinates of a stored data-element corresponding to spatial coordinates of a key value, unique identifier, or any combination of attributes of the data-element designating or pointing to a particular location in the D-dimensional space. 
     
     
       3. A method according to  claim 1  the notifying to the other computer-nodes that the first tree-node is to be replicated comprises sending, by the first computer-node, a notification to the other computer-nodes indicating that the first tree-node is to be replicated. 
     
     
       4. A method according to  claim 3  the verifying whether the other computer-nodes have been notified includes receiving from the other computer-nodes, by the first computer-node, a reply to the notification indicating that the notification has been received by the other computer-nodes. 
     
     
       5. A method according to  claim 1 , each of the tree-nodes having a real storage capacity and a permissible storage capacity smaller than the real storage capacity; and the determining whether the distributed index satisfies the storage imbalance condition comprises determining, by the first computer-node, whether at least the first tree-node is storing a number of data-elements which is at or exceeds the permissible storage capacity of the first tree-node. 
     
     
       6. A method according to  claim 5  the determining whether at least the first tree-node is storing a number of data-elements which is at or exceeds the permissible storage capacity further comprises determining, by the first computer-node, whether the first tree-node is to be read for replying a read request or query. 
     
     
       7. A method according to  claim 6  the verifying whether the other computer-nodes have been notified further includes determining, by the first computer-node, whether the reading of the first tree-node for replying the read request or query has been completed before the computer-nodes have been notified. 
     
     
       8. A method according to  claim 1  the determining whether the distributed index satisfies the storage imbalance condition comprises:
 determining, by the first computer-node, a difference between replicated and non-replicated tree-nodes at same tree-level within a sub-tree of the tree-structure, and verifying whether said difference exceeds a predefined replication difference threshold. 
 
     
     
       9. A method according to  claim 1 , each of the tree-nodes having a priority range and each of the data-elements having a priority;
 each non-replicated tree-node having its priority range equal to widest range of priorities that are assignable to data-elements to provoke that the priority of any data-element includable in the non-replicated tree-node depending on its space-coordinates, is also within the priority range of the non-replicated tree-node; and 
 the reorganization method further comprising adjusting the priority range of the first tree-node to define which of the data-elements in the tree-node is/are within or outside the permissible storage capacity depending on whether the priority of the data-element is within or outside the priority range of the tree-node. 
 
     
     
       10. A method according to  claim 9 , the priority range including a top-priority defining that the data-elements in the first tree-node with priority below the top-priority is within the permissible storage capacity and, otherwise, is outside the permissible storage capacity. 
     
     
       11. A method according to  claim 10  the adjusting the top-priority comprising:
 sorting the priorities of the data-elements stored in the first tree-node, and selecting a priority from the sorted priorities as the top-priority such that the permissible storage capacity is completed by the data-elements with priority below the top-priority, and the data-elements with priority above the top-priority are outside the permissible storage capacity. 
 
     
     
       12. A method according to  claim 9  the priority range including a bottom-priority defining that the data-elements in the first tree-node with priority above the bottom-priority is within the permissible storage capacity and, otherwise, is outside the permissible storage capacity. 
     
     
       13. A method according to  claim 12  the adjusting the bottom-priority comprising:
 sorting the priorities of the data-elements stored in the first tree-node, and selecting a priority from the sorted priorities as the bottom-priority such that the permissible storage capacity is completed by the data-elements with priority above the bottom-priority, and the data-elements with priority below the bottom-priority are outside the permissible storage capacity. 
 
     
     
       14. A method according to  claim 9  the reorganization method further comprising verifying whether the replication of the first tree-node has been completed and, if so, removing from the first tree-node the data-elements with priority outside the priority range of the first tree-node. 
     
     
       15. A method according to  claim 9  the priority of a data-element being a random or pseudo-random priority; or
 being calculated by applying a hash-function to at least part of the data-element, or 
 being calculated by applying the hash-function to a unique identifier or a key value of the data-element. 
 
     
     
       16. A non-transitory medium comprising a computer program having program instructions for causing a computing system to perform a method according to  claim 1  of optimizing a distributed index. 
     
     
       17. A computing system for optimizing a distributed index, the computing system comprising a memory and a processor, embodying instructions stored in the memory and executable by the processor, the instructions comprising functionality to execute a method according to  claim 1  of optimizing a distributed index. 
     
     
       18. A method of inserting a data-element into a distributed index having a tree structure comprising a plurality of tree-nodes including a root node, a plurality of non-root nodes and parent-child relations between the tree-nodes;
 the root node covering a D-dimensional space, and each of the non-root nodes covering a part of the D-dimensional space such that each of the non-root nodes with same parent node covers a partition of the whole or part of the D-dimensional space or domain covered by said parent node; 
 at least some of the tree-nodes storing one or more data-elements each having space-coordinates within the whole or part of the D-dimensional space or domain covered by the tree-node in which the data-element is stored; 
 the distributed index being disposed in a distributed system including a plurality of computer-nodes, and each of at least some of the tree-nodes is stored at one of the computer-nodes along with an in-memory map structurally describing the distributed index; 
 at least some of the tree-nodes having been replicated into children nodes to compensate or resolve a storage imbalance condition induced at least by said tree-node and to optimize the distributed index; 
 each of at least some of the tree-nodes having a real storage capacity and a permissible storage capacity smaller than the real storage capacity; 
 each of at least some of the tree-nodes having a priority range, and each of at least some of the data-elements having a priority, the priority range defining which of the data-elements stored in the tree-node is/are within or outside the permissible storage capacity depending on whether the priority of the data-element is within or outside the priority range of the tree-node; and said method of inserting a data-element comprising: 
 determining a series of updatable tree-nodes of the tree-nodes having a priority including an initial tree-node, one or more intermediate tree-nodes and a final tree-node; and 
 inserting the data-element into each updatable tree-node that is within the series of updatable tree-nodes and satisfies that priority of the data-element to be inserted is within the priority range of said updatable tree-node; 
 the initial tree-node being a tree-node closest to the root tree-node, satisfying that space-coordinates and priority of the data-element to be inserted are/is within the domain and priority range of said initial tree-node, respectively; 
 the final tree-node being a descendant node of the initial tree-node, satisfying that said final tree-node has not been replicated and space-coordinates of the data-element to be inserted are within the domain of said final tree-node and; 
 each of the one or more intermediate updatable tree-nodes being a descendant node of the initial tree-node and an ancestor node of the final tree-node. 
 
     
     
       19. A method of replying a query by accessing a distributed index having a tree structure comprising a plurality of tree-nodes including a root node, a plurality of non-root nodes and parent-child relations between the tree-nodes;
 the root node covering a D-dimensional space, and each of the non-root nodes covering a part of the D-dimensional space such that each of the non-root nodes with same parent node covers a partition of the whole or part of the D-dimensional space or domain covered by said parent node; 
 at least some of the tree-nodes storing one or more data-elements each having space-coordinates within the whole or part of the D-dimensional space or domain covered by the tree-node in which the data-element is stored; 
 the distributed index being disposed in a distributed system including a plurality of computer-nodes, and each of at least some of the tree-nodes is stored at one of the computer-nodes along with an in-memory map structurally describing the distributed index; 
 at least some of the tree-nodes having been replicated into children nodes to compensate or resolve a storage imbalance condition induced at least by said tree-node and to therefore optimize the distributed index; 
 each of at least some of the tree-nodes having a real storage capacity and a permissible storage capacity smaller than the real storage capacity; 
 each of at least some of the tree-nodes having a priority range, and each of at least some of the data-elements having a priority, the priority range defining which of the data-elements stored in the tree-node is/are within or outside the permissible storage capacity depending on whether the priority of the data-element is within or outside the priority range of the tree-node; 
 the query including a domain scope defining one or more parts of the D-dimensional space to be consulted, and a proportion scope defining a proportional sample of the domain scope; 
 at least some of the tree-nodes having a depth attribute indicating a number of levels of descendant nodes of said tree-node forming together a perfect 2 D -ary tree with said tree-node as root of said perfect 2 D -ary tree; the method of replying a query, or querying method, comprising: 
 determining a tree-node in the tree-structure with smallest domain and best matching the domain scope of the query; 
 verifying whether the best matching tree-node has been replicated and, if so, designating the best matching tree-node as starting node and, otherwise, 
 determining an ancestor node of the best matching tree-node, which is closest to the best matching tree-node and has been replicated, and designating said replicated ancestor node as a starting node; 
 iteratively performing a loop until the proportion scope of the query is fulfilled, the loop comprising: 
 determining a number of tree-levels to be jumped from the/each designated starting node, such that tree-nodes at the tree-level to be jumped to are estimated to include sufficient data-elements to fulfil the proportion scope of the query; 
 determining a minimum value between the number of tree-levels to be jumped and the depth of the starting node; 
 verifying whether said minimum value or minimum jump is greater than the depth of the starting node and, if so, determining descendant nodes of the starting node that are at a distance from the starting node equal to the depth of the starting node and designating said descendant nodes as new starting nodes to initiate a new iteration of the loop for each of said new starting nodes and, otherwise, 
 performing the minimum jump from the starting node to a target tree-level and accessing tree-nodes at said target tree-level; 
 verifying whether the performed accesses have caused fulfilling of the proportion scope of the query and, if so, quitting the loop and, otherwise, designating the accessed tree-nodes as new starting nodes to initiate a new iteration of the loop for each of said new starting nodes.