Hierarchical locking in B-tree indexes

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

2006-10-06

2009-08-18

Le, Debbie M (Department: 2168)

Data processing: database and file management or data structures

Database design

Data structure types

C707S793000, C707S793000

Reexamination Certificate

active

07577658

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.
Patrick O'Neil et al Some Considerations of Locking to Prevent Phantoms, Australia 2006, pp. 1-20.
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 29thVLDB 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 Ubiquitos B-Tree”, ACM Computing Surveys (CSUR), 1979, vol. 11, No. 2.
K.P. Eswaran et al. “The Notions of Consistency Locks 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 18thVLDB Conference, 1992.
Goetz Graefe “B-tree indexes, interpolation search, and skew”, Proceedings of the 2ndInternational 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 30thVLDB 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 17thInternational 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 21stVLDB Conference, 1995.
David B. Lomet “Key Range Locking Strategies for Improved Concurrency”, Proceedings of the 19thVLBD 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 16thVLDB 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-4070629