Efficient index versioning in multi-version databases
First Claim
1. A method for maintaining a database index version comprising:
- storing an index item in a leaf node of a B-tree and storing version information of said index item in a secondary node remote from said B-tree; and
associating said leaf node of said B tree with said secondary node.
1 Assignment
0 Petitions
Accused Products
Abstract
A method and system are provided for maintaining a database index version. The database index includes a secondary node affiliated with each leaf node of the index. The secondary node stores version information for each leaf node. A pointer in a header section of the leaf node connects the leaf node to the secondary node. In addition, a status list is maintained to identify each transaction. At such time as a scan of a database index is conducted and an index item is returned, a computation is conducted using the transaction identifiers in the secondary node, the delete flag in the leaf node, and the status list contents for the scanning transaction. The computation and associated logic will determine whether to accept or reject an item. The method results in returning a correct version of the item as existed at the time of start of the scanning transaction.
78 Citations
18 Claims
-
1. A method for maintaining a database index version comprising:
-
storing an index item in a leaf node of a B-tree and storing version information of said index item in a secondary node remote from said B-tree; and
associating said leaf node of said B tree with said secondary node. - View Dependent Claims (2, 3, 4, 5, 6)
-
-
7. A database comprising:
-
an index item adapted to be stored in a leaf node of a B-tree;
version data of said index item adapted to be stored in a secondary node remote from said B-tree; and
a pointer to connect said leaf node with said secondary node. - View Dependent Claims (8, 9, 10, 11, 12)
-
-
13. An article comprising:
a computer useable medium embodying computer usable program code for maintaining a database index, said computer program code including;
instructions for storing an index item in a leaf node of a B-tree;
instructions for storing version information of said index item in a secondary node remote from said B-tree; and
instructions for associating said leaf node with said secondary node. - View Dependent Claims (14, 15, 16, 17, 18)
Specification