51CTO數(shù)據(jù)庫頻道也向您推薦《數(shù)據(jù)庫之索引與查詢專題》專題，相信這個專題能幫助您更好的理解本文。為了從一本書中獲取信息，怎樣做更有效？仔細閱讀每一頁內容，還是根據(jù)索引來精確確定要獲取信息的位置？

顯然后者更有效，嵌入式系統(tǒng)也應該能如此智能。如今，嵌入式應用程序管理著數(shù)量高速增長的復雜數(shù)據(jù)。找到正確的數(shù)據(jù)（無論是尋找網(wǎng)絡包的路由目標節(jié)點、計算地圖上點與點之間的距離、以及其他計算目標）通常必須在實時性能要求下被實現(xiàn)。

幸運的是，編程人員可以使用數(shù)據(jù)索引將查找速度從線性級別提升到對數(shù)級別。隨著成品數(shù)據(jù)庫管理系統(tǒng)（DBMS）在嵌入式系統(tǒng)開發(fā)中的日趨重要，索引也得到了更多的使用，多數(shù)嵌入式數(shù)據(jù)庫都支持至少一種索引類型。

然而，在許多項目中，首先考慮（通常也是唯一的）索引是B樹。這是因為在現(xiàn)有的大量索引類型中，只有B樹索引最為通用。毫無疑問，B樹能夠高效完成基本的搜索操作，諸如：精確匹配、前綴、范圍搜索等。然而，對于IP路由、映射、模式查詢算法開發(fā)等目標來說，非通用的索引類型更加合適，并且能夠帶來更快的速度和對CPU時鐘周期等資源更有效地利用（見圖1）。

圖 1: B樹并不是嵌入式應用程序唯一的索引選擇

下面章節(jié)展示了如何使用兩種非通用索引類型：R樹和Patricia trie

空間索引和R樹

映射(地圖)以及其他基于位置的功能在移動嵌入式應用中十分常見，這些應用從戰(zhàn)斗車輛中的戰(zhàn)場支持系統(tǒng)到用來尋找最近的比薩餅店的移動電話應用程序。這些應用程序基于空間查詢的算法，例如：找到離當前位置最近的對象，找到用戶附近的全部對象，等等。

B樹索引是一維的：它無法處理用于空間搜索的二維和三維坐標。R樹（又叫做Guttman R樹，根據(jù)發(fā)明者命名）是一個不錯的替代品。它使 用邊界盒（bounding box）來映射空間中的對象。如果一個對象由坐標點（X, Y）表示，那么他的邊界盒是一個邊長為1的正方形。

對所有的幾何對象（線、多邊形以及其他形狀），邊界盒是這樣一個長方形：其左上角坐標小于等于該對象中的任何點，其右下角坐標大于等于該對象中的任何點。換句話說，邊界長方形是能夠完全包含給定對象的最小長方形。

R樹索引通常被用來加速空間搜索（發(fā)現(xiàn)包含某個點的長方形、找出全部與給定長方形重合的長方形，諸如此類）。在邊界盒的幫助下，應用程序能夠管理各種形狀。

使用eXtremeDB的數(shù)據(jù)庫定義語言，空間對象可以被描述如下：

/* 表示地圖上點的結構 */  
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樹可以實現(xiàn)這種需求，但必須從最長的前綴開始進行多次迭代并且查詢不同的給定值前綴。

一種更加有效的前綴查找索引是用于查詢字母-數(shù)字編碼的實踐算法，即通常所說的Patricia trie。Patricia trie是二叉樹的一種變形，通常用于電話路由以及IP過濾。在第一種情況中，給定接入電話以及一張帶有已知前綴的接線員表，應用程序必須選擇正確的接線員接到該電話。在第二種情況下，給定了有效/拒絕域的IP掩碼，收到的(一個)HTTP請求應被分類為接受、拒絕、轉發(fā)，等等。下面的數(shù)據(jù)庫模式定義了一張路由表，帶有一個由位向量表示的掩碼。

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

為了給接受到的IP地址找到合適的轉發(fā)目標，應用程序使用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地址匹配的轉發(fā)節(jié)點*/  
if (MCO_S_OK == Route_by_dest_prefix_match(trans, &csr, mask, 32);  
Route route;  
Route_from_cursor(trans, &csr, &route);  
...  
}  
} 

下面的代碼將表示IP地址的整數(shù)轉換為位向量：

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的專用索引加快了代碼開發(fā)速度，提升了代碼效率，并使應用程序能夠處理更加復雜的數(shù)據(jù)結構。盡管著名的B樹足以處理大量的普通查詢任務，不怎么出名的索引類型能夠在專用應用程序和數(shù)據(jù)類型中做得更好。R樹能夠高效處理映射和地理空間數(shù)據(jù)，而Patricia trie是電話路由、IP過濾以及其他必須通過匹配特定數(shù)值最長前綴的關鍵字來完成的任務的理想方案。

Steve Graves是McObject公司的CEO和創(chuàng)始人之一。McObject公司專注于嵌入式數(shù)據(jù)庫系統(tǒng)軟件。在創(chuàng)立McObject之前，Steve曾擔任Centura Solutions公司總裁以及Centura Software公司（納斯達克股票代碼：CNTR）負責全球咨詢方面的副總裁。他還擔任Raima公司的總裁兼首席運營官?？梢酝ㄟ^steve.graves@mcobject.com與Steve聯(lián)系。

Konstantin Knizhnik是McObject公司的軟件工程師，參與了嵌入式數(shù)據(jù)庫系統(tǒng)eXtremeDB的開發(fā)。他同樣還是多個優(yōu)秀開源項目的作者，其中包括基于Java的數(shù)據(jù)庫管理系統(tǒng)Perst和Perst Lite，以及包括Java、C++和C#在內的多種編程語言的擴展工具?？梢酝ㄟ^knizhnik@mcobject.com與Konstantin聯(lián)系。如果您有任何問題可以和McObject中國區(qū)聯(lián)系。

【編輯推薦】

1. SQL優(yōu)化索引的實操與功能
2. MySQL索引被破壞所產(chǎn)生的問題解決
3. MySQL SQL優(yōu)化的索引問題詳解
4. Oracle數(shù)據(jù)庫索引的優(yōu)點與缺點簡介
5. Oracle數(shù)據(jù)庫中的最常用的索引有哪些