Optimal reorganization of a B-tree

Details Optimal reorganization of a B-tree Optimal reorganization of a B-tree

1993-09-17

1995-08-29

Black, Thomas G.

Boots, shoes, and leggings

395427, 36441919, 364974, 364975, 3642821, 3642823, 364DIG1, 364DIG2, G06F 1730

Patent

active

054468876

ABSTRACT:
A B-tree optimizer mechanism is provided for optimizing a B-tree stored in a storage device of a computer system. The B-tree optimizer monitors the type and amount of activity occurring within the B-tree. Based upon the type and amount of activity, the B-tree optimizer determines whether the B-tree should be reorganized. When it is determined that the B-tree should be reorganized, the B-tree optimizer computes an optimal fill factor for the pages within the B-tree, and reorganizes the B-tree by filling each page with key values according to the optimal fill factor.

REFERENCES:
patent: 5058002 (1991-10-01), Nakamura et al.
patent: 5089952 (1992-02-01), Bozman
patent: 5204958 (1993-03-01), Cheng et al.
patent: 5218696 (1993-06-01), Baird et al.
patent: 5261088 (1993-11-01), Baird et al.
Douglas Comer, "The Ubiquitous B-Tree", ACM Computing Surveys, vol. 11, No. 2, Jun. 1979, pp. 121-137.
Cesarini et al., "Binary tree Paging", Information Systems, vol. 7, No. 4, 1982, pp. 337-344.
Spirn et al., "Memory Management for B-Trees", Performance Evaluation An International Journal, vol. 5, 1985, pp. 159-174.
Roy Duncan, "Design Goals of the New High Performance File System", Microsoft Systems Journal, vol. 4, No. 5, Sep. 1989, p. 13.
Jim Powell, "B-tree Filer v. 5.0", Computer Language, vol. 7, No. 1, p. 99.
Tim Parker, "Off the Shelf: B-tree Data File Managers", Unix Review, vol. 9, No. 3, Mar. 1991, pp. 55-57.
Johnson et al., "Free-At-Empty is Better Than Merge-At-Half", Dr. Doobs Journal, vol. 7, No. 1, pp. 44-46.
David Snellen, "Ingres Table Structure", DBMS, vol. s, No. 8, Jul. 1992, pp. 60-62.
Sullivan et al., "An Index Implementation Supporting Fast Recovery for The POSTGRES Storage System", Eighth International Conference on Data Engineering, 2-3, Feb., 1992, pp. 293-300.
"Collecting Bucket Index Statistical Data with Colocation Considered," IBM Technical Disclosure Bulletin, Armonk, N.Y., 36(5) May 1993, pp. 1-2.
Haq, E. et al., "New Algorithms for Balancing Binary Search Trees," in IEEE Southeastcon, Knoxville, Tenn., Apr. 11-13, 1988, pp. 378-382.
Motzkin, D., "Database Performance Optimization," in AFIPS 1985 National Computer Conference Proceedings, Chicago, Ill., Jul. 15-18, 1985, pp. 555-560, FIGS. 2-5.

Affiliated with

Also associated with

Rating

Optimal reorganization of 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 Optimal reorganization of a B-tree, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimal reorganization of a B-tree will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-1827134