建站
咨詢
售后
建站咨詢
新聞中心
數(shù)據(jù)庫頻道也向您推薦《數(shù)據(jù)庫之索引與查詢專題》專題，相信這個(gè)專題能幫助您更好的理解本文。為了從一本書中獲取信息，怎樣做更有效？仔細(xì)閱讀每一頁內(nèi)容，還是根據(jù)索引來精確確定要獲取信息的位置？
成都創(chuàng)新互聯(lián)公司是一家集網(wǎng)站建設(shè),長嶺企業(yè)網(wǎng)站建設(shè),長嶺品牌網(wǎng)站建設(shè),網(wǎng)站定制,長嶺網(wǎng)站建設(shè)報(bào)價(jià),網(wǎng)絡(luò)營銷,網(wǎng)絡(luò)優(yōu)化,長嶺網(wǎng)站推廣為一體的創(chuàng)新建站企業(yè)，幫助傳統(tǒng)企業(yè)提升企業(yè)形象加強(qiáng)企業(yè)競爭力。可充分滿足這一群體相比中小企業(yè)更為豐富、高端、多元的互聯(lián)網(wǎng)需求。同時(shí)我們時(shí)刻保持專業(yè)、時(shí)尚、前沿，時(shí)刻以成就客戶成長自我，堅(jiān)持不斷學(xué)習(xí)、思考、沉淀、凈化自己，讓我們?yōu)楦嗟钠髽I(yè)打造出實(shí)用型網(wǎng)站。
顯然后者更有效，嵌入式系統(tǒng)也應(yīng)該能如此智能。如今，嵌入式應(yīng)用程序管理著數(shù)量高速增長的復(fù)雜數(shù)據(jù)。找到正確的數(shù)據(jù)（無論是尋找網(wǎng)絡(luò)包的路由目標(biāo)節(jié)點(diǎn)、計(jì)算地圖上點(diǎn)與點(diǎn)之間的距離、以及其他計(jì)算目標(biāo)）通常必須在實(shí)時(shí)性能要求下被實(shí)現(xiàn)。
幸運(yùn)的是，編程人員可以使用數(shù)據(jù)索引將查找速度從線性級別提升到對數(shù)級別。隨著成品數(shù)據(jù)庫管理系統(tǒng)（DBMS）在嵌入式系統(tǒng)開發(fā)中的日趨重要，索引也得到了更多的使用，多數(shù)嵌入式數(shù)據(jù)庫都支持至少一種索引類型。
然而，在許多項(xiàng)目中，首先考慮（通常也是唯一的）索引是B樹。這是因?yàn)樵诂F(xiàn)有的大量索引類型中，只有B樹索引最為通用。毫無疑問，B樹能夠高效完成基本的搜索操作，諸如：精確匹配、前綴、范圍搜索等。然而，對于IP路由、映射、模式查詢算法開發(fā)等目標(biāo)來說，非通用的索引類型更加合適，并且能夠帶來更快的速度和對CPU時(shí)鐘周期等資源更有效地利用（見圖1）。
圖 1: B樹并不是嵌入式應(yīng)用程序唯一的索引選擇
下面章節(jié)展示了如何使用兩種非通用索引類型：R樹和Patricia trie
空間索引和R樹
映射(地圖)以及其他基于位置的功能在移動(dòng)嵌入式應(yīng)用中十分常見，這些應(yīng)用從戰(zhàn)斗車輛中的戰(zhàn)場支持系統(tǒng)到用來尋找最近的比薩餅店的移動(dòng)電話應(yīng)用程序。這些應(yīng)用程序基于空間查詢的算法，例如：找到離當(dāng)前位置最近的對象，找到用戶附近的全部對象，等等。
B樹索引是一維的：它無法處理用于空間搜索的二維和三維坐標(biāo)。R樹（又叫做Guttman R樹，根據(jù)發(fā)明者命名）是一個(gè)不錯(cuò)的替代品。它使 用邊界盒（bounding box）來映射空間中的對象。如果一個(gè)對象由坐標(biāo)點(diǎn)（X, Y）表示，那么他的邊界盒是一個(gè)邊長為1的正方形。
對所有的幾何對象（線、多邊形以及其他形狀），邊界盒是這樣一個(gè)長方形：其左上角坐標(biāo)小于等于該對象中的任何點(diǎn)，其右下角坐標(biāo)大于等于該對象中的任何點(diǎn)。換句話說，邊界長方形是能夠完全包含給定對象的最小長方形。
R樹索引通常被用來加速空間搜索（發(fā)現(xiàn)包含某個(gè)點(diǎn)的長方形、找出全部與給定長方形重合的長方形，諸如此類）。在邊界盒的幫助下，應(yīng)用程序能夠管理各種形狀。
使用eXtremeDB的數(shù)據(jù)庫定義語言，空間對象可以被描述如下：
- /* 表示地圖上點(diǎn)的結(jié)構(gòu) */
- struct Point
- {
- double latitude;
- double longitude;
- };
- class Street {
- /* 表示街道的點(diǎn)向量 */
- vector
points; - /* 街道封裝長方形 */
- rect
wrap_rect; - rtree
streets_idx; - };
如果我們希望加入一條新的街道，應(yīng)用程序必須存儲街道的坐標(biāo)并計(jì)算其邊界盒。
- 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);
如果用戶搜索一個(gè)位置，地圖應(yīng)用程序?qū)⒔Y(jié)果（街道）在窗口中表示為一個(gè)坐標(biāo)為||的地圖長方形。
- 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樹可以利用指定的前綴來定位關(guān)鍵字，例如，尋找以名字以“AAA”開頭的公司。然而，一些應(yīng)用程序必須搜索代表著一個(gè)特定值最長前綴的關(guān)鍵字。B樹可以實(shí)現(xiàn)這種需求，但必須從最長的前綴開始進(jìn)行多次迭代并且查詢不同的給定值前綴。
一種更加有效的前綴查找索引是用于查詢字母-數(shù)字編碼的實(shí)踐算法，即通常所說的Patricia trie。Patricia trie是二叉樹的一種變形，通常用于電話路由以及IP過濾。在第一種情況中，給定接入電話以及一張帶有已知前綴的接線員表，應(yīng)用程序必須選擇正確的接線員接到該電話。在第二種情況下，給定了有效/拒絕域的IP掩碼，收到的(一個(gè))HTTP請求應(yīng)被分類為接受、拒絕、轉(zhuǎn)發(fā)，等等。下面的數(shù)據(jù)庫模式定義了一張路由表，帶有一個(gè)由位向量表示的掩碼。
- class Route
- {
- Vector
dest; - uint4 gateway;
- uint4 interf;
- uint2 metric;
- unique patricia by_dest;
- };
為了給接受到的IP地址找到合適的轉(zhuǎn)發(fā)目標(biāo)，應(yīng)用程序使用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地址匹配的轉(zhuǎn)發(fā)節(jié)點(diǎn)*/
- if (MCO_S_OK == Route_by_dest_prefix_match(trans, &csr, mask, 32);
- Route route;
- Route_from_cursor(trans, &csr, &route);
- ...
- }
- }
下面的代碼將表示IP地址的整數(shù)轉(zhuǎn)換為位向量：
- 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);
- }
- }
可選索引越多，結(jié)果越好
使用諸如R樹和Patricia trie的專用索引加快了代碼開發(fā)速度，提升了代碼效率，并使應(yīng)用程序能夠處理更加復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。盡管著名的B樹足以處理大量的普通查詢?nèi)蝿?wù)，不怎么出名的索引類型能夠在專用應(yīng)用程序和數(shù)據(jù)類型中做得更好。R樹能夠高效處理映射和地理空間數(shù)據(jù)，而Patricia trie是電話路由、IP過濾以及其他必須通過匹配特定數(shù)值最長前綴的關(guān)鍵字來完成的任務(wù)的理想方案。
Steve Graves是McObject公司的CEO和創(chuàng)始人之一。McObject公司專注于嵌入式數(shù)據(jù)庫系統(tǒng)軟件。在創(chuàng)立McObject之前，Steve曾擔(dān)任Centura Solutions公司總裁以及Centura Software公司（納斯達(dá)克股票代碼：CNTR）負(fù)責(zé)全球咨詢方面的副總裁。他還擔(dān)任Raima公司的總裁兼首席運(yùn)營官?？梢酝ㄟ^[email protected]與Steve聯(lián)系。
Konstantin Knizhnik是McObject公司的軟件工程師，參與了嵌入式數(shù)據(jù)庫系統(tǒng)eXtremeDB的開發(fā)。他同樣還是多個(gè)優(yōu)秀開源項(xiàng)目的作者，其中包括基于Java的數(shù)據(jù)庫管理系統(tǒng)Perst和Perst Lite，以及包括Java、C++和C#在內(nèi)的多種編程語言的擴(kuò)展工具。可以通過[email protected]與Konstantin聯(lián)系。如果您有任何問題可以和McObject中國區(qū)聯(lián)系。
【編輯推薦】
- SQL優(yōu)化索引的實(shí)操與功能
- MySQL索引被破壞所產(chǎn)生的問題解決
- MySQL SQL優(yōu)化的索引問題詳解
- Oracle數(shù)據(jù)庫索引的優(yōu)點(diǎn)與缺點(diǎn)簡介
- Oracle數(shù)據(jù)庫中的最常用的索引有哪些
本文名稱：用好數(shù)據(jù)庫索引提升嵌入式軟件性能和效率
文章路徑：http://fisionsoft.com.cn/article/dhciess.html
