Data system with distributed tree indexes and method for maintaining the indexes
First Claim
1. In a data management computing system having data organized according to a tree index structure and supporting access to that data from multiple processing units through a distributed tree index architecture where at least a portion of the tree index is provided at the multiple processing units, a computer-implemented method for maintaining the tree indexes at the multiple processing units comprising the following steps:
- accessing the data from the processing units using their corresponding tree indexes;
during said access by one of the processing units, changing a storage location of a particular search space; and
updating the tree index at said one processing unit without updating the tree indexes at others of the processing units.
2 Assignments
0 Petitions
Accused Products
Abstract
A data system has a data server and multiple clients. The data server organizes data according to a tree index structure, where memory pages used to store data are indexed by higher level index nodes in the tree structure. The index nodes are replicated and maintained locally at the clients. The data organization on the server is further characterized by use of indexed side links between data pages to provide side access traversal, such as a Pi-tree structure. During a search for a particular search space, a requesting client traverses its own index replica until reference is made to a data page at the server. If the request causes a data page split or otherwise changes the storage location of a particular search space, the server sends information back as part of the result message to the requesting client to update the tree index replica. However, no coherence messages are sent to other clients. Instead, the other clients learn of data page splits and other changes to the search space in their own time when they request the search space. When a second client tries to access a search space that has changed due to activity of the first client, the second client is initially directed to the data page it expects to contain the search space. The server then side traverses the data pages using the indexed side links until the actual data page with the search space is located. Each side traversal results in its index term being included in the result message. Such index terms, when received at the index replica, are posted in the replica maintained at the second client to update that index replica. Accordingly, replicas are maintained as a by product of their individual search requests, thereby removing the need for coherence or other coordination messages among all index replicas.
-
Citations
22 Claims
-
1. In a data management computing system having data organized according to a tree index structure and supporting access to that data from multiple processing units through a distributed tree index architecture where at least a portion of the tree index is provided at the multiple processing units, a computer-implemented method for maintaining the tree indexes at the multiple processing units comprising the following steps:
-
accessing the data from the processing units using their corresponding tree indexes; during said access by one of the processing units, changing a storage location of a particular search space; and updating the tree index at said one processing unit without updating the tree indexes at others of the processing units. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8)
-
-
9. In a data system constructed according to a Pi-tree file structure having indexes replicated over multiple computing sites, an index maintenance manager stored in a storage medium and executable on a processor to perform the following steps:
-
creating an indexed side link, in response to a data node split caused by a request from a particular computing site, to connect an old data node to a new data node formed in the split; constructing a message containing index terms indicative of the created indexed side link; and sending the message to the requesting computing site to update the index maintained at the requesting computing site without sending similar messages to other computing sites.
-
-
10. A data system comprising:
-
a database configured in a tree index file structure having data nodes representative of memory pages used to store data and index nodes representative of memory pages used to store information to index the memory pages, the tree index file structure being characterized by use of indexed side links between data nodes to permit side traversal from one memory page to the next; multiple client processing units connected to access the data on the database, the index nodes being at least partially replicated and maintained locally at the client processing units; individual ones of the client processing units being capable of independently manipulating the data on the database in a manner which changes a storage location of particular data; in an event one of the client processing units causes a storage location change, the database providing update information to update the index nodes at said one client processing unit to reflect the storage location change without providing the update information to others of the client processing units. - View Dependent Claims (11, 12, 13)
-
-
14. In a distributed data management system having data distributed over multiple computing sites and organized in a tree index structure having index nodes to direct access to the data, the data being stored on memory pages that are connected by indexed side links to direct side access traversal from one memory page to the next, the distributed data management system further having multiple client processing units capable of accessing the distributed data on the different sites using replicas of the index nodes maintained locally at the client processing units, a computer-implemented method for managing the data distribution among the multiple sites comprising the following steps:
-
identifying an existing data page at a first site; creating a new data page at a second site; transferring at least some of the data from the existing data page at the first site to the new data page at the second site; deleting the existing data page at the first site; and individually updating each tree index replica at a client processing unit as that processing unit accesses the transferred data without updating the tree index replicas at other processing units. - View Dependent Claims (15, 16, 17, 18)
-
-
19. In a data management system having a data server supporting multiple client processing units, the data server storing data in a tree index structure having index nodes to direct access to the data, the data being stored on memory pages that are connected by indexed side links to direct side access traversal from one memory page to the next and the index nodes being replicated and maintained at the client processing units, a computer-implemented method comprising the following steps:
-
receiving a request at the data server from a client processing unit, the request identifying a type of action and a data page expected to contain a search space to be affected by the action; in an event that the data page identified in the request contains the search space, performing the action; in an event that the data page identified in the request does not contain the search space, side traversing from the identified data page using the indexed side links to an actual page which contains the search space; constructing a message containing index terms indicative of each indexed side link traversed; and sending the message and request results back to the client processing unit that originated the request to update the index nodes maintained on the client processing unit without sending similar messages to other computing sites that did not originate the request. - View Dependent Claims (20, 21, 22)
-
Specification