Email	Print Reprint
	add to:
	Del.icio.us Digg Google Furl	Slashdot Y! MyWeb Blink

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.

RELATED ARTICLES Tesla Algorithm Charts Evolving Genetic Networks An embedded Single Timer Wheel Software Engineering ≠ Computer Science Intelligent Standby Energy Saver Sun Releases Open Source Standard for Storage Encryption		TOP 5 ARTICLES No Top Articles.