Trading off cache space and write amplification for Bε-trees
US10983909B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Jan 18, 2019 |
| Grant date | Apr 20, 2021 |
| Priority date | — |
| Expiry date | Apr 12, 2039 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F2212/1044
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
Certain aspects provide systems and methods for performing an operation on a Bε-tree. A method comprises writing a message associated with the operation to a first slot in a first buffer of a first non-leaf node of the Bε-tree in an append-only manner, wherein a first filter associated with the first slot is used for query operations associated with the first slot. The method further comprises determining that the first buffer is full and, upon determining to flush the message to a non-leaf child node, flushing the message in an append-only manner to a second slot in a second buffer of the non-leaf child node, wherein a second filter associated with the second slot is used for query operations associated with the second slot. The method further comprises, upon determining to flush the message to a leaf node, flushing the message to the leaf node in a sorted manner.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.