Method and apparatus for hardware-implemented AVL tree updates
US9836491B1 · kind B1 · utility
Assignee
Inventors
Key dates
| Filing date | Oct 17, 2016 |
| Grant date | Dec 5, 2017 |
| Priority date | — |
| Expiry date | Oct 17, 2036 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F16/951
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
The present disclosure describes techniques and apparatuses for hardware-implemented AVL tree updates. In some aspects, records are accessed as part of a search performed to update an AVL tree. The update may involve inserting a new node into, or removing a node from, the AVL tree. The AVL tree is represented by records stored in memory, each of which represents a node of the AVL tree. During the search, each of the records accessed is read from memory. The records read from memory are then written to an AVL tree rebalancing component implemented in hardware. Once the records are written to the hardware-implemented AVL tree rebalancer, it can modify, without subsequently accessing the memory, those records corresponding to the nodes affected by the update. After those records are modified by the hardware-implemented AVL tree rebalancer, the modified records are written back to the memory effective to update the AVL tree.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.