US5446887A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Optimal reorganization of a B-tree
Assignee: Microsoft Technology Licensing LLC
•
Filing: 1993-09-17
•
Granted: 1995-08-29
•
Expires: 2013-09-17
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-10-29 18:22
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: 18
Claim 1
Independent Claim
191 words
A method in a computer system of B-tree optimization, the B-tree comprising a plurality of fixed-size pages, wherein an amount of data is stored on each page of the B-tree, the method comprising: providing activity statistics for the B-tree; when the activity statistics indicate that less than a minimal amount of activity has occurred within the B-tree, classifying the B-tree as static; when the activity statistics indicate that more than the minimal amount of activity has occurred within the B-tree, classifying the B-tree as dynamic; based upon the activity statistics and the amount of data in the B-tree, determining whether the B-tree should be reorganized; and when it is determined that the B-tree should be reorganized, determining an optimal amount of data that should be stored on each page of the B-tree based on the classification of the B-tree as static or dynamic, such that the optimal amount of data has a first value if the B-tree is classified as dynamic and a second value if the B-tree is classified as static, and reorganizing the B-tree by storing approximately the optimal amount of data on substantially each page of the B-tree.
Claim 2
Independent Claim
191 words
A method in a computer system of B-tree optimization, the B-tree comprising a plurality of fixed-size pages, wherein an amount of data is stored on each page of the B-tree, the method comprising: providing activity statistics for the B-tree; when the activity statistics indicate that less than a minimal amount of activity has occurred within the B-tree, classifying the B-tree as static; when the activity statistics indicate that more than the minimal amount of activity has occurred within the B-tree, classifying the B-tree as dynamic; based upon the activity statistics and the amount of data in the B-tree, determining whether the B-tree should be reorganized; and when it is determined that the B-tree should be reorganized, determining an optimal amount of data that should be stored on each page of the B-tree based on the classification of the B-tree as static or dynamic, such that the optimal amount of data has a first value if the B-tree is classified as dynamic and a second value if the B-tree is classified as static, and reorganizing the B-tree by storing approximately the optimal amount of data on substantially each page of the B-tree.
Claim 3
Dependent Claim
127 words
The method of claim 1 wherein the step of determining whether the B-tree should be reorganized includes the steps of: determining a first value for an optimal amount of data to store on each page of a static B-tree; determining a second value for an optimal amount of data to store on each page of a dynamic B-tree; determining that the B-tree should be reorganized when the B-tree is classified as static and less than the first value for the optimal amount of data is stored on each page of the B-tree; and determining that the B-tree should be reorganized when the B-tree is classified as dynamic and more than the second value for the optimal amount of data is stored on each page of the B-tree.
Claim 4
Dependent Claim
125 words
The method of claim 1 wherein the step of determining whether the B-tree should be reorganized includes: determining a total number of pages in the B-tree; determining a total number of pages added to the B-tree in a time period; determining a total number of pages deleted from the B-tree in the time period; and 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 in the time period multiplied by an addition factor plus the total number of pages deleted from the B-tree in the time period multiplied by a deletion factor is greater than the total number of pages.
Claim 5
Dependent Claim
98 words
The method of claim 1 wherein the step of determining whether the B-tree should be reorganized includes: determining a total number of pages in the B-tree; determining a total number of key values deleted from the B-tree in the time period; and determining that the B-tree should be reorganized when an amount of time since a last reorganization is greater than a minimum amount of time and the total number of key values deleted from the B-tree in the time period divided by the total number of pages in the B-tree is greater than a data deletion factor.
Claim 6
Dependent Claim
146 words
The method of claim 1 wherein the B-tree was previously reorganized and the step of determining whether the B-tree should be reorganized includes: determining an amount of time that has passed since the previous reorganization; determining an approximation of an average amount of data that was stored on each page of the B-tree at the time of the previous reorganization; determining an optimal amount of data that should be stored on each page of the B-tree; and determining that the B-tree should be reorganized when the amount of time that has passed since the last reorganization is greater than a minimum amount of time, and the optimal amount of data that should be stored on each page of the B-tree is greater than the approximation of the average amount of data that was stored on each page of the B-tree at the time of previous reorganization.
Claim 7
Independent Claim
135 words
A method in a computer system of determining whether a B-tree should be reorganized, wherein the B-tree comprises a plurality of pages and data is stored in each page of the B-tree, the method comprising the steps of: determining a total number of pages that comprise the B-tree; determining a total number of pages added to the B-tree in a specified time period due to data being added to the B-tree; determining a total number of pages deleted from the B-tree in the specified time period due to data being deleted from the B-tree; and determining that the B-tree should be reorganized when the B-tree comprises a minimum total number of pages and an amount of pages that have been added to or deleted from the B-tree in the specified time period exceeds a threshold.
Claim 8
Independent Claim
135 words
A method in a computer system of determining whether a B-tree should be reorganized, wherein the B-tree comprises a plurality of pages and data is stored in each page of the B-tree, the method comprising the steps of: determining a total number of pages that comprise the B-tree; determining a total number of pages added to the B-tree in a specified time period due to data being added to the B-tree; determining a total number of pages deleted from the B-tree in the specified time period due to data being deleted from the B-tree; and determining that the B-tree should be reorganized when the B-tree comprises a minimum total number of pages and an amount of pages that have been added to or deleted from the B-tree in the specified time period exceeds a threshold.
Claim 9
Independent Claim
109 words
A method in a computer system of determining whether a B-tree should be reorganized, wherein the B-tree comprises a plurality of pages and data is stored in each page of the B-tree, the method comprising the steps of: determining a time when the B-tree was last reorganized; determining a total number of key values deleted from the B-tree in a specified time period; and determining that the B-tree should be reorganized when a specified amount of time has passed since the time when the B-tree was last reorganized and said told number of key values that were deleted from the B-tree in the specified time period exceeds a threshold.
Claim 10
Independent Claim
109 words
A method in a computer system of determining whether a B-tree should be reorganized, wherein the B-tree comprises a plurality of pages and data is stored in each page of the B-tree, the method comprising the steps of: determining a time when the B-tree was last reorganized; determining a total number of key values deleted from the B-tree in a specified time period; and determining that the B-tree should be reorganized when a specified amount of time has passed since the time when the B-tree was last reorganized and said told number of key values that were deleted from the B-tree in the specified time period exceeds a threshold.
Claim 11
Independent Claim
150 words
A method in a computer system of determining whether a B-tree should be reorganized, wherein the B-tree comprises a plurality of pages and data is stored in each page of the B-tree, the method comprising the steps of: determining an optimal amount of data that should be stored in each page of the B-tree; determining a time when the B-tree was last reorganized; determining an average amount of data previously stored in each page of the B-tree at the time the B-tree was last reorganized; and determining that the B-tree should be reorganized when a specified amount of time has passed since the time when the B-tree was last reorganized and the optimal amount of data that should be stored in each page of the B-tree is greater than the average amount of data previously stored in each page of the B-tree at the time the B-tree was last reorganized.
Claim 12
Independent Claim
150 words
A method in a computer system of determining whether a B-tree should be reorganized, wherein the B-tree comprises a plurality of pages and data is stored in each page of the B-tree, the method comprising the steps of: determining an optimal amount of data that should be stored in each page of the B-tree; determining a time when the B-tree was last reorganized; determining an average amount of data previously stored in each page of the B-tree at the time the B-tree was last reorganized; and determining that the B-tree should be reorganized when a specified amount of time has passed since the time when the B-tree was last reorganized and the optimal amount of data that should be stored in each page of the B-tree is greater than the average amount of data previously stored in each page of the B-tree at the time the B-tree was last reorganized.
Claim 13
Independent Claim
122 words
A method in a computer system for B-tree optimization, the B-tree comprising a plurality of fixed-size pages, wherein an amount of data is stored on each page of the B-tree, the method comprising: providing activity statistics for the B-tree, the activity statistics indicating whether the B-tree is static or dynamic; determining whether the B-tree should be reorganized based upon the activity statistics and an approximation of all average amount of data stored on each page of the B-tree; and determining an optimal amount of data that should be stored on each page of the B-tree and reorganizing the B-tree by storing the optimal amount of data on each page of the B-tree when it is determined that the B-tree should be reorganized.
Claim 14
Independent Claim
122 words
A method in a computer system for B-tree optimization, the B-tree comprising a plurality of fixed-size pages, wherein an amount of data is stored on each page of the B-tree, the method comprising: providing activity statistics for the B-tree, the activity statistics indicating whether the B-tree is static or dynamic; determining whether the B-tree should be reorganized based upon the activity statistics and an approximation of all average amount of data stored on each page of the B-tree; and determining an optimal amount of data that should be stored on each page of the B-tree and reorganizing the B-tree by storing the optimal amount of data on each page of the B-tree when it is determined that the B-tree should be reorganized.
Claim 15
Dependent Claim
131 words
A computer system for B-tree optimization, the B-tree comprising a plurality of fixed-size pages, wherein data is stored on each page of the B-tree, the computer system comprising: a monitoring mechanism for providing activity statistics for the B-tree, the activity statistics indicating whether the B-tree is static or dynamic; an optimizing mechanism for determining whether the B-tree should be reorganized based upon the activity statistics and an approximation of an average amount of data stored on each page of the B-tree; and a reorganizing mechanism for determining 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 when it is determined that the B-tree should be reorganized.
Claim 16
Dependent Claim
131 words
A computer system for B-tree optimization, the B-tree comprising a plurality of fixed-size pages, wherein data is stored on each page of the B-tree, the computer system comprising: a monitoring mechanism for providing activity statistics for the B-tree, the activity statistics indicating whether the B-tree is static or dynamic; an optimizing mechanism for determining whether the B-tree should be reorganized based upon the activity statistics and an approximation of an average amount of data stored on each page of the B-tree; and a reorganizing mechanism for determining 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 when it is determined that the B-tree should be reorganized.
Claim 17
Dependent Claim
181 words
A computer system for B-tree optimization, the B-tree comprising a plurality of fixed-size pages, wherein all amount of data is stored on each page of the B-tree, the computer system comprising: a monitoring mechanism for providing activity statistics for the B-tree; a classifying mechanism for classifying the B-tree as static when the activity statistics indicate that less than a minimal amount of activity has occurred within the B-tree, and classifying the B-tree as dynamic when the activity statistics indicate that more than the minimal amount of activity has occurred within the B-tree; an optimizing mechanism for determining whether the B-tree should be reorganized based upon the classification of the B-tree as static or dynamic by the classifying mechanism, and the amount of data stored on each page of the B-tree; and a reorganizing mechanism for determining 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 when the optimizing mechanism determines that the B-tree should be reorganized.
Claim 18
Dependent Claim
181 words
A computer system for B-tree optimization, the B-tree comprising a plurality of fixed-size pages, wherein all amount of data is stored on each page of the B-tree, the computer system comprising: a monitoring mechanism for providing activity statistics for the B-tree; a classifying mechanism for classifying the B-tree as static when the activity statistics indicate that less than a minimal amount of activity has occurred within the B-tree, and classifying the B-tree as dynamic when the activity statistics indicate that more than the minimal amount of activity has occurred within the B-tree; an optimizing mechanism for determining whether the B-tree should be reorganized based upon the classification of the B-tree as static or dynamic by the classifying mechanism, and the amount of data stored on each page of the B-tree; and a reorganizing mechanism for determining 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 when the optimizing mechanism determines that the B-tree should be reorganized.
References Cited (Backward Citations)
JPS581242A
Cited
US5058002A
Cited
US5089952A
Cited
US5218696A
Cited
US5261088A
Cited
US5204958A
Cited
EP0546567A2
Cited
EP0547992A2
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1998-08-28 | 1999-02-27 | 1999-08-29 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2002-08-28 | 2003-02-27 | 2003-08-29 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2006-08-28 | 2007-02-27 | 2007-08-29 | $7700.00 | Window Closed / Lapsed |