| 摘要 |
A method for implementing a memory. The memory is implemented as a directory structure comprising a tree-shaped hierarchy having nodes at several different levels, wherein an individual node can be (i) a trie node comprising an array wherein an individual element may contain the address of a lower node in the tree-shaped hierarchy and wherein an individual element may also be empty, the number of elements in the array corresponding to a power of two, or (ii) a bucket containing at least one element so that the type of an individual element in the bucket is selected from a group including a data unit, a pointer to a stored data unit, a pointer to another directory structure and another directory structure. To optimize storage space occupancy and memory efficiency, trie nodes are maintained in the directory structure in such a way that (1) in a trie node, the number of empty elements is smaller than or equal to half the number of elements in said node or alternatively the number of elements pointing to other trie nodes is greater than a fourth of the number of elements in the node, and (2) the number of addresses in the trie node pointing to other trie nodes is smaller than or equal to half the number of elements in the node, wherein when condition (1) is false the node is halved and when condition (2) is false the node is duplicated. This method also relates to a structure in which buckets are not employed. |
