17886865. TECHNIQUES TO BALANCE LOG STRUCTURED MERGE TREES simplified abstract (Micron Technology, Inc.)
Contents
TECHNIQUES TO BALANCE LOG STRUCTURED MERGE TREES
Organization Name
Inventor(s)
Alexander Tomlinson of Austin TX (US)
Gaurav Sanjay Ramdasi of Austin TX (US)
Greg Alan Becker of Austin TX (US)
Nabeel Meeramohideen Mohamed of Round Rock TX (US)
Steven Andrew Moyer of Round Rock TX (US)
Tristan Antonio Partin of Austin TX (US)
TECHNIQUES TO BALANCE LOG STRUCTURED MERGE TREES - A simplified explanation of the abstract
This abstract first appeared for US patent application 17886865 titled 'TECHNIQUES TO BALANCE LOG STRUCTURED MERGE TREES
Simplified Explanation
Methods, systems, and devices for balancing log structured merge trees are described in the patent application. A computing system may rebalance a tree structure with an ordered set of leaf nodes by splitting or joining leaf nodes of the tree structure. To split a leaf node, the computing system selects a key to evenly partition key and value data stored in the leaf. The system then places key blocks with keys less than or equal to the selected key in a new leaf node, and key blocks with keys greater than the selected key in another new leaf node. To join leaf nodes, the system combines key and value blocks of the leaf node and the adjacent leaf node into a new leaf node.
- Rebalancing of tree structures with ordered sets of leaf nodes
- Splitting leaf nodes by selecting a key to partition data
- Placing key blocks in new leaf nodes based on selected key
- Joining leaf nodes by combining key and value blocks into a new leaf node
- Potential Applications
- Database management systems - File systems - Data storage systems
- Problems Solved
- Efficiently rebalancing tree structures - Managing large amounts of data in log structured merge trees
- Benefits
- Improved performance in data retrieval - Enhanced scalability for growing datasets - Optimal use of storage space
Original Abstract Submitted
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.
