Of all the indexes that can order records in database-management systems, only B-Tree indexes 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 typesthe 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 searchesto 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:
/* structure representing point on the map */ struct Point { double latitude; double longitude; }; class Street { /* vector of points specifying the street */ vector<Point> points; /* Street wrapping rectangle */ rect<double> wrap_rect; rtree<wrap_rect> 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.l.longitude) { wr.l.longitude = points[i].longitude; } if (points[i].latitude > wr.r.latitude) { wr.r.latitude = points[i].latitude; } if (points[i].longitude > wr.r.longitude) { wr.r.longitude = points[i].longitude; } Street_points_put(&street, i, &points[i]); } Street_wrap_rect_put(&street, &wr);
For instance, assume a user is searching for a location using mapping software. The application must present the result (streets) in a window that corresponds to a map rectangle with coordinates min_longitude, min_latitude, max_longitude, max_latitude.
mco_rect_t r; mco_cursor_t c; MCO_RET rc; r.l.x = min_longitude; r.l.y = min_latitude; r.r.x = max_longitude; r.r.y = max_latitude; if (Street_streets_idx_search(trans, MCO_EQ, &c, (double*)&r) == MCO_S_OK) { for (; rc == MCO_S_OK; rc = mco_cursor_next(trans, &c)) { Street street; Street_from_cursor(trans, &c, &street); // display it } }