Index with entries that store the key of a row and all non-key values of the row
First Claim
1. A method for storing data in a database, the method comprising the steps of:
- receiving a row of data from a client;
wherein said row includes a set of one or more key columns and a set of one or more non-key columns;
identifying a key value in said set of one or more key columns of said row of data;
locating an index in said database that is built on said set of one or more key columns;
wherein said index has a plurality of branch levels populated with branch nodes;
identifying a leaf node in said index by traversing each branch level of said plurality of branch levels by comparing said key value to a key value associated with a branch node at said each branch level; and
storing in said leaf node an index entry that includes said key value and all other values in said row of data.
3 Assignments
0 Petitions
Accused Products
Abstract
A method and apparatus for efficiently storing and retrieving data in a database using index-only tables is disclosed. Storing a row of data in a database using index-only tables involves storing in a leaf node an index entry that includes a key value along with all other values in the row of data. If the row of data exceeds a predetermined size, then a portion of the row of data is stored in a user specified overflow area. Retrieving a row of data from an index-only table for a user-supplied key involves identifying a leaf node for the key, and reading a row of data from the index entry and any remaining portion from the overflow area when the row exceeds the predetermined size.
-
Citations
24 Claims
-
1. A method for storing data in a database, the method comprising the steps of:
-
receiving a row of data from a client; wherein said row includes a set of one or more key columns and a set of one or more non-key columns; identifying a key value in said set of one or more key columns of said row of data; locating an index in said database that is built on said set of one or more key columns; wherein said index has a plurality of branch levels populated with branch nodes; identifying a leaf node in said index by traversing each branch level of said plurality of branch levels by comparing said key value to a key value associated with a branch node at said each branch level; and storing in said leaf node an index entry that includes said key value and all other values in said row of data. - View Dependent Claims (2, 3, 4, 5, 6, 7)
-
-
8. A method for retrieving data from a database for a user-supplied key, the method comprising the steps of:
-
identifying an index entry in a leaf node of an index based on said user-supplied key; wherein at least a portion of said index entry resides on a storage block that may be used to store up to a maximum amount of data; determining whether the index entry has a size that exceeds a row threshold that is less than said maximum amount; if the index entry does not have a size that exceeds the row threshold, then reading a row of data from the index entry; and if the index entry has a size that exceeds the row threshold, then reading a first portion of a row of data from the index entry, and a second portion of the row of data from an associated row overflow area. - View Dependent Claims (9)
-
-
10. A method for retrieving data from a database for a user-supplied key, the method comprising the steps of:
-
receiving one or more SQL statements requesting data from said database; in response to receiving said one or more SQL statements, performing the steps of; identifying an index entry in a leaf node of an index based on said user-supplied key; wherein at least a portion of said index entry resides on a storage block that may be used to store up to a maximum amount of data; determining whether the index entry has a size that exceeds a row threshold that is less than said maximum amount; if the index entry does not have a size that exceeds the row threshold, then reading a row of data from the index entry; and if the index entry has a size that exceeds the row threshold, then reading a first portion of a row of data from the index entry, and a second portion of the row of data from an associated row overflow area.
-
-
11. A computer-readable medium carrying one or more sequences of one or more instructions for storing data in a database, wherein the execution of the one or more sequences of the one or more instructions causes the one or more processors to perform the steps of:
-
receiving a row of data from a client; wherein said row includes a set of one or more key columns and a set of one or more non-key columns; identifying a key value in said set of one or more key columns of said row of data; locating an index in said database that is built on said set of one or more key columns; wherein said index has a plurality of branch levels populated with branch nodes; identifying a leaf node in said index by traversing each branch level of said plurality of branch levels by comparing said key value to a key value associated with a branch node at said each branch level; and storing in said leaf node an index entry that includes said key value and all other values in said row of data. - View Dependent Claims (12, 13, 21, 22, 23, 24)
-
-
14. A computer-readable medium carrying one or more sequences of one or more instructions for retrieving data from a database for a user-supplied key, wherein the execution of the one or more sequences of the one or more instructions causes the one or more processors to perform the steps of:
-
identifying an index entry in a leaf node of an index based on said user-supplied key; wherein at least a portion of said index entry resides on a storage block that may be used to store up to a maximum amount of data; determining whether the index entry has a size that exceeds a row threshold that is less than said maximum amount; if the index entry does not have a size that exceeds the row threshold, then reading a row of data from the index entry; and if the index entry has a size that exceeds the row threshold, then reading a first portion of a row of data from the index entry, and a second portion of the row of data from an associated row overflow area. - View Dependent Claims (15)
-
-
16. A database system, comprising:
-
a processor, a memory coupled to said processor; a database; an index that has a plurality of branch levels populated with branch nodes, said index is built on a set of one or more key columns of a row of data; said processor being configured to identify a leaf node in an index based on a key value by traversing each branch level of said plurality of branch levels; said processor being configured to traverse each branch level of said plurality of branch levels by comparing said key value to a key value associated with a branch node at said each branch level; and said processor being configured to store in said leaf node an index entry that includes said key value and all other values in said row of data. - View Dependent Claims (17, 18, 19)
-
-
20. A database system that includes an index stored on a storage device, wherein:
-
the database system has no separately stored table that corresponds to the index; the index is built on key values contained in rows that are stored in the index itself; entries within the index include both a key value for a row and all other values for the row; and the index has plurality of branch levels populated with branch nodes; the database system is configured to identify a leaf node containing a particular row by traversing each branch level of said plurality of branch levels; and the database system is configured to traverse each branch level by comparing said key value for the row to a key value associated with a branch node at said each branch level.
-
Specification