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.
