The invention relates to a method for implementing a functional memory and to
a memory arrangement. The memory is implemented as a directory structure comprising
a tree-shaped hierarchy having nodes at several different hierarchy levels, wherein
an individual node can be (i) a trie node associated with a logical table wherein
an individual element may contain a pointer pointing to a lower node in the hierarchy,
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 of e.g. a data unit or
a pointer to a stored data unit. To optimize the performance of the functional
trie structure, the trie nodes are implemented as quad nodes of four elements,
and in at least part of the directory structure groups of successive quad nodes
are replaced by compressed nodes in such a way that (a) an individual group comprising
a given quad node and its child nodes is replaced by a node whose logical table
has 16 elements, and (b) a compressed node known per se is formed from said node
of 16 elements by physically storing in the node only non-nil pointers and in addition
a bit pattern on the basis of which the physical storage location in the node,
corresponding to the search word, can be determined. The invention also relates
to a structure in which no buckets are used.
