Granted Patent B2

US 8,682,872 · App. 12/640,549 · Granted Mar 25, 2014

Abstract

Claims (68)

1. A method, comprising:

identifying a first page in a key-ordered chain of index pages of a database implemented in a computer system in which to store a first key value;

determining that the first page is full;

responsive to the determining, determining that an existing adjacent page of the key-ordered chain is full;

responsive to determining that the existing adjacent page is full, moving a key from each of a sequence of pages of the key-ordered chain of pages beginning with the existing adjacent page to make room in the existing adjacent page without splitting the existing adjacent page;

moving a second key value from the first page to the existing adjacent page of the key-ordered chain after moving the key from each of the sequence of pages; and

after moving the second key value, inserting the first key value into the first page.

2. The method of claim 1 , the method further comprising:

determining that the existing adjacent page is not full, and

moving the second key value from the first page to the existing adjacent page of the key-ordered chain that has room for the second key value.

3. The method of claim 1 , wherein the action of moving a key from each of a sequence of pages of the key-ordered chain of pages beginning with the existing adjacent page ends with a penultimate page of the key-ordered chain of pages; and the method further comprises:

moving a highest key from a last page of the key-ordered chain of pages to a cache.

4. The method of claim 3 , further comprising:

creating a new page at the end of the key-ordered chain of pages; and

moving keys from the cache to the new page.

5. The method of claim 4 , wherein the action of moving keys from the cache to the new page is performed if the cache reaches a predetermined threshold size.

6. The method of claim 4 , wherein the action of moving keys from the cache to the new page comprises:

moving keys from the cache to the new page; and

clearing the cache.

7. The method of claim 1 , wherein the action of moving a key from each of a sequence of pages of the key-ordered chain of pages beginning with the existing adjacent page comprises:

moving a key from each of the sequence of pages in reverse order of the sequence of pages.

8. A computer-readable storage device with instructions for a programmable control device stored thereon wherein the instructions cause a programmable control device to perform the method of claim 1 .

9. A computer system comprising:

a processor;

a first datastore, operatively coupled to the processor; and

a database, stored in the first datastore, comprising:

a plurality of data records, each containing a key value,

a plurality of index key pages, each containing a plurality of keys ordered according to a collating sequence, the plurality of index key pages linked in a key-ordered chain of index key pages, and

a program datastore, operatively coupled to the processor, configured to hold programs that when executed, cause the processor to perform the method of claim 1 .

10. A method, comprising:

receiving a new key for insertion into a key-ordered chain of index pages of a database implemented in a computer system;

determining that a first index page in the key-ordered chain of index pages does not have room to insert the new key;

responsive to the determining, defining a sequence of index pages from the first index page to a second index page in the chain of index pages, the second page existing at the time of the determining, and having room for an additional key, wherein the second index page is within a sequence of no more than a predetermined quantity of index pages;

freeing space in the first index page by moving a key from each index page in the sequence of index pages to an adjacent page in the sequence of index pages, including moving a key from the first index page to an existing adjacent index page in the chain of index pages without splitting the first index page; and

after moving the key from the first index page, inserting the new key into the first index page.

11. The method of claim 10 , wherein the second index page is a successor index page to the first index page of the sequence of index pages and moving a key comprises:

moving a highest key of each index page to a successor index page in the sequence of index pages.

12. The method of claim 10 , wherein the second index page is a predecessor index page to the first index page of the sequence of index pages and moving a key comprises:

moving a lowest key of each index page to a predecessor index page in the sequence of index pages.

13. The method of claim 10 , wherein the action of defining a sequence of index pages from the first index page to a second index page in the chain of index pages comprises:

when the second index page is not within a sequence of no more than the predetermined quantity of index pages:

splitting the first index page into an original page and a split page, and

inserting the new key into one of the original page or the split page.

14. The method of claim 10 , wherein freeing space in the first index page includes:

moving a first key from a last index page in the sequence of index pages to a cache of keys.

15. The method of claim 10 , wherein

defining the sequence of index pages includes:

moving a highest key from a last index page of the chain of index pages to a cache of keys, and

defining the sequence of index pages as the first index page to the last index page of the chain of index pages; and

freeing space in the first index page includes:

moving a sequence of keys from members of the sequence of index pages to other members of the sequence of index pages, freeing space in the first index page,

creating a new index page as new last page of the chain of index pages, and

inserting keys from the cache of keys into the new index page.

16. The method of claim 15 , further comprising:

performing the creating of the new index page when the cache reaches a predetermined threshold size.

17. A computer-readable storage device with instructions for a programmable control device stored thereon wherein the instructions cause a programmable control device to perform the method of claim 10 .

18. A networked computer system comprising:

a plurality of computers communicatively coupled, at least one of the plurality of computers programmed to perform at least a portion of the method of claim 11 wherein the entire method of claim 10 is performed collectively by the plurality of computers.

19. The method of claim 10 , wherein the first index page does not have room when inserting the new key would cause the first index page to exceed a percent full parameter.

20. A computer system, comprising:

at least one processor; and

memory storing instructions that, when executed by the at least one processor, cause the computer system to perform operations comprising:

determining that a first index page in a key-ordered chain of index pages of a database does not have room to insert a new key;

determining a first quantity of key movements for moving keys among a first sequence of index pages between the first index page and a second index page that precedes the first index page in the key-ordered chain and that has room to insert a key;

determining a second quantity of key movements for moving keys among a second sequence of index pages between the first index page and a third index page that succeeds the first index page in the key-ordered chain and that has room to insert a key;

when the first quantity is fewer than the second quantity, moving a lowest key of each index page to a predecessor index page in the first sequence of index pages;

when the first quantity is not fewer than the second quantity, moving a highest key of each index page to a successor index page in the second sequence of index pages; and

inserting the new key into the first index page.

Assignments (13)