Dr. Dobb's Journal July 2008

Patricia Tries

A better index for prefix searches

By Konstantin Knizhnik

A B-Tree can locate keys with a specified prefix; for example, finding all stock symbols starting with "AAA." But some applications require the opposite search—locating keys that represent the longest prefixes of a specified value. Here a B-tree could perform several iterations, searching for different prefixes of the specified value starting from the longest, but this is inefficient. A much better index for prefix searches is the Patricia trie, which is a variation of a binary tree. Typically, the Patricia trie is used for performing two tasks—phone routing and IP filtering. In the first case, given an incoming phone call and a table of operators with known prefixes, the right operator must be selected to handle the call. The second case deals with IP addresses: Given IP masks for valid/rejected domains, a received HTTP request should be classified as accepted, rejected, redirected, and so on. The following is a schema definition for a routing table. The mask is represented by a vector of bits (Booleans).

class Route
{
	Vector<bool> dest;
	uint4 gateway;
	uint4 interf;
	uint2 metric;
	unique patricia<dest> by_dest;
};

To locate the proper route for the received IP address, the following search is performed in eXtremeDB using a Patricia trie:

mco_cursor_t csr;
if (MCO_S_OK == Route_by_dest_index_cursor(trans, &csr)) {
    uint1 mask[4];
    make_mask(mask, ip, 32);
    /* find routes which mask match this IP address */
    if (MCO_S_OK == Route_by_dest_prefix_match(trans, &csr, mask,32);
        Route route;
        Route_from_cursor(trans, &csr, &route);
        ...
    }
}

The following code (from McObject's eXtremeDB embedded database; www.mcobject.com) converts the integer number representing the IP address into an array of bits:

void make_mask(uint1* mask, uint4 val, int bitnum)
{
    int i;
    val = val >> (32-bitnum);
    memset(mask, 0, 4);
    for (i = 0; i < bitnum; i++, val = val >> 1)
    {
         mask[i >> 3] |= (val&1) << (i&7);
    }
}

Knowledge of specialized indexes enables faster development, more efficient code, and the ability to work with more complex data structures.