Dr. Dobb's Journal - July 2008 - (Page 20)

Core Technology by Konstantin Knizhnik Patricia Tries A better index for prefix searches A B-Tree can locate keys with a specified prefix; for example, finding all stock symbols starting Konstantin Knizhnik is a software engineer at McObject. He can be reached at knizhnik@mcobject.com. 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 dest; uint4 gateway; uint4 interf; uint2 metric; unique patricia 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 > 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. DDJ 20 Dr. Dobb’s Journal l www.ddj.com l July 2008 http://www.mcobject.com http://www.ddj.com

Table of Contents Feed for the Digital Edition of Dr. Dobb's Journal - July 2008

Dr. Dobb's Journal - July 2008 Contents Friday Night Fish Fry Alia Vox Developer Diaries Developer’s Notebook Engineers Without Borders Conversations Patricia Tries Event-Based Architectures Graphs Versus Objects Lock-Free Queues Dr. Dobb’s Architecture & Design World Java and the Nokia N10 Internet Tablet Effective Concurrency The Agile Edge Swaine’s Flames

Dr. Dobb's Journal - July 2008

For optimal viewing of this digital publication, please enable JavaScript and then refresh the page. If you would like to try to load the digital publication without using Flash Player detection, please click here.