An example computer system includes a memory storing program code and a storage system storing at least a portion of a fragmented log-structured merge (FLSM) tree implementing a key-value store. The FLSM tree includes H levels, where H is an integer greater than one. The computer system further includes a central processing unit (CPU) configured to execute the program code stored in the memory to store a plurality of key-value pairs in the FLSM tree, the key value pairs having keys defined within a key space, the key space divided by a plurality of guards for each of the H levels of the FLSM tree, each of the key-value pairs being stored a maximum of H times in the FLSM tree.