Database management system and method for maintaining a database in a range sensitive manner

A system for managing a tree structure that stores data records, comprising:

• a storage device for storing multiple pages included in the tree structure;
• and
• a processor coupled to the storage device to:
• receive a data record included within an ascending sequence of data records;
• locate a page of the multiple pages that includes an insertion point at which to store the data record based on a searchable field in the data record, wherein the located page includes first, second and third sequentially-ordered data records, wherein the first, second and third sequentially-ordered data records are adjacent data records within the page, and wherein the insertion point lies between the first and second sequentially-ordered data records;
• determine whether the located page includes insufficient storage space to store the data record;
• based on the determination of insufficient storage space, determine whether dividing the located page at the insertion point will lower a load factor of the tree structure, wherein the load factor is a metric that measures overall usage of storage space within the tree structure;
• divide, in response to the determination that dividing the located page at the insertion point will lower the load factor of the tree structure, the located page into two pages at a point between the second and third sequentially-ordered data records;
• store, after the division of the located page into the two pages, the first sequentially-ordered data record, the data record to be inserted and the second sequentially-ordered data record to a same one of the two pages to increase the load factor of the tree structure for ascending sequences of records;
• and
• store the third sequentially-ordered record on a second one of the two pages resulting from the division.

A system for managing records of a database table that is represented by a tree structure having multiple nodes, comprising:

• a storage device for storing multiple nodes included in the tree structure;
• a processor coupled to the storage device;
• means for receiving a record that is part of an ascending sequence of data records;
• means for locating a node of the multiple nodes of the tree structure that includes an insertion point for the record at which to store the record based on a searchable field in the record, wherein the first, second and third sequentially-ordered data records are adjacent data records within the page and wherein the insertion point lies between the first and second sequentially-ordered records;
• means for determining whether the located node includes insufficient storage space to store the data record;
• means for determining based on the determination of insufficient storage space whether dividing the located node at the insertion point will lower a load factor of the tree structure, wherein the load factor is a metric that measures overall usage of storage space within the tree structure;
• means for dividing, in response to the determination that dividing the located node at the insertion point will lower the load factor of the tree structure, the located node into two nodes at a point between the second and third sequentially-ordered records;
• means for storing, after the division of the located node into the two pages, the first sequentially-ordered record, the record to be inserted and the second sequentially-ordered record to a same one of the two pages to increase the load factor of the tree structure for ascending sequences of records;
• and
• means for storing the third sequentially-ordered record on a second one of the two pages resulting from the division.

A computer-readable storage medium comprising instructions that cause a processor to insert an ascending sequence of records into a tree structure having multiple nodes, wherein the instruction further cause the processor to:

• a) receive a record included in the ascending sequence of records;
• b) locate a node of the multiple nodes that includes an insertion point for the record, wherein the located node includes first, second, and third sequentially-ordered records, and wherein the first, second and third sequentially-ordered records are adjacent within the located node, and wherein the insertion point lies between the first and second sequentially-ordered records;
• c) determine that the located node has insufficient storage space to store the record to be inserted;
• d) based on the determination of insufficient storage space, determine whether dividing the located node at the insertion point will lower a load factor of the tree structure, wherein the load factor is a metric that measures overall usage of storage space within the tree structure;
• e) in response to determining that dividing the located node at the insertion point will increase the load factor of the tree structure, divide the located node into two nodes at a point between the second and third sequentially ordered records
• f) store, after the division of the located node into two nodes, the first sequentially-ordered record, the record to be inserted and the second sequentially-ordered record on a first one of the two nodes resulting from the division of the located node to increase the load factor of the tree structure for ascending sequences of records;
• and
• g) store the third sequentially-ordered record on a second one of the two nodes resulting from the division.