# US 2025/0094401 A1 · Space efficiency in log-structured file systems using unbalanced splits > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 2025/0094401 A1 - Document ID: US20250094401A1 - Status: Published application - Kind: A1 - Application number: 18/469,533 - Filed: 2023-09-18 - Published: 2025-03-20 - Earliest claimed: 2023-09-18 - Applicants: VMware, Inc. - Inventors: Quanxing LIU; Wenguang WANG; Eric KNAUFT; Enning XIANG; Salit GAZIT; Satish PUDI - Web page: https://patentgrep.com/patent/US20250094401A1 ## CPC - G06F 16/2246: {Trees, e.g. B+trees} - G06F 16/13: File access structures, e.g. distributed indices (arrangements of input from, or output to, record carriers G06F3/06) - G06F 16/2358: {Change logging, detection, and notification (replication G06F16/27)} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract A system manages a log-structured file system (LFS) by: receiving an input/output (I/O) operation for the LFS, the I/O operation prompting a key to be added to a first node of a tree metadata structure, the tree 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 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 nodes of the LFS; and writing updates to the tree metadata structure within the LFS. ## Claims ### Claim 1 A computerized method of managing a log-structured file system (LFS) on a computing device, the method comprising: receiving an input/output (I/O) operation for the 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. ### Claim 2 (depends on 1) The computerized method of claim 1, wherein the tree metadata structure is one of a b-tree and a b+-tree. ### Claim 3 (depends on 1) The computerized method of claim 1, wherein the first node is one of a right-most leaf node or a left-most leaf node of the tree metadata structure. ### Claim 4 (depends on 3) The computerized method of claim 3, further comprising performing a balanced split operation of nodes in the tree metadata structure for any node splits involving nodes that are not a right-most node of a layer of the tree metadata structure. ### Claim 5 (depends on 1) The computerized method of claim 1, wherein the tree metadata structure maps a middle address space of the LFS to a physical address space of the LFS, the physical address space identifying blocks of persistent storage used by the LFS. ### Claim 6 (depends on 5) The computerized method of claim 5, wherein the key is paired with a mapped value, wherein the key identifies a key value, the key value being a virtual address in the middle address space, wherein the mapped value is an address of one or more blocks of the persistent storage. ### Claim 7 (depends on 6) The computerized method of claim 6, further comprising: traversing the tree metadata structure resulting in a location of the key, the key being a first address in the middle address space; identifying, from the tree metadata structure based on the traversing, the address of the one or more blocks associated with the key; and performing a write operation to the persistent storage using the one or more blocks. ### Claim 8 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. ### Claim 9 (depends on 8) The computer system of claim 8, wherein the tree metadata structure is one of a b-tree and a b+-tree. ### Claim 10 (depends on 8) The computer system of claim 8, wherein the first node is one of a right-most leaf node or a left-most leaf node of the tree metadata structure. ### Claim 11 (depends on 10) The computer system of claim 10, wherein the program code further causes the at least one processor to perform a balanced split operation of nodes in the tree metadata structure for any node splits involving nodes that are not a right-most node of a layer of the tree metadata structure. ### Claim 12 (depends on 8) The computer system of claim 8, wherein the tree metadata structure maps a middle address space of the LFS to a physical address space of the LFS, the physical address space identifying blocks of the persistent storage device used by the LFS. ### Claim 13 (depends on 12) The computer system of claim 12, wherein the key is paired with a mapped value, wherein the key identifies a key value, the key value being a virtual address in the middle address space, wherein the mapped value is an address of one or more blocks of the persistent storage. ### Claim 14 (depends on 13) The computer system of claim 13, wherein the program code further causes the at least one processor to: traverse the tree metadata structure resulting in a location of the key, the key being a first address in the middle address space; identify, from the tree metadata structure based on the traversing, the address of the one or more blocks associated with the key; and perform a write operation to the persistent storage using the one or more blocks. ### Claim 15 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. ### Claim 16 (depends on 15) The non-transitory computer storage medium of claim 15, wherein the tree metadata structure is one of a b-tree and a b+-tree. ### Claim 17 (depends on 15) The non-transitory computer storage medium of claim 15, wherein the first node is one of a right-most leaf node or a left-most leaf node of the tree metadata structure. ### Claim 18 (depends on 17) The non-transitory computer storage medium of claim 17, wherein the program code method further comprises performing a balanced split operation of nodes in the tree metadata structure for any node splits involving nodes that are not a right-most node of a layer of the tree metadata structure. ### Claim 19 (depends on 15) The non-transitory computer storage medium of claim 15, wherein the tree metadata structure maps a middle address space of the LFS to a physical address space of the LFS, the physical address space identifying blocks of persistent storage used by the LFS. ### Claim 20 (depends on 19) The non-transitory computer storage medium of claim 19, wherein the key is paired with a mapped value, wherein the key identifies a key value, the key value being a virtual address in the middle address space, wherein the mapped value is an address of one or more blocks of the persistent storage.