Data system with distributed tree indexes and method for maintaining the indexes

• US 5,806,065 A
• Filed: 05/06/1996
• Issued: 09/08/1998
• Est. Priority Date: 05/06/1996
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Lomet, David B.
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): RONES, CHARLES
• Application Number:
  US08/642,764
• Time in Patent Office: 855 Days
• Field of Search: 395/617, 395/677, 395/200.53, 395/182.02, 707/8, 707/3, 707/202, 711/130
• US Class Current: 707/610
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/27 Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor
• CPC Class Codes: Y10S 707/966 Distributed
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99938 Concurrency, e.g. lock management in shared database

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.

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.

2. A computer-implemented method as recited in claim 1 wherein the index tree structure comprises a Pi-tree index.

3. A computer-implemented method as recited in claim 1 further comprising the step of updating the tree index of said other processing units individually as each of said other processing units access the changed storage location.

4. A computer-implemented method as recited in claim 1 further comprising the step of sharing the tree index of a different processing unit to access the data.

5. A computer-readable medium which directs a computer to perform the steps in the method as recited in claim 1.

6. A computer programmed to perform the steps in the method as recited in claim 1.

7. A tree index formed in memory as a result of the computer-implemented method recited in claim 1.

8. A computer-implemented method as recited in claim 1 further comprising the step of enabling the tree indexes of the processing units to evolve independently of one another without converging to one common form.

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.

11. A data system as recited in claim 10 wherein the tree index file structure comprises a Pi-tree.

12. A data system as recited in claim 10 wherein the database provides update information to update the index nodes at said other client processing units as each of said other client processing units accesses the changed storage location.

13. A data system as recited in claim 10, wherein the index nodes are free to evolve independently of one another without converging to one common form.

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.

15. A computer-implemented method as recited in claim 14 wherein the creating step comprises the following three steps which are performed as a single atomic action:

allocating the new data page in memory at the second site;

storing at least some of the data from the existing data page onto the new data page; and

updating the existing data page by removing that data that is now stored on the new data page and creating an indexed side link from the existing data page to the new data page.

16. A computer-implemented method as recited in claim 14 wherein the creating step comprises the following steps:

allocating the new data page in memory at the second site;

storing at least some of the data from the existing data page onto the new data page;

sending a message from the second site to the first site notifying the first cite that the existing page has been split and an address to the new data page, the message containing commit coordination;

updating the existing data page by removing that data that is now stored on the new data page and creating an indexed side link from the existing data page to the new data page;

committing atomically at the first site; and

upon receipt at the second site of a new access request for the data on the new data page, committing atomically at the second site.

17. A computer-implemented method as recited in claim 14 wherein the deleting step comprises the following steps which are performed as a single atomic action:

posting the indexed side link supported by the deleted data page to a containing data page that contains an indexed side link to the deleted data page; and

establishing a marker representative of the deleted data page containing a forwarding address to the containing data page.

18. A computer-implemented method as recited in claim 14 further comprising the step of enabling the tree index replicas of the processing units to evolve independently of one another without converging to one common form.

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.

20. A computer-implemented method as recited in claim 19 wherein the action comprises an update action to store more data, comprising the following additional steps:

causing, by virtue of storing more data, a split in the data between an existing data page and a new data page;

creating an indexed side link from the existing data page to the new data page; and

adding an index term indicative of the created indexed side link to the message.

21. A computer-readable medium which directs a computer to perform the steps in the method as recited in claim 19.

22. A data server programmed to perform the steps in the method as recited in claim 19.