Channels ▼
RSS

Design

Beyond B-Trees


Konstantin is a software engineer at McObject. He can be reached at knizhnik@mcobject.com.


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



Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<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

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 

Video