US5408654A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method to reorganize an index file without sorting by changing the physical order of pages to match the logical order determined from the index structure
Assignee: BMC Software Inc
•
Filing: 1992-05-27
•
Granted: 1995-04-18
•
Expires: 2012-05-27
Abstract
Abstract A method for reorganizing database index files without performing a conventional sort operation. The index file uses a balanced tree structure, with the logical order of the entries in each page being maintained by the database program. In the reorganizing method the logical order of the leaf pages is determined. A logical order buffer is developed which correlates the logical order to the physical order. This buffer is transposed to a physical order to logical order buffer. A large buffer is set aside in memory and the index file is read sequentially. As each physical page is read, it is placed in its logical position in the large memory buffer. When the large buffer is filled, the pages are sequentially written to a new index file, with the various tree pages being developed in the fly. When the writing operation is completed, the old index file is removed and the new, ordered index file is used.
Inventors
- 👤 Richard E. Barry
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-30 10:16
CPC Classifications
G; G06; G06F; G06F7/00; G06F7/22; G06F16/00; G06F16/20; G06F16/22; G06F16/2228; G06F16/2246; Y; Y10; Y10S; Y10S707/00; Y10S707/99941; Y10S707/99942
Claims Analysis
Total Claims: 6
Claim 1
Independent Claim
167 words
A method for reorganizing an index file on a storage system using a computer, the index file having a tree structure with tree and leaf pages, the tree pages for indicating the logical order of tree pages and leaf pages, the method comprising the steps of: reading the tree pages to determine the logical order of the leaf pages; preparing a buffer correlating the leaf page physical position with its logical position for each leaf page; preparing a large buffer for receiving a copy of all the leaf pages in the index file; sequentially reading the leaf pages from the index file; for each sequentially read leaf page, determining the leaf page logical position by reference to said physical to logical buffer and placing the read leaf page in said large buffer at a location corresponding to the leaf page logical location; sequentially writing the contents of said large buffer to a new index file; and substituting said new index file for the index file being reorganized.
Claim 2
Independent Claim
167 words
A method for reorganizing an index file on a storage system using a computer, the index file having a tree structure with tree and leaf pages, the tree pages for indicating the logical order of tree pages and leaf pages, the method comprising the steps of: reading the tree pages to determine the logical order of the leaf pages; preparing a buffer correlating the leaf page physical position with its logical position for each leaf page; preparing a large buffer for receiving a copy of all the leaf pages in the index file; sequentially reading the leaf pages from the index file; for each sequentially read leaf page, determining the leaf page logical position by reference to said physical to logical buffer and placing the read leaf page in said large buffer at a location corresponding to the leaf page logical location; sequentially writing the contents of said large buffer to a new index file; and substituting said new index file for the index file being reorganized.
Claim 3
Dependent Claim
45 words
The method of claim 1, further comprising the step of: preparing a buffer correlating the leaf page logical position to its physical position for each leaf page; and wherein said step of preparing said physical to logical buffer includes transposing said logical to physical buffer.
Claim 4
Dependent Claim
18 words
The method of claim 1, wherein said sequential reading and sequential writing steps occur at least partially concurrently.
Claim 5
Dependent Claim
88 words
The method of claim 3, further comprising the steps of: preparing a map table having an entry for each leaf page; indicating in said map table at a location corresponding to a location in said large buffer that a leaf page has been placed said large buffer location; and wherein said step of sequentially writing includes reviewing said map table to determine if a next series of large buffer locations have received leaf pages, and if so, sequentially writing the received leaf pages to the new index file.
Claim 6
Dependent Claim
39 words
The method of claim 1, wherein said step of sequentially writing includes developing tree pages as the leaf pages are written and writing said tree pages to said new index file as filled in sequence with the leaf pages.
References Cited (Backward Citations)
US4890226A
Cited
US4679139A
Cited
US5121493A
Cited
US5222235A
Cited
US5117495A
Cited
US5269019A
Cited
US5204958A
Cited
US5241474A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1998-04-17 | 1998-10-17 | 1999-04-18 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2002-04-17 | 2002-10-17 | 2003-04-18 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2006-04-17 | 2006-10-17 | 2007-04-18 | $7700.00 | Window Closed / Lapsed |