METHOD AND APPARATUS FOR HARDWARE-IMPLEMENTED AVL TREE UPDATES

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.