用好數據庫索引提升嵌入式軟件性能和效率
原創51CTO數據庫頻道也向您推薦《數據庫之索引與查詢專題》專題，相信這個專題能幫助您更好的理解本文。為了從一本書中獲取信息，怎樣做更有效？仔細閱讀每一頁內容，還是根據索引來精確確定要獲取信息的位置？
顯然后者更有效，嵌入式系統也應該能如此智能。如今，嵌入式應用程序管理著數量高速增長的復雜數據。找到正確的數據（無論是尋找網絡包的路由目標節點、計算地圖上點與點之間的距離、以及其他計算目標）通常必須在實時性能要求下被實現。
幸運的是，編程人員可以使用數據索引將查找速度從線性級別提升到對數級別。隨著成品數據庫管理系統（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過濾以及其他必須通過匹配特定數值最長前綴的關鍵字來完成的任務的理想方案。
Steve Graves是McObject公司的CEO和創始人之一。McObject公司專注于嵌入式數據庫系統軟件。在創立McObject之前，Steve曾擔任Centura Solutions公司總裁以及Centura Software公司（納斯達克股票代碼：CNTR）負責全球咨詢方面的副總裁。他還擔任Raima公司的總裁兼首席運營官?？梢酝ㄟ^steve.graves@mcobject.com與Steve聯系。
Konstantin Knizhnik是McObject公司的軟件工程師，參與了嵌入式數據庫系統eXtremeDB的開發。他同樣還是多個優秀開源項目的作者，其中包括基于Java的數據庫管理系統Perst和Perst Lite，以及包括Java、C++和C#在內的多種編程語言的擴展工具。可以通過knizhnik@mcobject.com與Konstantin聯系。如果您有任何問題可以和McObject中國區聯系。
【編輯推薦】
