Patent ID: 8412881

Claim:
A system comprising: a memory device organized as a plurality of data pages, each of the plurality of data pages to be associated with a physical address and a logical address, the physical address to indicate a memory location of the data page in the memory device, the logical address to identify the page to a component of the system; a tree structure stored in the memory device, the tree structure to organize the plurality of data pages, each node of the tree structure to have a node capacity to store a number of logical addresses, the node capacity to be determined by a data page size and a number of physical addresses in the memory device, the tree structure to further include a plurality of leaf nodes to represent the logical addresses of the data pages of the memory device, and each leaf node to include the physical address of one of the data pages, a plurality of mid-level nodes to store the addresses of the leaf nodes, and a root node to store the addresses of the plurality of mid-level nodes; a cache unit to store copies of some of the nodes of the tree structure; and a memory controller to determine the physical address of the page based on the logical address of the page; wherein the physical addresses of the data pages to be stored only in the plurality of leaf nodes, the plurality of leaf nodes to sequentially store the physical addresses of the data pages of the system and the plurality of mid-level nodes to sequentially store the addresses of the leaf nodes, and determining the physical address of the page includes identifying an index of the root node by obtaining the quotient of the logical address of the page divided by the result of the node capacity squared, the index of the root node to identify a mid-level node, identifying an index of the mid-level node by dividing, the remainder of the result of the quotient of the logical address divided by the node capacity, by the node capacity, the index of the mid-level node to identify a leaf node, and identifying an index of the leaf node by obtaining the remainder of the result of logical address divided by the node capacity, the index of the leaf node to identify the physical address of the page.