Hierarchical locking in B-tree indexes

Details Hierarchical locking in B-tree indexes Hierarchical locking in B-tree indexes

2011-05-31

2011-05-31

Le, Debbie (Department: 2168)

Data processing: database and file management or data structures

Data integrity

Concurrent read/write management using locks

C707S797000

Reexamination Certificate

active

07953717

ABSTRACT:
Portions of a B-tree index in a database are locked for concurrency control. In one example, hierarchical lock modes are provided that permit locking a key, a gap between the key and the next key, and a combination of the key and the gap. In another example, key range locking may be applied to the B-tree index using locks on separator keys of index nodes. In another example, key range locking may be applied to the B-tree index using locks on key prefixes.

REFERENCES:
patent: 5440732 (1995-08-01), Lomet et al.
patent: 5960194 (1999-09-01), Choy et al.
patent: 6144983 (2000-11-01), Klots et al.
patent: 7269588 (2007-09-01), Verma et al.
patent: 7321898 (2008-01-01), Luo et al.
patent: 7577658 (2009-08-01), Graefe
Gennady Antoshenkov, et al., “Order Preserving String Compression”, Proceedings of the Twelfth International Conference on Data Engineering, 1996.
Rudolf Bayer, et al., “Prefix B-Trees”, ACM Transactions on Database Systems (TODS), Mar. 1997, vol. 2, Issue 1.
Bishwaranjan Bhattacharjee, et al., “Efficient Query Processing for Multi-Dimensionally Clustered Tables in DB2”, Proceedings of the 29th VLDB Conference, Berlin, Germany, 2003.
Michael J. Carey, “Granularity Hierarchies in Concurrency Control”, Proceedings of the 2nd ACM SIGACT-SIGMOD symposium on Principles of database systems, 1993.
Michael J. Carey, et al., “Storage Management in EXODUS”, Object-Oriented Concepts, Databases and Applications 1989, pp. 341-369.
Douglas Comer, “The Ubiquitous B-Tree”, ACM Computing Surveys (CSUR), 1979, vol. 11, No. 2.
K.P. Eswaran, et al., “The Notions of Consistency Looks in a Database System”, Communications of the ACM, Nov. 1976, vol. 19, No. 11.
Vibby Gottemukkala, et al., “Locking and Latching in a Memory-Resident Database System”, Proceedings of the 18th VLDB Conference, 1992.
Goetz Graefe, “B-tree indexes, interpolation search, and skew”, Proceedings of the 2nd International Workshop on Data Management on New Hardware (DaMoN 2006), Jun. 2006.
Goetz Graefe, “Executing nested Queries”, 2003.
Goetz Graefe, “Sorting and Indexing with Partitioned B-Trees”, Proceedings of the 2003 CIDR Conference, 2003.
Goetz Graefe, et al., “Transaction support for indexed summary views”, SIGMOD 2004, Jun. 2004.
Goetz Graefe, “Write-Optimized B-Trees”, Proceedings of the 30th VLDB Conference, 2004.
Jim Gray, et al., “Granularity of Locks in a Large Shared Data Base”, Proceedings of the International Conference on Very Large Data Bases, 1975.
J.N. Gray, “Notes on Data Base Operating Systems”, IBM Research Laboratory, Lecture Notes in Computer Science, vol. 60, Operating Systems, An Advanced Course, 1978.
Jim Gray, et al., “Transaction Processing: Concepts and Techniques”, 1993, pp. 406-421, 851-876.
J.R. Jordan, et al., “Precision Locks”, Proceedings of the 1981 ACM SIGMOD international conference on Management of data, 1981.
Ashok M. Joshi, “Adaptive Locking Strategies in a Multi-node Data Sharing Environment”, Proceedings of the 17th International conference on Very Large Data Bases, Sep. 1991.
Henry F. Korth, “Locking Primitives in a Database System”, Journal of the ACM (JACM), 1983, vol. 30, Issue 1.
Harry Leslie, et al., “Efficient Search of Multidimensional B-Trees”, Proceedings of the 21st VLDB Conference, 1995.
David B. Lomet, “Key Range Locking Strategies for Improved Concurrency”, Proceedings of the 19th VLDB Conference, 1993.
C. Mohan, et al., “ARIES/IM: An Efficient and High Concurrency Index Management Method Using Write-Ahead Logging”, ACM SIGMOD, 1992.
C. Mohan, “ARIES/KLV: A Key-Value Locking Method for Concurrency Control of Multiaction transactions Operating on B-Tree Indexes”, Proceedings of the 16th VLDB Conference, 1990.
C. Mohan, et al., “ARIES: A Transaction Recovery Method Supporting Fine-Granularity Locking and Partial Rollbacks Using Wrote-Ahead Logging”, ACM Transactions on Database Systems, Mar. 1992, vol. 17, No. 1.
Patrick O'Neil, et al., “Improved Query Performance with Variant Indexes”, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, 1997.
Sriram Padmanabham, “Multi-Dimensional Clustering: A New Data Layout Scheme in DB2”, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, 2003.
Jaideep Srivastava, et al., “A Tree based Access Method (TBSAM) for Fast Proceeding of Aggregate Queries”, Proceedings of the Fourth International Conference on Data Engineering, 1998.

Affiliated with

Also associated with

Rating

Hierarchical locking in B-tree indexes does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Hierarchical locking in B-tree indexes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hierarchical locking in B-tree indexes will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2660214