用好数据库索引提升嵌入式软件性能和效率

2010-11-11 作者: 麦科捷来源: 51Testing

摘要：使用数据索引能够成数量级的提升嵌入式应用的线性查找速度。B树是最著名的通用索引，然而诸如R树和Partricia tries之类的专用索引则是以IP过滤为代表的多种应用程序的理想方案。

为了从一本书中获取信息，怎样做更有效？仔细阅读每一页内容，还是根据索引来精确确定要获取信息的位置？

显然后者更有效，嵌入式系统也应该能如此智能。如今，嵌入式应用程序管理着数量高速增长的复杂数据。找到正确的数据（无论是寻找网络包的路由目标节点、计算地图上点与点之间的距离、以及其他计算目标）通常必须在实时性能要求下被实现。

幸运的是，编程人员可以使用数据索引将查找速度从线性级别提升到对数级别。随着成品数据库管理系统（DBMS）在嵌入式系统开发中的日趋重要，索引也得到了更多的使用，多数嵌入式数据库都支持至少一种索引类型。

然而，在许多项目中，首先考虑（通常也是唯一的）索引是B树。这是因为在现有的大量索引类型中，只有B树索引最为通用。毫无疑问，B树能够高效完成基本的搜索操作，诸如：精确匹配、前缀、范围搜索等。然而，对于IP路由、映射、模式查询算法开发等目标来说，非通用的索引类型更加合适，并且能够带来更快的速度和对CPU时钟周期等资源更有效地利用。（见图1）。

图 1: B树并不是嵌入式应用程序唯一的索引选择

下面章节展示了如何使用两种非通用索引类型：R树和Patricia trie

空间索引和R树

映射(地图)以及其他基于位置的功能在移动嵌入式应用中十分常见，这些应用从战斗车辆中的战场支持系统到用来寻找最近的比萨饼店的移动电话应用程序。这些应用程序基于空间查询的算法，例如：找到离当前位置最近的对象，找到用户附近的全部对象，等等。

B树索引是一维的：它无法处理用于空间搜索的二维和三维坐标。R树（又叫做Guttman R树，根据发明者命名）是一个不错的替代品。它使用边界盒（bounding box）来映射空间中的对象。如果一个对象由坐标点（X, Y）表示，那么他的边界盒是一个边长为1的正方形。

对所有的几何对象（线、多边形以及其他形状），边界盒是这样一个长方形：其左上角坐标小于等于该对象中的任何点，其右下角坐标大于等于该对象中的任何点。换句话说，边界长方形是能够完全包含给定对象的最小长方形。

R树索引通常被用来加速空间搜索（发现包含某个点的长方形、找出全部与给定长方形重合的长方形，诸如此类）。在边界盒的帮助下，应用程序能够管理各种形状。

使用eXtremeDB的数据库定义语言，空间对象可以被描述如下：

/* 表示地图上点的结构 */
struct Point
{
double latitude;
double longitude;
};
class Street {
/* 表示街道的点向量 */
vector<Point> points;
/* 街道封装长方形 */
rect<double> wrap_rect;
rtree<wrap_rect> streets_idx;
};

如果我们希望加入一条新的街道，应用程序必须存储街道的坐标并计算其边界盒。

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);

如果用户搜索一个位置，地图应用程序将结果（街道）在窗口中表示为一个坐标为||的地图长方形。

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

Patricia trie

B树可以利用指定的前缀来定位关键字，例如，寻找以名字以“AAA”开头的公司。然而，一些应用程序必须搜索代表着一个特定值最长前缀的关键字。B树可以实现这种需求，但必须从最长的前缀开始进行多次迭代并且查询不同的给定值前缀。

一种更加有效的前缀查找索引是用于查询字母-数字编码的实践算法，即通常所说的Patricia trie。Patricia trie是二叉树的一种变形，通常用于电话路由以及IP过滤。在第一种情况中，给定接入电话以及一张带有已知前缀的接线员表，应用程序必须选择正确的接线员接到该电话。在第二种情况下，给定了有效/拒绝域的IP掩码，收到的(一个)HTTP请求应被分类为接受、拒绝、转发，等等。下面的数据库模式定义了一张路由表，带有一个由位向量表示的掩码。

class Route
{
Vector<bool> dest;
uint4 gateway;
uint4 interf;
uint2 metric;
unique patricia by_dest;
};

为了给接受到的IP地址找到合适的转发目标，应用程序使用Patricia trie对eXtremeDB做出如下查询：

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 */
/*寻找掩码与IP地址匹配的转发节点*/
if (MCO_S_OK == Route_by_dest_prefix_match(trans, &csr, mask, 32);
Route route;
Route_from_cursor(trans, &csr, &route);
...
}
}

下面的代码将表示IP地址的整数转换为位向量：

void make_mask(uint1* mask, uint4 val, int bitnum)
{
int i;
val = val >> (32-bitnum);
memset(mask, 0, 4);
for (i = 0; i < bitnum; i++, val = val >> 1)
{
mask[i >> 3] |= (val&1) << (i&7);
}
}

可选索引越多，结果越好

使用诸如R树和Patricia trie的专用索引加快了代码开发速度，提升了代码效率，并使应用程序能够处理更加复杂的数据结构。尽管著名的B树足以处理大量的普通查询任务，不怎么出名的索引类型能够在专用应用程序和数据类型中做得更好。R树能够高效处理映射和地理空间数据，而Patricia trie是电话路由、IP过滤以及其他必须通过匹配特定数值最长前缀的关键字来完成的任务的理想方案。