Techniques to balance log structured merge trees
US12088497B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Aug 12, 2022 |
| Grant date | Sep 10, 2024 |
| Priority date | — |
| Expiry date | Sep 11, 2042 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F16/2246
- WIPO fieldDigital communication
- WIPO sectorElectrical engineering
Abstract
Methods, systems, and devices for techniques to balance log structured merge trees are described. A computing system may rebalance a tree structure having an ordered set of leaf nodes by splitting or joining leaf nodes of the tree structure. To split a leaf node, the computing system may select a key to evenly partition key and value data stored in the leaf. The computing system may place each key block of the leaf node having keys less than or equal to the selected key in a first new leaf node, and may place each key block of the leaf node having keys greater than the selected key in a second new leaf node. To join leaf nodes of the tree structure, the computing system may place each key block and each value block of the leaf node and the adjacent leaf node in a new leaf node.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.