Defragmentation for log structured merge tree to improve read and write amplification

A non-transitory machine readable medium comprising instructions, which when executed by a machine, causes the machine to:

• store keys of key-value pairs within a log structured merge tree associated with a key-value store, wherein the keys of the key-value pairs are assigned to bins within distributed storage based upon prefixes of the keys;
• merge keys down to lower levels of the log structured merge tree to re-compact the keys;
• and
• during a rebalancing process that rebalances the keys across the bins based upon the prefixes, defragment a set of keys within a level of the log structured merge tree to store the set of keys together within a region of the distributed storage.

A system, comprising:

• a memory comprising machine executable code;
• and
• a processor coupled to the memory, the processor configured to execute the machine executable code to cause the machine to:
• store keys of key-value pairs within a log structured merge tree associated with a key-value store, wherein the keys of the key-value pairs are assigned to bins within distributed storage based upon prefixes of the keys;
• merge keys down to lower levels of the log structured merge tree to re-compact the keys;
• and
• during a rebalancing process that rebalances the keys across the bins based upon the prefixes, defragment a set of keys within a level of the log structured merge tree to store the set of keys together within a region of the distributed storage.