Prefix trees: New efficient data structures for matching strings of different lengths

Prefix matching is an essential part of some applications. A well known application of prefix matching is layers 3 and 4 switching in TCP/IP protocols. It is assumed there are strings of an alphabet Σ which are ordered. The strings may have different lengths and some may be prefixes of others. We introduce a simple scheme for comparing and sorting strings of different lengths first. Then, data is manipulated and the well-known tree structures are tuned to handle the prefix matching queries. A string prefix represents a data space that includes all strings for which it is a prefix. Using this concept, first, we propose a binary prefix tree and extended it to two m_way tree structures, static m_way prefix tree and dynamic m_way prefix tree later. The m_way trees have better search performance at the expense of some memory space. The static m_way prefix is more suitable for an environment with few data transactions and expected to give better memory usage and create a more compact tree structure. The dynamic m_way prefix tree is a superset of B tree and suited better for environment with large transactions. All data structures share a common property. No data string can be at a higher level than its prefix in the data set. The proposed data structures are simple, well defined, easy to implement in hardware or software and efficient in terms of memory usages and search time.