Patent ID: 9064030
Filing Date: 2015-06-23
Classification: G06F

Abstract:
1. A method for tree traversal in a memory device, the method comprising: receiving a pointer to a tree structure within memory of the memory device; receiving an evaluation condition to identify a desired node of the tree structure; traversing the tree structure to identify the desired node by a traverse engine within the memory device; returning data from the desired node meeting the evaluation condition; fetching a node of the tree structure from the memory of the memory device by the traverse engine, wherein returning the data from the desired node meeting the evaluation condition is based on determining that the fetched node is the desired node, where fetched node data meets the evaluation condition; based on determining that the fetched node is not the desired node and the fetched node comprises two or more child nodes setting a next node to one of the child nodes, storing one or more of the child nodes remaining to a traverse queue, and continuing with fetching the next node from the memory of the memory device by the traverse engine; based on determining that the fetched node is not the desired node and the fetched node comprises one child node, setting a next node to the one child node, and continuing with fetching the next node from the memory of the memory device by the traverse engine; and based on determining that the fetched node is not the desired node and the fetched node comprises no child nodes, fetching the next node from the traverse queue based on determining that the traverse queue includes at least one node, and continuing with fetching the next node from the memory of the memory device by the traverse engine.