Mapping logical row identifiers for primary B+tree-like structures to physical row identifiers

• US 6,859,808 B1
• Filed: 05/31/2001
• Issued: 02/22/2005
• Est. Priority Date: 05/31/2001
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Jagannath, Mahesh, Yalamanchi, Aravind, Tran, Anh-Tuan, Das, Souripriya, Srinivasan, Jagannathan, Krishnan, Ramkumar, Chong, Eugene I., Freiwald, Charles G.
• Primary Examiner(s): Channavajjala, Srirama
• Application Number:
  US09/867,678
• Time in Patent Office: 1,363 Days
• Field of Search: 707/100, 707/101, 707/102, 707 3- 10, 707/201
• US Class Current: 707/741
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: Y10S 707/968 Partitioning
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

A mapping mechanism for a primary B+tree in a database management system. The primary B+tree includes a plurality of rows. The mapping mechanism includes introducing a mapping table that includes a plurality of rows, including a row for each row of the primary B+tree, and that stores the logical identifier of the corresponding primary B+tree row. In addition, reverse mapping is provided by augmenting a primary B+tree to include in each primary B+tree row a physical row identifier of the corresponding mapping table row. An auxiliary structure created on a primary B+tree can make use of the proposed mapping mechanism. Specifically, the auxiliary structures refers to primary B+tree rows indirectly by storing the physical row identifier of the corresponding mapping table row.

Claims

1. A method for loading/populating a primary B+tree in a memory of a computer system having an associated mapping table, the method comprising:

generating a row of the mapping table for each row of the primary B+tree; and

storing in each row of the mapping table a row identifier for a corresponding row of the primary B+tree, the row identifier comprising a primary key column value for each row of the primary B+tree and a guess-DBA.

2. A method for maintaining a circular dependency between a mapping table row in a memory of a computer system and a primary B+tree row in the memory of the computer system, the method comprising:

computing a length of a mapping table row based upon a length of a primary key and an overhead of a guess-DBA;

utilizing the computed length to identify a mapping table block that can accommodate the row;

reserving a slot in the identified mapping table block, wherein an address of the block and a reserved slot form a mapping table physical row identifier;

inserting a primary B+tree row containing the physical row identifier into the primary B+tree;

utilizing a leaf block address of the primary B+tree row to construct a row of the mapping table; and

inserting the mapping table row in the reserved slot.

3. The method according to claim 2, further comprising:

carrying out a partition maintenance operation on the primary B+tree; and

rebuilding the mapping table after the partition maintenance.

4. The method according to claim 2, further comprising:

carrying out a partition maintenance operation on the primary B+tree; and

maintain the mapping table during the partition maintenance.

5. The method according to claim 2, further comprising:

carrying out a partition maintenance operation on the primary B+tree and rebuilding the mapping table on-line.

6. A computer program product for performing a process for indexing a primary B+tree, the computer program product comprising:

a computer readable medium; and

computer program instructions, recorded on the computer readable medium, executable by a processor, for performing the steps of;

generating a row of a mapping table for each row of the primary B+tree; and

storing in each row of the mapping table a row identifier for a corresponding row of the primary B+tree, the identifier comprising a primary key column value and a guess-database address for each row of the primary B+tree.

7. A system for performing a process for indexing a primary B+tree, the system comprising:

a processor operable to execute computer program instructions; and

a memory operable to store computer program instructions executable by the processor, for performing the steps of;

generating a row of a mapping table for each row of the primary B+tree; and

storing in each row of the mapping table a row identifier for a corresponding row of the primary B+tree, the identifier comprising a primary key column value and a guess-database address for each row of the primary B+tree.

8. A method of referencing rows of a primary B+tree in the memory of a computer system, the method comprising:

generating a mapping table in the memory of the computer system, the mapping table having a row for each row of the primary B+tree; and

storing in each row of the mapping table a primary key value from the primary B+tree, wherein the mapping table provides one-to-one mapping between primary keys of the primary B+tree structure and physical row identifiers of the mapping table.

9. The method according to claim 8, further comprising:

storing in each row of the mapping table a guess-DBA, database block address of a leaf block of the primary B+tree, where a corresponding primary B+tree row is likely to be found.

10. A method of generating a mapping table in a memory of a computer system, comprising:

generating a row of the mapping table for each row of a primary B+tree; and

storing in each row of the primary B+tree a mapping table row identifier, the mapping table row identifier comprising a physical row identifier of a corresponding mapping table row.

11. The method according to claim 10, wherein the mapping table row identifiers are stored at a fixed offset from a beginning of each row of the primary B+tree.

12. The method of claim 11, further comprising

generating an auxiliary structure for the primary B+tree in the memory of the computer system, the auxiliary structure comprising row identifiers of corresponding mapping table rows, the row identifiers referring to a primary B+tree row.

13. A method for maintaining a circular dependency between a mapping table row in a memory of a computer system and a primary index row in the memory of the computer system, the method comprising:

computing a length of a mapping table row based upon a length of a primary key and an overhead of a guess-DBA;

utilizing the computed length to identify a mapping table block that can accommodate the row;

reserving a slot in the identified mapping table block, wherein an address of the block and a reserved slot form a mapping table physical row identifier;

inserting a primary index row containing the physical row identifier into the primary index;

utilizing a leaf block address of the primary index row to construct a row of the mapping table; and

inserting the mapping table row in the reserved slot.

14. The method according to claim 13, further comprising:

carrying out a partition maintenance operation on the primary index; and

rebuilding the mapping table after the partition maintenance.

15. The method according to claim 13, further comprising:

carrying out a partition maintenance operation on the primary index; and

maintain the mapping table during the partition maintenance.

16. The method according to claim 13, further comprising:

carrying out a partition maintenance operation on the primary index and rebuilding the mapping table on-line.