Write-optimized nested trees
US10649959B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Sep 27, 2017 |
| Grant date | May 12, 2020 |
| Priority date | — |
| Expiry date | Apr 10, 2038 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F16/2246
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
A Bε-tree associated with a file system on a storage volume includes a hierarchy of nodes. Each node includes a buffer portion that can be characterized by a fixed maximum allowable size to store key-value pairs as messages in the buffer. Messages can be initially buffered in the root node of the Bε-tree, and flushed to descendent children from the root node. Messages stored in the buffers can be indexed using a B+-tree data structure. As the B+-tree data structure in a buffer grows (due to receiving flushed messages) and shrinks (due to messages being flushed), disk blocks can be allocated from the storage volume to increase the actual size of the buffer and deallocated from the buffer to reduce the actual size of the buffer.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.