摘要 |
In random access memory, a data structure of trie elements of compact and fixed size is provided in order to store elements of a hierarchical prefix-type data structure such that the data structure can be searched quickly. A trie element according to the invention contains the data in one stride of the search through the prefix-type data structure. According to the invention, the trie element may contain 1) a description of the tree structure associated with the trie element, 2) a description of the links to the next level trie element, and 3) a pointer to the storage location of the next level trie element. The prefix structure has a first level trie element, and at least one second level trie element. The trie element includes a first code of the first level trie element describing the prefixes contained in the first level trie element, a second code specifying paths between the first level trie element and all children of the first level trie element (such children are second level trie elements), and a pointer for linking the first level trie element with one of the second level trie elements. Each of the first and second trie elements and the pointer are of a fixed, predefined size.
|