Beyond B-Trees

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 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:

/* 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
    }
}