Patent ID: 7130859

Claim:
A computerized method for controlling storage and retrieval of data in a memory device by constructing a data structure in which items of data are stored for search, comprising: a) forming an assumed tree structure in which all the items of data are stored; b) sequentially selecting a node from the assumed tree structure to select a sub-tree structure including the selected node and any child nodes of the selected node; c) forming an equivalent table storing at least a portion of the items of data included in the selected sub-tree structure in a table form; d) determining whether the selected sub-tree structure satisfies one or more predetermined conditions; and e) when the selected sub-tree structure satisfies the one or more predetermined conditions, replacing the selected sub-tree structure with the equivalent table to construct the data structure, wherein the predetermined conditions are that: 1) an amount of memory required to store a data structure including the equivalent table in place of the selected sub-tree structure is smaller than that required to store the assumed tree structure; and 2) search performance of the data structure is not lower than that of the assumed tree structure.