Efficient in-memory multi-version concurrency control for a trie data structure based database
AssigneeCenshare GmbH
InventorWalter Bauer
Life of this patent
Estimating the term…
Abstract
The invention describes a method for determining a storage location of a database object of a specific version, wherein indexes for each version of the database object are stored in a trie having a root node corresponding to the specific version, the method comprising: determining a trie corresponding to the specific version by accessing the root node of the trie corresponding to the specific version; determining an object identifier of the database object by traversing the trie corresponding to the specific version using a secondary key related to the database object as search key; determining the storage location of the database object by traversing the trie corresponding to the specific version using the determined object identifier as search key.
Claims24
A computer-implemented method for determining, in an electronic database application or information retrieval system, a storage location of a database object of a specific version, wherein indexes for each version of the database object are stored in a trie having a root node corresponding to the specific version, the method comprising:
- determining a trie corresponding to the specific version by accessing the root node of the trie corresponding to the specific version;
- determining an object identifier of the database object by traversing the trie corresponding to the specific version using a secondary key related to the database object as search key;
- and
- determining the storage location of the database object by traversing the trie corresponding to the specific version using the determined object identifier as search key,
- wherein the trie having a root node corresponding to the specific version is created by:
- creating a new root node for the specific version,
- copying and modifying the nodes that have been amended with regard to the nodes of a previous trie having a root node corresponding to the previous version, and
- creating references pointing to the nodes in the previous trie that have not been amended.
A data-processing device or system comprising one or more processors and memory, the data-processing device or system being configured to determine, using the one or more processors and in connection with an electronic database application or information retrieval system, a storage location of a database object of a specific version, by performing operations comprising:
- having indexes for each version of the database object stored in a trie having a root node corresponding to the specific version;
- determining a trie corresponding to the specific version by accessing the root node of the trie corresponding to the specific version;
- determining an object identifier of the database object by traversing the trie corresponding to the specific version using a secondary key related to the database object as search key;
- and
- determining the storage location of the database object by traversing the trie corresponding to the specific version using the determined object identifier as search key,
- wherein the trie having a root node corresponding to the specific version is created by:
- creating a new root node for the specific version,
- copying and modifying the nodes that have been amended with regard to the nodes of a previous trie having a root node corresponding to the previous version, and
- creating references pointing to the nodes in the previous trie that have not been amended.
A preferably non-transitory computer readable medium having stored therein instructions for an electronic database application or information retrieval system that, when performed by at least one processor, determine a storage location of a database object of a specific version, by performing operations comprising:
- having indexes for each version of the database object stored in a trie having a root node corresponding to the specific version;
- determining a trie corresponding to the specific version by accessing the root node of the trie corresponding to the specific version;
- determining an object identifier of the database object by traversing the trie corresponding to the specific version using a secondary key related to the database object as search key;
- and
- determining the storage location of the database object by traversing the trie corresponding to the specific version using the determined object identifier as search key,
- wherein the trie having a root node corresponding to the specific version is created by:
- creating a new root node for the specific version,
- copying and modifying the nodes that have been amended with regard to the nodes of a previous trie having a root node corresponding to the previous version, and
- creating references pointing to the nodes in the previous trie that have not been amended.
Dependencies are inferred from the claim text.