Database system with improved methods for B-tree maintenance

Details Database system with improved methods for B-tree maintenance Database system with improved methods for B-tree maintenance

1995-06-28

1997-07-01

Black, Thomas G.

395611, G06F 1730

Patent

active

056447639

ABSTRACT:
Database system and methods are described for maintenance of B-Tree indexes, such as are commonly used in a relational database environment. "Load patterns" are monitored, for optimizing B-Tree node splitting, based on a particular load pattern's effect on B-Tree growth. More particularly, an "ascending insert" load pattern--that is, the insertion of data records for a multi-column table where the particular records to be inserted have a fixed value for the first column and a monotonically increasing value for the subsequent column(s)--can be identified and optimized. Methods are described for splitting the B-Tree nodes or pages, not at the half-way point, but instead exactly at the point of insertion, a position where the insert row would have gone into the page (had it not overflowed). Since splitting the index nodes or pages at the insertion point all the time would lead to regression in performance (particularly for random inserts), the methods of the present invention further include steps for testing conditions which should preferably exist before pages are split at insertion points.

REFERENCES:
patent: 4606002 (1986-08-01), Waisman et al.
patent: 4677550 (1987-06-01), Ferguson
patent: 4791561 (1988-12-01), Huber
patent: 4805099 (1989-02-01), Huber
patent: 4947320 (1990-08-01), Crus et al.
patent: 5089952 (1992-02-01), Bozman
patent: 5123104 (1992-06-01), Levine et al.
patent: 5163148 (1992-11-01), Walls
patent: 5204958 (1993-04-01), Cheng et al.
patent: 5265244 (1993-11-01), Ghosh et al.
patent: 5430869 (1995-07-01), Ishak et al.
Comer, d., "The Ubiquituos B-Tree", Computing Surveys, pp. 121-137 Jun. 1979.
Stevens, A., Hypertree: A Hypertext Index Technique, Dr. Dobb's Journal, Jun. 1990, pp. 135-136, 138-140, 154, 156-159.
Baker, M., B-tree indexing, A look at indexing tradeoffs in dBASE, Clipper, and FoxPro, Programmer's Journal, Nov./Dec. 1990, pp. 42-46.
Ferguson, D., Bit-Tree, Communications of the ACM, Jun. 1992, pp. 115-120.
Williams, W., Supercharging Sequential Searches, Speed plus compression equals faster searches, Dr. Dobb's Journal, Dec. 1990, pp. 54-61.

Affiliated with

Also associated with

Rating

Database system with improved methods for B-tree maintenance does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Database system with improved methods for B-tree maintenance, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Database system with improved methods for B-tree maintenance will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-606348