Patent US6128610A successfully refreshed from Google Patents.
US6128610A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Index with entries that store the key of a row and all non-key values of the row
Assignee: Oracle International Corp
•
Filing: 1998-08-25
•
Granted: 2000-10-03
•
Expires: 2018-08-25
Abstract
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.
Inventors
- 👤 Jagannathan Srinivasan
- 👤 Samuel De Fazio
- 👤 Anil Nori
- 👤 Souripriya Das
- 👤 Chuck Freiwald
- 👤 Jayanta Banerjee
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-04 08:39
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/20; G06F16/22; G06F16/2228; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99932; Y10S707/99933; Y10S707/99941; Y10S707/99943
Claims Analysis
Total Claims: 31
Claim 1
Independent Claim
152 words
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.
Claim 2
Independent Claim
152 words
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.
Claim 3
Dependent Claim
24 words
The method of claim 1, wherein the step of storing includes storing at least a portion of said other values in an overflow area.
Claim 4
Dependent Claim
34 words
The method of claim 2, wherein the step of storing at least a portion of said other values includes storing at least a portion of said other values in a user specified overflow area.
Claim 5
Dependent Claim
65 words
The method of claim 1, the method further comprising the steps of: wherein the leaf node resides on a storage block that has space available to entirely store the row of data, determining whether the row of data exceeds a threshold size, and if the row of data exceeds said threshold size, then storing a portion of said row of data in an overflow area.
Claim 6
Dependent Claim
32 words
The method of claim 4, wherein the step of determining whether the row of data exceeds a predetermined size includes determining whether the row of data exceeds a user specified threshold size.
Claim 7
Dependent Claim
36 words
The method of claim 5, wherein the step of determining whether the row of data exceeds a user specified threshold includes determining whether the row of data exceeds a user specified percentage of a block size.
Claim 8
Dependent Claim
22 words
The method of claim 1 wherein said step of identifying a leaf node includes finding said leaf node in a B-tree index.
Claim 9
Independent Claim
147 words
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.
Claim 10
Independent Claim
147 words
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.
Claim 11
Dependent Claim
34 words
The method of claim 8, wherein the step of reading a first portion and a second portion includes reading the second portion of the row of data from a user specified row overflow area.
Claim 12
Independent Claim
172 words
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.
Claim 13
Independent Claim
172 words
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.
Claim 14
Dependent Claim
183 words
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.
Claim 15
Dependent Claim
183 words
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.
Claim 16
Dependent Claim
25 words
The computer-readable medium of claim 11, wherein the step of storing includes storing at least a portion of said other values in an overflow area.
Claim 17
Dependent Claim
35 words
The computer-readable medium of claim 12, wherein the step of storing at least a portion of said other values includes storing at least a portion of said other values in a user specified overflow area.
Claim 18
Dependent Claim
178 words
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.
Claim 19
Dependent Claim
178 words
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.
Claim 20
Dependent Claim
35 words
The computer-readable medium of claim 14, wherein the step of reading a first portion and a second portion includes reading the second portion of the row of data from a user specified row overflow area.
Claim 21
Dependent Claim
135 words
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.
Claim 22
Dependent Claim
135 words
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.
Claim 23
Dependent Claim
36 words
The database system of claim 16, wherein said processor is configured to store said index entry in said leaf node by storing at least a portion of said other values in a user specified overflow area.
Claim 24
Dependent Claim
155 words
The database system of claim 16 wherein: said processor is configured to store at least a portion of said index entry in a storage block that may be used to store up to a maximum amount of data; said processor is configured to identify the index entry in said leaf node based on a user-supplied key; said processor is configured to determine whether the index entry has a size that exceeds a row threshold that is less than the maximum amount of data; said processor is configured to read a row of data from the index entry if the index entry has a size that exceeds the row threshold; and said processor is configured to read 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 if the index entry has a size that exceeds the row threshold.
Claim 25
Dependent Claim
24 words
The database system of claim 18, wherein said processor is configured to read the second portion by reading a user specified row overflow area.
Claim 26
Dependent Claim
132 words
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.
Claim 27
Dependent Claim
132 words
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.
Claim 28
Dependent Claim
65 words
The computer-readable of claim 11, the method further comprising the steps of: wherein the leaf node resides on a storage block that has space available to entirely store the row of data, determining whether the row of data exceeds a threshold size, and if the row of data exceeds said threshold size, then storing a portion of said row of data in an overflow area.
Claim 29
Dependent Claim
32 words
The computer-readable of claim 21, wherein the step of determining whether the row of data exceeds a predetermined size includes determining whether the row of data exceeds a user specified threshold size.
Claim 30
Dependent Claim
36 words
The computer-readable of claim 22, wherein the step of determining whether the row of data exceeds a user specified threshold includes determining whether the row of data exceeds a user specified percentage of a block size.
Claim 31
Dependent Claim
22 words
The computer-readable of claim 11, wherein said step of identifying a leaf node includes finding said leaf node in a B-tree index.
References Cited (Backward Citations)
US5761493A
Cited
US5752243A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-10-03 | 2004-04-03 | 2004-10-03 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-10-03 | 2008-04-03 | 2008-10-03 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-10-03 | 2012-04-03 | 2012-10-03 | $7700.00 | Window Closed / Lapsed |