Database system with improved methods for B-tree maintenance
US5644763A · kind A · utility
Assignee
Inventor
Key dates
| Filing date | Jun 28, 1995 |
| Grant date | Jul 1, 1997 |
| Priority date | — |
| Expiry date | Jun 28, 2015 |
Classification
- Technology area (CPC Y)Emerging Cross-Sectional Technologies
- CPC primaryY10S707/99942
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
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.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.