Deletion and compaction using versioned nodes

Details Deletion and compaction using versioned nodes Deletion and compaction using versioned nodes

2006-07-04

2006-07-04

Mizrahi, Diane (Department: 2165)

Data processing: database and file management or data structures

Database design

Data structure types

Reexamination Certificate

active

07072904

ABSTRACT:
An information management system includes a database comprising a B-Tree data structure. The B-Tree includes a plurality of nodes associated with disk blocks, handles stored in the nodes, and version numbers attached to each of the handles and disk blocks. In addition, the system includes a mechanism for initially assigning each disk block a first prescribed version number (e.g., version number 0), and a mechanism for performing an allocate operation whereby a handle identifying a disk block is returned along with the disk block's version number. The system may also include a mechanism for performing a deallocate operation that increments the disk block's version number, as well as a mechanism for performing a read operation that returns a disk block's version number in addition to the node stored at that disk block. Moreover, a caller of the read operation checks whether the version number returned by the read operation matches the version number of the handle that was read. The caller is preferably restarted if the version numbers do not match, thus indicating that the node has been deleted and subsequently deallocated by a different thread. The caller may be a lookup operation, an insert operation, or a delete operation.

REFERENCES:
patent: 5893086 (1999-04-01), Schmuck et al.
patent: 5960446 (1999-09-01), Schmuck et al.
patent: 5974424 (1999-10-01), Schmuck et al.
patent: 6792432 (2004-09-01), Kodavalla et al.
patent: 2002/0166026 (2002-11-01), Ulrich et al.
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 (considered Abstract Only).
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-Trees,”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, 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 Confernence, 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 Wr

Affiliated with

Also associated with

Rating

Deletion and compaction using versioned nodes does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Deletion and compaction using versioned nodes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Deletion and compaction using versioned nodes will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3553554