A computer implemented method for indexing a storage class memory -enabled main-memory database, comprising: traversing, within a tree data structure, a root node and at least one inner node (340; 403A) to find a location of a leaf node (346; 403B; 446a) corresponding to a search key; wherein the tree data structure includes the root node, the at least one inner node (340; 403A) and at least one leaf node (346; 403B; 446a) including the leaf node, wherein each of the at least one leaf node (346; 403B; 446a) includes key-value pairs being keys and values associated with each respective key, wherein each of the at least one leaf node (346; 403B; 446a) includes a fingerprint; calculating a hash value for the search key; comparing the calculated hash value with fingerprint values stored in the fingerprint of the leaf node (346; 403B; 446a), wherein the fingerprint values are hash values of each key stored in the leaf node (346; 403B; 446a); if a match is found, accessing at least one key-value pair having the matching hash value determined by the comparing; and if the search key and the accessed key are the same, returning a value associated with the matching key-value pair including the accessed key; wherein the traversing, calculating, comparing, accessing, and returning are performed by one or more computers; wherein the memory of the SCM-enabled main-memory database comprises a volatile memory and a persistent memory, wherein the root node and the at least one inner node (340; 403A) are located within the volatile memory; and wherein at least the at least one leaf node (346; 403B; 446a) is located within the persistent memory. traversing, within a tree data structure, a root node and at least one inner node (340; 403A) to find a location of a leaf node (346; 403B; 446a) corresponding to a search key; wherein the tree data structure includes the root node, the at least one inner node (340; 403A) and at least one leaf node (346; 403B; 446a) including the leaf node, wherein each of the at least one leaf node (346; 403B; 446a) includes key-value pairs being keys and values associated with each respective key, wherein each of the at least one leaf node (346; 403B; 446a) includes a fingerprint; calculating a hash value for the search key; comparing the calculated hash value with fingerprint values stored in the fingerprint of the leaf node (346; 403B; 446a), wherein the fingerprint values are hash values of each key stored in the leaf node (346; 403B; 446a); if a match is found, accessing at least one key-value pair having the matching hash value determined by the comparing; and if the search key and the accessed key are the same, returning a value associated with the matching key-value pair including the accessed key; wherein the traversing, calculating, comparing, accessing, and returning are performed by one or more computers; wherein the memory of the SCM-enabled main-memory database comprises a volatile memory and a persistent memory, wherein the root node and the at least one inner node (340; 403A) are located within the volatile memory; and wherein at least the at least one leaf node (346; 403B; 446a) is located within the persistent memory.