A database management system, comprising: a memory including: an index (200, 202, 204) including a plurality of keys and at least one record associated with each of the plurality of keys; and a controller communicably coupled to the memory, configured to: receive a first database transaction for accessing a first requested key that does not match any of the plurality of keys, determine a first key from the plurality of keys, wherein a value of the first key is nearest to and is one of less than and greater than a value of the first requested key, use a k-partition function to assign the first requested key a first partition out of k -partitions, the k-partition function being configured to partition a plurality of keys, which are not comprised within the plurality of keys in the index, and each of which has a respective value between the value of the first key and a value of another key that is preceding or subsequent to the first key in the plurality of keys in the index, into a plurality of partitions; issue a first lock to the first database transaction for the first partition, receive, prior to completion of the first database transaction, a second database transaction for accessing a second requested key that does not match any of the plurality of keys, wherein a value of the second requested key has a same less than or greater than relationship with the value of the first key as the value of the first requested key does with the value of the first key, use the k-partition function to assign the second requested key a second partition out of the k -partitions, and issue a second lock to the second database transaction for the second partition based on a determination that the second partition is distinct from the first partition. a memory including: an index (200, 202, 204) including a plurality of keys and at least one record associated with each of the plurality of keys; and a controller communicably coupled to the memory, configured to: receive a first database transaction for accessing a first requested key that does not match any of the plurality of keys, determine a first key from the plurality of keys, wherein a value of the first key is nearest to and is one of less than and greater than a value of the first requested key, use a k-partition function to assign the first requested key a first partition out of k -partitions, the k-partition function being configured to partition a plurality of keys, which are not comprised within the plurality of keys in the index, and each of which has a respective value between the value of the first key and a value of another key that is preceding or subsequent to the first key in the plurality of keys in the index, into a plurality of partitions; issue a first lock to the first database transaction for the first partition, receive, prior to completion of the first database transaction, a second database transaction for accessing a second requested key that does not match any of the plurality of keys, wherein a value of the second requested key has a same less than or greater than relationship with the value of the first key as the value of the first requested key does with the value of the first key, use the k-partition function to assign the second requested key a second partition out of the k -partitions, and issue a second lock to the second database transaction for the second partition based on a determination that the second partition is distinct from the first partition. receive a first database transaction for accessing a first requested key that does not match any of the plurality of keys, determine a first key from the plurality of keys, wherein a value of the first key is nearest to and is one of less than and greater than a value of the first requested key, use a k-partition function to assign the first requested key a first partition out of k -partitions, the k-partition function being configured to partition a plurality of keys, which are not comprised within the plurality of keys in the index, and each of which has a respective value between the value of the first key and a value of another key that is preceding or subsequent to the first key in the plurality of keys in the index, into a plurality of partitions; issue a first lock to the first database transaction for the first partition, receive, prior to completion of the first database transaction, a second database transaction for accessing a second requested key that does not match any of the plurality of keys, wherein a value of the second requested key has a same less than or greater than relationship with the value of the first key as the value of the first requested key does with the value of the first key, use the k-partition function to assign the second requested key a second partition out of the k -partitions, and issue a second lock to the second database transaction for the second partition based on a determination that the second partition is distinct from the first partition.