Efficient in-memory multi-version concurrency control for a trie data structure based database

1. 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.

2. The method according to claim 1 , wherein the information whether a search key is an object identifier, or a secondary key related to a database object, is comprised in the search key.

3. The method according to claim 1 , wherein a secondary key comprises information regarding one or more properties encoded in the secondary key.

4. The method according to claim 3 , wherein the one or more properties encoded in the secondary key comprise one of a name and an address.

5. The method according to claim 1 , wherein indexes are defined as having a key and a value.

6. The method according to claim 1 , wherein a first index is defined by having the secondary key as key and the object identifier as value, and

wherein a second index is defined by having the object identifier as key and the storage location of the database object as value.

7. The method according to claim 1 , wherein creating the trie having a root node corresponding to the specific version is performed during a transaction, and the specific version is associated with the transaction.

8. The method according to claim 7 , wherein the transaction is identified by a transaction identifier.

9. 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.

10. The data-processing device or system according to claim 9 , wherein the information whether a search key is an object identifier, or a secondary key related to a database object, is comprised in the search key.

11. The data-processing device or system according to claim 9 , wherein a secondary key comprises information regarding one or more properties encoded in the secondary key.

12. The data-processing device or system according to claim 11 , wherein the one or more properties encoded in the secondary key comprise one of a name and an address.

13. The data-processing device or system according to claim 9 , wherein indexes are defined as having a key and a value.

14. The data-processing device or system according to claim 9 , wherein a first index is defined by having the secondary key as key and the object identifier as value, and

wherein a second index is defined by having the object identifier as key and the storage location of the database object as value.

15. The data-processing device or system according to claim 9 , wherein creating the trie having a root node corresponding to the specific version is performed during a transaction, and the specific version is associated with the transaction.

16. The data-processing device or system according to claim 15 , wherein the transaction is identified by a transaction identifier.

17. 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.

18. The non-transitory computer readable medium according to claim 17 , wherein the information whether a search key is an object identifier, or a secondary key related to a database object, is comprised in the search key.

19. The non-transitory computer readable medium according to claim 17 , wherein a secondary key comprises information regarding one or more properties encoded in the secondary key.

20. The non-transitory computer readable medium according to claim 19 , wherein the one or more properties encoded in the secondary key comprise one of a name and an address.

21. The non-transitory computer readable medium according to claim 17 , wherein indexes are defined as having a key and a value.

22. The non-transitory computer readable medium according to claim 17 , wherein a first index is defined by having the secondary key as key and the object identifier as value, and

wherein a second index is defined by having the object identifier as key and the storage location of the database object as value.

23. The non-transitory computer readable medium according to claim 17 , wherein creating the trie having a root node corresponding to the specific version is performed during a transaction, and the specific version is associated with the transaction.

24. The non-transitory computer readable medium according to claim 23 , wherein the transaction is identified by a transaction identifier.