Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2006-02-28
2006-02-28
Mizrahi, Diane (Department: 2165)
Data processing: database and file management or data structures
Database design
Data structure types
Reexamination Certificate
active
07007027
ABSTRACT:
An information management system includes a computer and a database comprising a B-Tree data structure comprising a plurality of nodes associated with disk blocks and handles stored in the nodes. At least one left-link handle, hleft, stored in each node points to a left sibling of that node. A mechanism for performing a lookup operation with respect to a key, k, traverses the B-Tree and refers to the left-link handle, hleft, of a node to access a left sibling of the node if the key k is less than or equal to a value kminstored in the node. Mechanisms are also provided for performing insert and delete operations, and the lookup, insert, and delete operations detect if the key range of an index node, A, does not include the key k that the operation is trying to locate, and follow a handle A.hleftto the left sibling when k≦A.kmin.
REFERENCES:
Sagiv, Y. “Concurrent Operations on B*-Trees with Overtaking”, 1986, Joural of Computer Science, vol. 33, pp. 275-296.
Shimin Chen, “Fractal prefetching B*-Trees: optimizing both cache and disk performance”, 2002, ACM Press, N.Y., N.Y., pp. 157-168.
Antoshenkov, G., “Random Sampling from Pseudo-Ranked B+ Trees,”VLDB, 1992, 375-382.
Arnow, D.M. et al., “An Empirical Comparison of B-Trees, Compact B-Trees and Multiway Trees,”SIGMOD Conference, 1984, 33-46.
Baeza-Yates, R.A. et al., “Performance of B+-Trees with Partial Expansions,”TKDE, 1989, 1(2), 248-257.
Baeza-Yates, R.A., “An Adaptive Overflow Technique for B-Trees,”EDBT, 1990, 16-28.
Baeza-Yates, R.A., “Modeling Spits in File Structures,”Acta Informatica, 1989, 26(4), 349-362.
Baeza-Yates, R.A., “The Expected Behavior of B+-Trees,”Acta Informatica, 1989, 26(5), 439-471.
Bayer, R. et al., “Concurrency of Operations on B-trees,”Acta Informatica, 1977, 9, 1-21.
Bayer, R. et al., “Organization and Maintenance of Large Ordered Indexes”,Acta Informatica, 1972, 1, 173-189.
Bayer, R. et al., “Prefix B-Trees,”TODS, 1977, 2(1), 11-26.
Biliris, A., “A Comparative Study of Concurrency Control Methods in B-Trees,”Aegean Workshop on Computing, 1986, 305-316.
Biliris, A., “Operation Specific Locking in B-Trees,”PODS, 1987, 159-169.
Boswell, W. et al., “Alternatives to the B+-Trees,”ICCI, 1990, 266-274.
Chu, J-H. et al., “AN Analysis of B-Trees and Their Variants,”IS, 1989, 14(5), 359-370.
Comer, D., “The Ubiquitous B-Tree”,Computing Surveys, Jun. 1979, 11(2), 121-137.
Diehr, G. et al., “Optimal Pagination of B-Trees with Variable-Length Items,”CACM, 1984, 27(3), 241-247.
Eisenbarth, B. et al., “The Theory of Fringe Analysis and its Application to 2-3 Trees and B-Trees,”Information and Control, 1982, 55(1-3), 125-174.
Eiter, T. et al., “Sperrverfahren fur B-Baume im Vergleich,”Informatik Spektrum, 1991, 14(4), 183-200.
Ellis C., “Concurrent Search and Insertion in 2-3 trees,”Acta Informatica, 1980, 14,63-86.
Faloutsos, C. et al., “On B-Tree Indices for Skewed Distributions,”VLDB, 1992, 363-374.
Ferguson, D.E., “Bit-Tree, A Data Structure for Fast File Processing,”CACM, 1992, 35(6), 114-120.
Fu, A. et al., “Concurrency Control of Nested Transactions Accessing B-Trees”,ACM, 1989, 270-285.
Fujimura, K. et al., “On Robustness of B-Trees,”TKDE, 1993, 5(3), 530-534.
Goh, C.H. et al., “Indexing Temporal Data Using Existing B+-Trees,”DKE, 1996, 18(2), 147-165.
Goodman, N. et al., “Semantically-based Concurrency Control for Search Structures,”Principles Of Database Systems, 1985, 8-19.
Gupta, G.K., “A Self-Assessment Procedure Dealing with Binary Trees and B-Tress,”Communications of the ACM, 1984, 27(5), 435-443.
Gupta, U.I. et al., “Ranking and Unranking of B-Trees,”Journal of Algorithms, 1983, 4(1), 51-60.
Hardjono, T. et al., Search Key Substitution in the Encipherment of B-Trees,VLDB, 1990, 50-58.
Held, G. et al., “B-Trees Re-Examined,”Communications of the ACM, 1978, 21(2), 139-143.
Hellerstein, J.M. et al., “Generalized Search Trees for Database Systems,”VLDB, 1995, 1-12.
Ishak, R., “Semantically Consistent Schedules for Efficient and Concurrent B-Tree Restructuring,”ICDE, 1992, 184-191.
Jannink, J., “Implementing Deletion in B+-Trees,”SIGMOD Record, 1995, 24(1), 33-38.
Johnson, T. et al., “A Framework for the Performance Analysis of Concurrent B-Tree Algorithms,”PODS, 1990, 273-287.
Johnson, T. et al., “B-Trees with Inserts and Deletes: Why Free-at-Empty is Better than Merge-at-Half,”Journal of Computer and System Sciences, 1993, 47(1), 45-76.
Johnson, T. et al., “The Performance of Current B-Tree Algorithms,”ACM Transactions On Database Systems, 1993, 18(1), 51-101.
Johnson, T. et al., “Utilization of B-Trees with Inserts, Deletes and Modifies,”PODS, 1989, 235-246.
Keller, A.M. et al., “Concurrent Use of B-Trees with Variable-Length Entries,”SIGMOD Record, 1988, 17(2), 89-90.
Kersten, M. et al., “Application of an Optimistic Concurrency Control Method,”Software Practice and Experience, 1984, 14(2), 153-168.
Kuspert, K., “Storage Utilization in B*-Trees with a Generalized Overflow Technique,”Acta Informatica, 1983, 19, 35-55.
Kwong, Y. et al., “A New Method for Concurrency in B-Trees,”IEE Transaction on Software Engineering, 1982, 8(3), 211-222.
Kwong, Y. et al., “Approaches to Concurrency in B-trees,”MFCS, 1980, 402-413.
Kwong, Y. et al., “Concurrent Operations in Large Ordered Indices,”Lecture Notes in Computer Science, 1980, 83, 207-222.
Kwong, Y-S. et al., “On B-Trees: Routing Schemes and Concurrency,”SIGMOD Conference, 1980, 207-213.
Langenhop, C. et al., “A Model of the Dynamic Behavior of B-Trees,”Acta Informatica, 1989, 27(1), 41-59.
Lanin, V. et al., “A Symmetric Concurrent B-Tree Algorithm,”FJCC, 1986, 380-389.
Lanka, S. et al., “Fully Persistent B+-Trees,”SIGMOD Conference,1991, 426-435.
Lausen, G., “Integrated Concurrency Control Shared B-Trees,”Computing, 1984, 33(1), 13-26.
Lehman, P.L. et al., “Efficient Locking for Concurrent Operations on B-Trees”,ACM Transactions on Database Systems, Dec. 1981, 6(4), 650-670.
Leung, C., “Approximate Storage Utilisation of B-Trees: A Simple Derivation and Generalisation,”Information Processing Letters, 1984, 19(4), 199-201.
Lomet, D.B. et al., “Access Method Concurrency with Recovery,”SIGMOD Conference,, 1992, 351-360.
Lomet, D.B., “Multi-Table Search for B-Tree Files,”SIGMOD Conference, 1979, 35-42.
Lomet, D.B., “Partial Expansions for File Organizations with an Index,”ACM Transactions on Database Systems, 1987, 12(1), 65-84.
Lum, V.Y., “Multi-Attribute Retrieval with Combined Indexes,”Communications of the ACM, 1970, 13(11), 660-665.
Maelbrancke, R. et al., “Optimizing Jan Jannink's Implementation of B+-Tree Deletion,”SIGMOD Record, 1995, 24(3), 5-7.
McCreight, E.M., “Pagination of B*-Trees with Variable-Length Records,”Communications of the ACM, 1977, 20(9), 670-674.
Mohan, C. et al., “Algorithms for Creating Indexes for Very Large Tables Without Quiescing Updates,”SIGMOD Conference, 1992, 361-370.
Mohan, C. et al., “ARIES/IM: An Efficient and High Concurrency Index Management Method Using Write-Ahead Logging,”SIGMOD Conference, 1992, 371-380.
Mohan, C., “ARIES/KVL: A Key-Value Locking Method for Concurrency Control of Multiaction Transactions Operating on B-Tree Indexes,”Proceedings of the 16thVLDB Conference, 1990, 392-405.
Mond, Y. et al., “Concurrency Control in B-Trees+-Trees Database Using Preparatory Operations,”VLDB, 1985, 331-
Najork Marc A.
Thekkath Chandramohan A.
Microsoft Corporation
Mizrahi Diane
Woodcock & Washburn LLP
LandOfFree
Algorithm for tree traversals using left links does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Algorithm for tree traversals using left links, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Algorithm for tree traversals using left links will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3710276