US5522068A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Statistic-based reorganization of B-trees yielding an approximate optimal fill on substantially every page
Assignee: Microsoft Technology Licensing LLC
•
Filing: 1995-06-01
•
Granted: 1996-05-28
•
Expires: 2015-06-01
Abstract
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.
Inventors
- 👤 Brian T. Berkowitz
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-01 21:06
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/90; G06F16/901; G06F16/9027; Y; Y10; Y10S; Y10S707/00; Y10S707/99941; Y10S707/99942
Claims Analysis
Total Claims: 10
Claim 1
Independent Claim
104 words
A method in a computer system of automatically reorganizing a B-tree, the B-tree comprising a plurality of pages, and an amount of data being stored on each page, the method comprising: providing activity statistics for the B-tree; when data is added to or deleted from the B-tree, determining whether the B-tree should be reorganized by analyzing the activity statistics; and when it is determined that the B-tree should be reorganized, computing an optimal amount of data that should be stored on each paged of the B-tree, and reorganizing the B-tree by storing approximately the optimal amount of data on each page of the B-tree.
Claim 2
Independent Claim
104 words
A method in a computer system of automatically reorganizing a B-tree, the B-tree comprising a plurality of pages, and an amount of data being stored on each page, the method comprising: providing activity statistics for the B-tree; when data is added to or deleted from the B-tree, determining whether the B-tree should be reorganized by analyzing the activity statistics; and when it is determined that the B-tree should be reorganized, computing an optimal amount of data that should be stored on each paged of the B-tree, and reorganizing the B-tree by storing approximately the optimal amount of data on each page of the B-tree.
Claim 3
Dependent Claim
61 words
The method of claim 1 wherein the B-tree was previously reorganized and the activity statistics include an amount of time since the last reorganization and the step of determining whether the B-tree should be reorganized includes determining that the B-tree should not be reorganized when the amount of time since the last reorganization is less than a minimum amount of time.
Claim 4
Independent Claim
103 words
A method in a computer system of automatically reorganizing a B-tree, the B-tree comprising a plurality of pages, and an amount of data being stored on each page, the method comprising: providing activity statistics for the B-tree; after a predetermined amount of time has passed, determining whether the B-tree should be reorganized by analyzing the activity statistics, and when it is determined that the B-tree should be reorganized, computing an optimal amount of data that should be stored on each page of the B-tree, and reorganizing the B-tree by storing approximately the optimal amount of data on substantially each page of the B-tree.
Claim 5
Independent Claim
103 words
A method in a computer system of automatically reorganizing a B-tree, the B-tree comprising a plurality of pages, and an amount of data being stored on each page, the method comprising: providing activity statistics for the B-tree; after a predetermined amount of time has passed, determining whether the B-tree should be reorganized by analyzing the activity statistics, and when it is determined that the B-tree should be reorganized, computing an optimal amount of data that should be stored on each page of the B-tree, and reorganizing the B-tree by storing approximately the optimal amount of data on substantially each page of the B-tree.
Claim 6
Independent Claim
54 words
The method of claims 1 or 3 wherein the activity statistics include a total number of pages in the B-tree and the step of determining whether the B-tree should be reorganized includes determining that the B-tree should not be reorganized when the total number of pages is less than or equal to one page.
Claim 7
Independent Claim
74 words
The method of claims 1 or 3 wherein the activity statistics include a total number of pages added to the B-tree and the step of determining whether the B-tree should be reorganized includes determining that the B-tree should be reorganized when the total number of pages in the B-tree is greater than a minimum number of pages and the total number of pages added to the B-tree is greater than a page addition threshold.
Claim 8
Independent Claim
74 words
The method of claims 1 or 3 wherein the activity statistics include a total number of pages deleted from the B-tree and the step of determining whether the B-tree should be reorganized includes determining that the B-tree should be reorganized when the total number of pages in the B-tree is greater than a minimum number of pages and the total number of pages deleted from the B-tree is greater than a page deletion threshold.
Claim 9
Dependent Claim
95 words
In a computer system having a B-tree with a number of pages holding data, a method comprising the steps of: providing activity statistics that provide a metric of an amount of activity performed on the B-tree; determining whether the amount of activity performed on the B-tree as reflected by the activity statistics exceeds a threshold; and where the amount of activity performed on the B-tree exceeds the threshold, reorganizing the B-tree so that data is stored in the pages so that it is distributed among the pages of the B-tree differently than before the reorganization.
Claim 10
Dependent Claim
95 words
In a computer system having a B-tree with a number of pages holding data, a method comprising the steps of: providing activity statistics that provide a metric of an amount of activity performed on the B-tree; determining whether the amount of activity performed on the B-tree as reflected by the activity statistics exceeds a threshold; and where the amount of activity performed on the B-tree exceeds the threshold, reorganizing the B-tree so that data is stored in the pages so that it is distributed among the pages of the B-tree differently than before the reorganization.
References Cited (Backward Citations)
JPS581242A
Cited
US5058002A
Cited
US5089952A
Cited
US5218696A
Cited
US5261088A
Cited
US5204958A
Cited
EP0546567A2
Cited
EP0547992A2
Cited
US5446887A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-05-28 | 1999-11-27 | 2000-05-28 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-05-28 | 2003-11-27 | 2004-05-28 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-05-28 | 2007-11-27 | 2008-05-28 | $7700.00 | Window Closed / Lapsed |