US5806065A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Data system with distributed tree indexes and method for maintaining the indexes
Assignee: Microsoft Technology Licensing LLC
•
Filing: 1996-05-06
•
Granted: 1998-09-08
•
Expires: 2016-05-06
Abstract
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.
Inventors
- 👤 David B. Lomet
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-05 21:15
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/20; G06F16/22; G06F16/2228; G06F16/2246; G06F16/27; Y; Y10; Y10S; Y10S707/00; Y10S707/964; Y10S707/966; Y10S707/99931; Y10S707/99933; Y10S707/99938
Claims Analysis
Total Claims: 27
Claim 1
Independent Claim
115 words
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.
Claim 2
Dependent Claim
115 words
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.
Claim 3
Dependent Claim
17 words
A computer-implemented method as recited in claim 1 wherein the index tree structure comprises a Pi-tree index.
Claim 4
Dependent Claim
35 words
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.
Claim 5
Dependent Claim
26 words
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.
Claim 6
Dependent Claim
19 words
A computer-readable medium which directs a computer to perform the steps in the method as recited in claim 1.
Claim 7
Dependent Claim
15 words
A computer programmed to perform the steps in the method as recited in claim 1.
Claim 8
Dependent Claim
17 words
A tree index formed in memory as a result of the computer-implemented method recited in claim 1.
Claim 9
Dependent Claim
33 words
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.
Claim 10
Dependent Claim
113 words
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.
Claim 11
Dependent Claim
113 words
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.
Claim 12
Dependent Claim
171 words
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.
Claim 13
Dependent Claim
171 words
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.
Claim 14
Dependent Claim
17 words
A data system as recited in claim 10 wherein the tree index file structure comprises a Pi-tree.
Claim 15
Dependent Claim
38 words
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.
Claim 16
Dependent Claim
26 words
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.
Claim 17
Dependent Claim
187 words
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.
Claim 18
Dependent Claim
187 words
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.
Claim 19
Dependent Claim
88 words
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.
Claim 20
Dependent Claim
145 words
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.
Claim 21
Dependent Claim
70 words
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.
Claim 22
Dependent Claim
34 words
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.
Claim 23
Dependent Claim
225 words
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.
Claim 24
Dependent Claim
225 words
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.
Claim 25
Dependent Claim
76 words
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.
Claim 26
Dependent Claim
19 words
A computer-readable medium which directs a computer to perform the steps in the method as recited in claim 19.
Claim 27
Dependent Claim
16 words
A data server programmed to perform the steps in the method as recited in claim 19.
References Cited (Backward Citations)
US4611272A
Cited
US5293618A
Cited
US5230047A
Cited
US5276872A
Cited
US5717921A
Cited
US5434994A
Cited
US5606669A
Cited
US5642501A
Cited
US5581765A
Cited
US5581753A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-09-07 | 2002-03-09 | 2002-09-08 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-09-07 | 2006-03-09 | 2006-09-08 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-09-07 | 2010-03-09 | 2010-09-08 | $7700.00 | Window Closed / Lapsed |