Dr. Dobb's Journal - December 2008 - (Page 40)

d12kri_p3ds 10/10/08 10:38 AM Page 40 Core Technology by Konstantin Knizhnik Beyond B-Trees Benefiting from ‘nonvanilla’ indexes Of all the indexes that can order records in database-management systems, only B-Tree indexKonstantin is a software engineer at McObject. He can be reached at knizhnik@mcobject.com. es are offered universally. Often, they are the only index offered. Of course, there’s no denying B-Trees’ efficiency for basic database search operations such as exact match, prefix, and range searches. But these “vanilla” indexes are a poor fit for certain data and access patterns. For purposes as varied as IP routing, geospatial searching, and soundex algorithm development, less-common indexes can be dramatically more efficient. The scenarios I present here focus on a pair of distinctive index types—the R-Tree and a “user-defined” index using the extremeDB database from McObject (www.mcobject.com). Spatial Index Today, many applications and services need efficient algorithms to perform spatial searches—to locate the nearest object to a current location, find all objects in the user’s vicinity, and so on. But B-Tree indexes are one-dimensional and cannot deal with the R2 or R3 coordinates inherent in spatial searches. The R-Tree algorithm (sometimes called “Guttman’s R-Tree”) does the job well by mapping objects in space using a “wrapping rectangle.” If an object is represented by point coordinates (X,Y), then the wrapping rectangle is a degenerated rectangle in which the width and height are zero. For all other geographical objects (lines, polygons, arbitrary shapes), the wrapping rectangle is such that the coordinates of the top-left corner are smaller than or equal to the coordinates of any point of the object, and the coordinates of the bottom-right corner are greater than or equal to the coordinates of any point of the object. In other words, a wrapping rectangle is the smallest rectangle that fully contains the specified object. A spatial object could be defined as follows in an eXtremeDB schema definition file: 40 Dr. Dobb’s Journal l www.ddj.com l December 2008 /* structure representing point on the map */ struct Point { double latitude; double longitude; }; class Street { /* vector of points specifying the street */ vector points; /* Street wrapping rectangle */ rect wrap_rect; rtree streets_idx; }; Adding a new street requires the application to store the street’s coordinates and calculate its wrapping rectangle: Street street; mco_rect_t wr; wr.l.x = DOUBLE_MAX; wr.l.y = DOUBLE_MAX; wr.r.x = DOUBLE_MIN; wr.r.y = DOUBLE_MIN; Street_new(trans, &street); Street_points_alloc(&street, n_points); for (i = 0; i < n_points; i++) { if (points[i].latitude < wr.l.latitude) { wr.l.latitude = points[i].latitude; } if (points[i].longitude wr.r.latitude) { wr.r.latitude = points[i].latitude; } http://www.mcobject.com http://www.ddj.com

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

Dr. Dobb's Journal - December 2008 Contents Friday Night Fish Fry Alia Vox Developer Diaries Conversations The Man Who Sold the Sky Performance on Rails LINQ-to-SQL and T-SQL A Remote Java RMI Registry Beyond B-Trees File Descriptors and Multithreaded Programs Effective Concurrency The Agile Edge Swaine's Flames

Dr. Dobb's Journal - December 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.