Channels ▼

JVM Languages

Patricia Tries

Source Code Accompanies This Article. Download It Now.

Konstantin Knizhnik is a software engineer at McObject. He can be reached at

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; 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 Reading

More Insights

Currently we allow the following HTML tags in comments:

Single tags


<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags


<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

