System and method for restructuring a B-Tree

Details System and method for restructuring a B-Tree System and method for restructuring a B-Tree

1991-05-29

1995-07-04

Black, Thomas G.

Boots, shoes, and leggings

395500, 395725, 364DIG1, G06F 700, G06F 1206

Patent

active

054308690

ABSTRACT:
A database management system and method which permit a B-Tree to be concurrently traversed for the purpose of reading while the B-Tree is actually in the process of restructuring. The present system and method support node splitting for expansion of the B-Tree. The present system and method also support node deletion. A set of update transactions are required to carry out the node-splitting/expansion process. A separate set of steps are required to carry out the node deletion process. The B-Tree can be accessed by readers while either node splitting or deletion occurs, because of the ordering of the process steps. The ordering of the node-splitting and node deletion processes modifies the B-Tree and permit concurrent data readout in an efficient manner. Hence, readers are not required to hold a tree latch or poll for potential in-progress restructuring.

REFERENCES:
patent: 4606002 (1986-08-01), Waisman et al.
patent: 5089952 (1992-02-01), Bozman
patent: 5119490 (1992-06-01), Kurose
patent: 5163148 (1992-11-01), Walls
"Concurrency of Operations on B-Trees", by Bayer et al., Acta Information, vol. 9, No. 1, pp. 1-21, 1977.
"The Ubiquitous B-Tree", by D. Comer, Computing Surveys, vol. 11, pp. 121-137, No. 2, Jun. 1979.
"Efficient Locking for Concurrent Operations on B-Trees" by Lehman et al., ACM Transactions on Database Systems, vol. 6, No. 4., Dec. 1981, pp. 650-670.
"Semantically-based Concurrency Control for Search Structures", Shasha et al., Ph.D. Thesis, 1985.
"Concurrent Search Structure Algorithms", Shasha et al., ACM Transactions on Database Systems, vol. 13, No. 1, pp. 53-90, Mar. 1988.
"Concurrent Use of B-Trees with Variable-Length Entries", Keller et al., Sigmod Record, vol. 17, No. 2, pp. 89-90, Jun. 1988.
"ARIES/IM: An Efficient and High Concurrency Index Management Method Using Write-Ahead Logging", Mohan et al., IBM Research Report, Aug. 29 1989, pp. 1-59.

Affiliated with

Also associated with

Rating

System and method for restructuring a B-Tree does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with System and method for restructuring a B-Tree, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for restructuring a B-Tree will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-767792