摘要：使用数据索引能够成数量级的提升嵌入式应用的线性查找速度。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的数据库定义语言，空间对象可以被描述如下：