Space efficiency in log-structured file systems using unbalanced splits

A computer system comprising:

• a persistent storage device storing a log-structured file system (LFS), the LFS including a tree metadata structure and user data;
• at least one processor;
• and
• a non-transitory computer readable medium having stored thereon program code executable by the at least one processor, the program code causing the at least one processor to:
• receive an input/output (I/O) operation for the LFS, the I/O operation prompting a key to be added to a first node of the tree metadata structure, the tree metadata structure mapping addresses in a first address space to addresses in a second address space;
• determine that addition of the key to the first node would exceed a maximum number of keys allowed in the first node;
• add a second node to the tree metadata structure based on the determining, the second node containing the key;
• move a quantity of keys from the first node to the second node such that a total number of keys resulting in the second node is less than half of the maximum number of keys, minus one, configured to be stored in the second node of the LFS;
• and
• write updates to the tree metadata structure within the LFS.

A non-transitory computer storage medium having stored thereon program code executable by a processor, the program code embodying a program code method comprising:

• receiving an input/output (I/O) operation for a log-structured file system (LFS), the I/O operation prompting a key to be added to a first node of a tree metadata structure, the tree metadata structure mapping addresses in a first address space to addresses in a second address space;
• determining that addition of the key to the first node would exceed a maximum number of keys allowed in the first node;
• adding a second node to the tree metadata structure based on the determining, the second node containing the key;
• moving a quantity of keys from the first node to the second node such that a total number of keys resulting in the second node is less than half of the maximum number of keys, minus one, configured to be stored in the second node of the LFS;
• and
• writing updates to the tree metadata structure within the LFS.