Data processing: database and file management or data structures – Database design – Data structure types
Patent
1996-05-06
1998-09-08
Black, Thomas G.
Data processing: database and file management or data structures
Database design
Data structure types
707 3, 711130, 39520053, G06F 1730
Patent
active
058060650
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.
REFERENCES:
patent: 4611272 (1986-09-01), Lomet
patent: 5230047 (1993-07-01), Frey, Jr. et al.
patent: 5276872 (1994-01-01), Lomet et al.
patent: 5293618 (1994-03-01), Tandai et al.
patent: 5434994 (1995-07-01), Shaheen et al.
patent: 5581753 (1996-12-01), Terry et al.
patent: 5581765 (1996-12-01), Munroe et al.
patent: 5606669 (1997-02-01), Bertin et al.
patent: 5642501 (1997-06-01), Doshi et al.
patent: 5717921 (1998-02-01), Lomet et al.
Johnson et al. "A Distributed Data-balance Dictionary Based on the B-link Tree", MIT Laboratory for Computer Science Technical Report MIT/LCS/TR-530, Feb. 1992.
Johnson et al. "Distributed Indicies for Accessing Distributed Data", Twelfth IEEE Symposium on Mass Storage Systems, pp. 199-207, 1993.
Evangelidis, George "The HB Pi-Tree: A Concurrent and Recoverable Multi-Attribute Index Structure", A Thesis:Northeastern Univ., Jun. 1994.
Johnson et al. "Lazy Updates for Distributed Search Structures", University of Florida, pp. 1-21, Dec. 1, 1992.
Evangeldis et al. "Node Deletion in the hB Pi-Tree", pp. 1-15, No date.
Duchamp et al. "An Interface to Support Lazy Replicated File Service", Management of Replicated Data, 192 Workshop, pp. 6-8, 1992.
Ladin et al. "Lazy Replication: Exploiting the Semantics of Distributed Services", Management of Replicated Data, 1990 Workshop, pp. 31-34, 1990.
Matsliach et al. "A Combined Method for Maintaining Large Indicies in Multiprocessor Multidisk Environments", IEEE Transactions on Knowledge and Data Engineering, v6., n3., pp. 479-496, Jun. 1994.
Tait et al. "Service Itnerface and Replica Management Algorithm for Mobile File System Clients", Parallel and Distributed Information Systems, 1991 Int'l Conf., pp. 190-197.
Wiederhold et al. "Consistency Control of Replicated Data In Federated Databases", Management of Replicated Data, Workshop, pp. 130-132, Jul. 1990.
Liebherr et al. "The Effect of Index Partitioning Schemes on the Performance of Distributed Query Processing", IEEE Transactions on Knowledge and Data Engineering, v.5, n3. pp. 510-522, Jun. 1993.
Maass et al. "Replicated Distributed Directory Services for Mobile Commnunications Networks", Serivces in Distributed and Networked Environments, 1994 1st Int'l Workshop, pp. 90-97.
Antoshenkov et al. "Order Preserving String Compression", Data Engineering, 1996 12th International Conference, pp. 655-663.
Lomet, David "Provate Locking and Distributed Cache Management", Parallel and Distributed Information Systems, 1994 Int'l. Conf., p. 151-159.
Lomet, David "Using Timestamps to Optimize Two Phase Commit", Parallel and Distributed Information Systems, 1993 Int'l Conf., pp. 48-55.
Evangeldis et al. "The hB Pi-Tree: A Multi-Attribute Index Supporting Concurrency, Recovery, and Node Consolidation", pp. 1-51, 1993.
Nicklas et al. "A Parallel Solution to the Cutting Stock Problem for a Cluster Workstations", High Performance Distributed Computing, 1996 5th Int'l Symposium, pp. 521-530.
"Silicon Graphics IRIX", Worldwide IT Analyst, pp. 1-13, Mar. 1997.
Carey, M. DeWitt, et al., Object and File Management in the EXODUS Extensible Database System, 12.sup.th Int'l Conference on Very Large Data Bases, (Aug. 1986) pp. 91-100.
Evangelidis, G. et al., The hB-Pi-Tree: A Modified hB-tree Supporting Concurrency, Recovery and Node Consolidation, 21.sup.th VLDB Conference, Zurich, Switzerland, 1995.
Johnson et al., Lazy Updates for Distributed Search Structure, SIGMOD, (May 1993) Washington, D.C., pp. 337-346.
Brigitte Kroll, et al., Distributing a Search Tree Among a Growing Number of Processors, SIGMOD, Minneapolis, MN, 1994, pp. 265-276.
Lehman P., et al., Efficient Locking for Concurrent Operations on B-Trees, AMC Transactions on Database Systems, vol. 6, No. 4, Dec. 1981, pp. 650-670.
Litwin, W., et al., LH*--Linear Hashing for Distributed Files, SIGMOD, 1993, Washington, D.C., pp. 327-336.
Litwin et al., RP*--A Family of Order-Preserving Scaleable Distributed Data Structures, 20.sup.th VLDB Conference, Santiago, Chile 1994, pp. 1-12.
Lomet et al., Access Method Concurrency With Recovery, SIGMOD, May 1992, San Diego, CA, pp. 351-360.
Vingralek, et al., Distributed File Organization With Scalable Cost/Performance, SIGMOD, May 1994, Minneapolis, MN, pp. 253-264.
Devine, R., "Design and Implementation of DDH: A Distributed Dynamic Hashing Algorithm," 4.sup.th Int'l Conf. On Foundations of Data Organization and Algorithms, Oct. 1993, Evanston, Ill.
Black Thomas G.
Microsoft Corporation
Rones Charles L.
LandOfFree
Data system with distributed tree indexes and method for maintai does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Data system with distributed tree indexes and method for maintai, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data system with distributed tree indexes and method for maintai will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-1296318