前言：想要寫出一篇令人眼前一亮的文章嗎？我們特意為您整理了5篇數(shù)據(jù)庫索引范文，相信會為您的寫作帶來幫助，發(fā)現(xiàn)更多的寫作思路和靈感。

數(shù)據(jù)庫索引范文第1篇

關(guān)鍵詞: 時空數(shù)據(jù)庫; 移動對象軌跡;索引

中圖分類號:TP311文獻(xiàn)標(biāo)識碼:A 文章編號:1009-3044(2010)02-268-03

Research on Spationtemporal Database Indices

ZHOU Yong-gang

(Department of Computer Technology, Anhui Vocational College of Posts and Telecom,Hefei 230031,China)

Abstract: To efficiently store, query and update trajectories of moving objects in spatio-temporal database,indexing techniques are sticking points. This paper thoroughly analyzed indexing methods for Spatio-Temporal Database, and finally some open researching problems and interesting direction were presented.

Key words: spatiotemporal database ; trajectories of moving objects; index

因為出現(xiàn)許多需要有效對移動對象管理的應(yīng)用,STDB受到很多關(guān)注。這些應(yīng)用需要在不同的時間戳記錄對象的地理位置(有時也記錄對象的形狀),而且支持對它們歷史的和將來預(yù)期的特征進(jìn)行查詢。

STDB的目的是根據(jù)數(shù)據(jù)的時間屬性作歷史性和預(yù)言性的檢索。具體地說,給定對象集合o1, o2,… , oN(N是基數(shù)),對于每個對象oi(1≤i≤N),歷史性STDB會存儲oi在歷史的所有時間戳t的有效范圍oi.E(t)。根據(jù)空間數(shù)據(jù)庫的原理,oi.E(t)能夠表示為一個描述對象在時刻t的真實形狀。尤其是,如果其形狀不是重要屬性,oi.E(t)則以一個點代替以表示oi在時刻t的位置。實際上,在連續(xù)時間戳,同一對象的有效范圍可以用不同的方法壓縮(例如:如果對象在幾個連續(xù)時間戳保持靜止,則它的有效范圍在該時間內(nèi)只需存儲一次)。

另一方面,對每個對象oi,預(yù)期性STDB會存儲它的最新更新的位置oi.L(tupd)(tupd:對象最新更新的時間)和用于描述它當(dāng)前移動特性時間函數(shù)。最適合的時間函數(shù)是線性函數(shù),因為1)線性函數(shù)能夠近似描述任何運動軌跡,2)線性函數(shù)要求的參數(shù)個數(shù)最少。具體來說,除了oi.L(tupd),系統(tǒng)只需記錄對象的速度oi.vel,就可以計算出在將來任何時刻t>tupd對象的位置:

oi.L(t) = oi.L(tupd)+oi.vel(t-tupd)

用這種模型只需在對象的時間函數(shù)的參數(shù)(如:速度)發(fā)生變化時采取更新數(shù)據(jù)庫。

人們已經(jīng)對作為支持時空查詢的輔助結(jié)構(gòu)的時空索引方法做了很多研究。時空存取方法主要集中在兩個正交方向:1)對對象過去位置的索引,2)對現(xiàn)在的位置和將來預(yù)期位置的索引。

1 移動對象歷史數(shù)據(jù)的時空索引

考慮到移動對象連續(xù)不斷發(fā)送它們的位置,保持所有的更新幾乎是不可能的。有兩種方法可用來減少歷史數(shù)據(jù):1)采樣,對數(shù)據(jù)流在某一時刻進(jìn)行采樣?？梢圆捎镁€性插值計算出相鄰采樣點間的線性軌跡。2)僅在變化時更新,移動對象僅當(dāng)它們的數(shù)據(jù)屬性(速度或方向)發(fā)生變化時才發(fā)送數(shù)據(jù)。我們把對歷史數(shù)據(jù)的時空索引機制分為三類。

第一類是在現(xiàn)存的空間索引方法加入時間屬性。這類時空索引方法主要是處理空間維,時間維是第二要素。

RT-tree[1]結(jié)合了作為空間存取方法的R樹和作為時間存取方法的TSB樹。在RT樹中,時間和空間信息是分開維護(hù)的。不管是葉結(jié)點還是非葉結(jié)點,每個索引項都包含(S,T, P) 形式。S是空間信息,T是時態(tài)信息(時間間隔), P是指向子樹或?qū)ο蟮闹羔?。隨著時間變化,如果對象空間位置不變,則它的空間信息S不變,僅對時態(tài)信息進(jìn)行更新。如果對象空間位置發(fā)生變化,則需要創(chuàng)建一個新的索引項插入RT樹。這種方法有許多局限性,一方面,如果變化對象的數(shù)量很大,許多索引項被創(chuàng)建,RT樹會迅速膨脹;另一方面,當(dāng)結(jié)點溢出時,怎樣分裂結(jié)點還沒有很好的解決辦法。

3D R-tree[2]把時間看作除了空間維以外的另一維。主要思想是為了避開時間和空間查詢之間的區(qū)別。3D R-tree可以直接利用現(xiàn)有的R樹算法來處理空間及時態(tài)查詢而無需修改,其前提是必須知道移動對象歷史軌跡存在的有效時間范圍,如果移動對象軌跡結(jié)束時刻不確定,那么3D R-tree將無法有效工作。比如若移動對象運動軌跡從某個歷史時刻開始一直延伸到當(dāng)前時刻,顯然包圍移動對象軌跡的3D MBR將會非常巨大且造成空間區(qū)域的大量重疊,直接導(dǎo)致3D R-tree的查詢搜索性能下降。因此,在應(yīng)用中要求移動對象軌跡是封閉的(closed),即移動對象歷史軌跡必須在某個過去時刻終止而不能延伸到當(dāng)前時刻。由于3D R-tree將時間維與空間維等同索引,時間片查詢則必須掃描整個3D R-tree而非在此時間片下的有效子樹, 因此性能非常低下。

第二類是同時把空間和時間加入某一結(jié)構(gòu)中,但它們是各自獨立的。這是為了使在某一時刻所有有效的空間數(shù)據(jù)同時在一個索引結(jié)構(gòu)(R-tree)中。最高目標(biāo)使為每一時間項都建立一個單獨的R-tree。這種方法需要很大的存儲量。

MR-tree[3]采用了在R-tree的背景下可重疊B-tree的思想。主要思想是避免每個時間戳都有單獨的R-tree而引起的存儲量過大。通過在連續(xù)的R-tree中不存儲相同的對象實現(xiàn)減少存儲量。作為替代,以不同根結(jié)點的鏈接指向同一結(jié)點,而所有的結(jié)點項都保存著它們在不同時間戳的值。這種思想對時間片查詢來說是完美的。搜索被指向適合的根結(jié)點,然后利用R-tree進(jìn)行空間搜索。然而,它對時間窗口查詢的執(zhí)行是無效的。而且,一個主要的缺陷是存在許多重復(fù)項?？紤]到這樣的情況,在連續(xù)兩個時間戳僅有一個結(jié)點項發(fā)生變化,而在這連續(xù)兩個R-tree的所有其它結(jié)點也必須重新復(fù)制。

HR-tree與[4]MR-tree非常相似。HR-tree是一種采用重疊技術(shù)、將單一版本的結(jié)構(gòu)轉(zhuǎn)換為部分固定結(jié)構(gòu)的高效時空索引結(jié)構(gòu)。該結(jié)構(gòu)為兩級索引機制,分別對時空對象的時間信息和空間信息進(jìn)行索引:1)HR-tree是對事務(wù)時間進(jìn)行索引,它按時間遞增順序?qū)r空對象的時間信息組織為有序表,并將時空對象不發(fā)生空間變化的那個時間片作為時空對象的時間信息值;2)用R-tree索引結(jié)構(gòu)為每個時間片的空間對象建立索引,并將R-tree的存儲信息(根結(jié)點存儲地址)保存到對應(yīng)時間片的時間索引結(jié)點中。為了節(jié)省空間,相鄰時間片的R-tree可能會重疊,即若相鄰時間片的R-tree有共同的分枝,則只保存該分枝的一個版本。

第三類是主要考慮時間維索引,其次考慮空間維。第三類方法主要集中在面向軌跡的查詢。在此類中處理空間查詢處于次要位置。

Trajectory-bundle(TB-tree)[5]是完全保持軌跡的類似R-tree結(jié)構(gòu)。一個葉子結(jié)點僅能包含屬于同一軌跡的線段。存在一個缺陷:在空間上比較靠近的不同軌跡的線段將被存儲在不同的結(jié)點上。構(gòu)建TB-tree是從左到右的原則。也就是說。最左邊的結(jié)點是最先插入的結(jié)點,最右邊的結(jié)點是最后插入的結(jié)點。

Scalable and Efficient Trajectory Index(SETI)[6]將空間區(qū)域分割成靜態(tài)且不重疊的分區(qū),在每個分區(qū)下對移動對象的軌跡線段利用R樹進(jìn)行索引。其考慮是,相對于無限連續(xù)變化的時間維而言,移動對象軌跡受空間范圍所限,那么可以把受限的空間區(qū)域利用某種規(guī)則靜態(tài)劃分以分而治之。良好的劃分函數(shù)應(yīng)盡量把同一移動對象不同軌跡線段聚類在同一個分區(qū)中。若一條軌跡線段穿過多個分區(qū),那么必須將此線段裁剪并分別存儲在不同分區(qū)R樹中,這樣會導(dǎo)致查詢結(jié)果的重復(fù),在查詢處理后必須進(jìn)行重復(fù)結(jié)果的剔出。相應(yīng)地,時態(tài)查詢則被轉(zhuǎn)換為對折線段集合的空間窗口查詢,利用幾何計算方法可以得到空間窗口內(nèi)的折線段集合,其對應(yīng)的移動對象集合即是時態(tài)查詢結(jié)果。

2 移動對象當(dāng)前位置軌跡索引

在現(xiàn)實應(yīng)用中許多要求能夠有效地對移動對象當(dāng)前位置進(jìn)行管理和查詢。相對來說,檢索移動對象當(dāng)前位置更具有挑戰(zhàn)性,其關(guān)鍵在于如何提高傳統(tǒng)空間索引的頻繁更新動態(tài)性能以滿足動態(tài)環(huán)境下的應(yīng)用要求。標(biāo)準(zhǔn)R樹更新算法采用刪除-重插機制來實現(xiàn)移動對象位置更新,頻繁更新會導(dǎo)致R樹性能急劇下降。為了支持R樹的頻繁更新操作,近年來提出的方法包括LUR樹(Lazy Update R-tree)、自底向上更新策略(Bottomup Update)、哈希方法(Hash)等。LUR[7]提出了一種延遲更新(Lazy Update)策略,即若移動對象位置未超出當(dāng)前節(jié)點MBR,算法僅僅更新移動對象所在的數(shù)據(jù)頁面并維持索引頁面不變;對于移出MBR之外的移動對象,根據(jù)其超出MBR程度大小,判斷是否將MBR進(jìn)行有限擴展以包含移動對象新位置;或者利用標(biāo)準(zhǔn)R樹更新算法進(jìn)行更新以盡量減少位置更新所帶來的索引樹更新操作。Bottom-up Updates的自底向上法擴展了LUR-tree思想。自底向上法比較適合處理移動對象的連續(xù)更新。例如:擴展MBR以包含新的值和移動當(dāng)前對象到兄弟結(jié)點。

Song 等人利用空間劃分的思想來索引移動對象當(dāng)前位置,首先靜態(tài)地把空間劃分為可以相互重疊的區(qū)域,然后根據(jù)當(dāng)前位置將移動對象哈希映射到不同區(qū)域中去。只有當(dāng)移動對象位置超出了當(dāng)前區(qū)域才會更新此對象的索引記錄,數(shù)據(jù)庫中保存了移動對象位置近似視圖。

3 當(dāng)前和將來軌跡查詢索引

在移動計算、位置服務(wù)等新興應(yīng)用中,需要對移動對象當(dāng)前及未來位置預(yù)測以提供相關(guān)服務(wù),針對移動對象當(dāng)前和未來軌跡的索引方法是目前研究的熱點。為了能夠預(yù)測移動對象未來軌跡,需要存儲一些額外的信息(如移動對象當(dāng)前速度和目的地等)。然后根據(jù)移動對象當(dāng)前的運動特性對未來軌跡進(jìn)行預(yù)測,目前通常使用線性方程來描述移動對象的運動特性。在D維空間下,移動對象運動特性可以使用參考時間tref時位置xref = ( x1,x2,…,xd )以及速度矢量v=(v1,v2,…,vd )來描述。移動對象在任何時間點t (t≥tref )的位置可利用公式xt = xref +v (t- tref )計算得出。主要的索引方法有:FT-Quadtree、PMR-Quadtree、STRIPE索引、TPR-tree、TPR*-tree等。

FT-Quadtree[8]使用的是Quad-tree索引結(jié)構(gòu),最大的特點是使用了軌跡共享技術(shù)來最大限度地減少數(shù)據(jù)的存儲數(shù)量,提高索引的更新效率。在這種樹中的葉子節(jié)點結(jié)構(gòu)表示為(oid,軌跡的數(shù)量,起始坐標(biāo),結(jié)束坐標(biāo),起始時間,結(jié)束時間,其他信息)。對于在同一時間內(nèi)的節(jié)點而言,如果它們的坐標(biāo)位置相同或者接近,那么就可以采取共享策略把若干個節(jié)點的內(nèi)容放入一個公共的節(jié)點內(nèi),這樣就可以明顯地減少存儲的空間。

使用PMR-quadtree[9]作為索引將來軌跡的基本空間存取方法,關(guān)鍵的一點是當(dāng)移動對象發(fā)生更新時,整個索引結(jié)構(gòu)被破壞,然后根據(jù)新的信息重建索引結(jié)構(gòu)。為了避免過多的更新操作,索引每ΔT時間單元重建。在理論上,無限的時間維可以分割為大小為ΔT的相等的時間片。對于每一時間片,會構(gòu)建一個新的基于運動方程的PMR-tree。然而,由于存儲設(shè)備的有限性,只有當(dāng)前的PMR-tree會被存儲。

TPR-tree[10]使用時間參數(shù)化包圍框來包含移動對象,其索引結(jié)構(gòu)與R樹類似。但TPR-tree采用謹(jǐn)慎的BR策略,在某些時刻(如構(gòu)建時刻)包圍框是最小的,但在其后的時間內(nèi)往往不是。從一維角度考慮,MBR最(大)小邊界速度為其范圍內(nèi)所有點的最(大)小速度,從而保證所有點始終包含在同一個MBR中。TPR-tree索引節(jié)點記錄不僅存儲了移動對象(子樹)MBR,而且包含了移動對象(子樹)MBR速度矢量。由于節(jié)點MBR呈現(xiàn)出一種隨時間變化的動態(tài)性,隨著時間延伸包圍框會越來越大,導(dǎo)致空間區(qū)域的大量重疊從而使得性能下降。因此,必須在適當(dāng)時候?qū)PR-tree進(jìn)行重構(gòu)以提高查詢性能。

TPR*-tree[11]修改了TPR-tree的動態(tài)操作算法。通過維護(hù)一個代價下降優(yōu)先隊列保證插入路徑選擇的全局最優(yōu),保持TPR-tree MBR的緊致性以提高查詢性能。對于上溢節(jié)點的分裂算法,TPR*-tree只是在必要的時候才對節(jié)點分裂并重插。以二維空間移動對象為例,節(jié)點首先在所有可能的8個方向(4×d)上進(jìn)行排序,并從中選擇一種最好的分裂方式,實際上此時節(jié)點并不分裂,而是把節(jié)點中30 %的記錄刪除后重插。如果在重插過程中發(fā)生上溢,那么就直接進(jìn)行節(jié)點分裂以避免傳遞操作。TPR*-tree是目前最好的參數(shù)化空間訪問方法。

4 結(jié)束語

該文總結(jié)了移動對象軌跡索引的各種技術(shù),并對它們進(jìn)行了比較詳細(xì)的分類,對每種方法均找出了多個比較典型的模型進(jìn)行介紹。近年來對移動對象歷史軌跡、當(dāng)前位置與未來趨勢預(yù)測的索引方法研究較多,在如何同時解決上述三種查詢的索引方法上研究仍然欠缺。多種索引結(jié)構(gòu)的結(jié)合是時空數(shù)據(jù)庫系統(tǒng)實際設(shè)計的主要趨勢,選擇哪幾種索引結(jié)構(gòu)以及如何把它們有機地結(jié)合起來將是系統(tǒng)設(shè)計所面臨的主要難題。

參考文獻(xiàn):

[1] Xu X, Han J, Lu W. RT-Tree: An Improved R-Tree Indexing Structure for Temporal Spatial Databases. In Proc. of the Intl. Symp. on Spatial Data Handling, SDH, pages 1040C1049, July 1990.

[2] Basch J, Guibas L J, Hershberger J. Data structures for mobile data. In Proc. of the ACM-SIAM symposium on Discrete algorithms, SODA, pages 747C756, 1997.

[3] Xu X, Han J, Lu W. RT-Tree: An Improved R-Tree Indexing Structure for Temporal Spatial Databases. In Proc. of the Intl. Symp. on Spatial Data Handling, SDH, pages 1040C1049, July 1990.

[4] Nascimento M A, Silva J R O. Towards historical R-trees. In Proc. of the ACM Symp. on Applied Computing, SAC, pages 235C240, Feb 1998.

[5] Pfoser D, Jensen C S, Theodoridis Y. Novel Approaches in Query Processing for Moving Object Trajectories. In Proc. of the Intl. Conf. on Very Large Data Bases, VLDB, pages 395C406, Sept. 2000.

[6] Chakka V P, Everspaugh A, Patel J M. Indexing Large Trajectory Data Sets with SETI. In Proc. of the Conf. on Innovative Data Systems Research, CIDR, Asilomar, CA, Jan. 2003.

[7] Kwon D, Lee S, Lee S. Indexing the Current Positions of Moving Objects Using the Lazy Update R-t ree[C]// In :Proc. of MDM,2002.

[8] Ding R, Meng X F, Bai Y. Efficient Index Maintenance for Moving Objects with Future Trajectories[C]// Kyoto: The 8th International Conference on Database Systems for Advanced Applications(DASFAA), 2003. 183.

[9] Tayeb J, Ulusoy O, Wolfson O. A Quadtree-Based Dynamic Attribute Indexing Method. The Computer Journal,41(3):185C200, 1998.

數(shù)據(jù)庫索引范文第2篇

作者簡介:劉波（1983-）,男，河南信陽人，博士研究生，主要研究方向：分布式實時數(shù)據(jù)庫、衛(wèi)星遙感信息處理； 范士明（1945-）,男,上海人，研究員,碩士,主要研究方向：衛(wèi)星遙感信息處理； 劉華（1969-）,男,重慶人，高級工程師,碩士,主要研究方向：衛(wèi)星遙感信息處理。

文章編號:1001-9081（2011）08-02265-05doi:10.3724/SP.J.1087.2011.02265

（中國航天科技集團公司第五研究院 五零三研究所，北京100086）

（.cn）

摘 要:在衛(wèi)星地面設(shè)備監(jiān)控中，需要將大量實時數(shù)據(jù)實時地存進(jìn)數(shù)據(jù)庫并提供實時查詢。針對實時數(shù)據(jù)和Judy array數(shù)字樹的特點，提出了一種基于內(nèi)存映射文件的位圖分配法，然后設(shè)計了一種哈希表、B+樹和Judy array混合索引機制。通過大量記錄的插入和查詢，結(jié)果表明位圖分配法能避免大量不可利用的內(nèi)存碎片的產(chǎn)生，結(jié)合內(nèi)存位圖分配法的混合索引機制也為應(yīng)用程序提供了實時的索引插入和查詢。

關(guān)鍵詞:實時數(shù)據(jù)庫；位圖分配法；內(nèi)存映射文件；哈希表；B+樹;Judy array

中圖分類號: TP311.131文獻(xiàn)標(biāo)志碼:A

Design and implementation of hybrid index mechanism for real-time database

LIU Bo, FAN Shi-ming, LIU Hua

（503 Institute, the Fifth Academy of China Aerospace Science and Technology Corporation, Beijing 100086, China）

Abstract: It is necessary to store massive real-time data into database and query records from database in real-time on the field of satellite ground device monitoring. Taking account of the characteristics of real-time data and Judy array, a bitmap memory allocation method based on memory map file was proposed. A hybrid index mechanism which employed Hash table, B+ tree and Judy array was designed. Through insertion and querying of massive records, the experimental results show that bitmap allocation method avoids the generation of massive tiny memory holes. Being combined with bitmap allocation method, the hybrid index mechanism provides real-time index insertion and record querying for applications.

Key words: real-time database; bitmap allocation method; memory map file; Hash table; B+ tree; Judy array

0 引言

衛(wèi)星地面設(shè)備監(jiān)控系統(tǒng)需要對大量數(shù)據(jù)信息進(jìn)行采集、傳輸、綜合分析、計算等處理。從監(jiān)控系統(tǒng)組成可以看出，數(shù)據(jù)是聯(lián)系各功能模塊的紐帶。隨著衛(wèi)星地面應(yīng)用系統(tǒng)的發(fā)展，地面設(shè)備監(jiān)控系統(tǒng)的功能需求也不斷增多、增強，數(shù)據(jù)量也不斷擴大，數(shù)據(jù)之間的關(guān)系也越來越復(fù)雜。因此需要將數(shù)據(jù)庫技術(shù)引入衛(wèi)星地面設(shè)備監(jiān)控，用數(shù)據(jù)庫技術(shù)來管理、處理監(jiān)控過程中的數(shù)據(jù)。但衛(wèi)星地面設(shè)備監(jiān)控中數(shù)據(jù)的一個顯著特點是具有時間特性，且有效時間是短暫的，過時則失效。而以關(guān)系數(shù)據(jù)庫為代表的傳統(tǒng)數(shù)據(jù)庫的設(shè)計目標(biāo)是維護(hù)數(shù)據(jù)的正確性、保證系統(tǒng)的低代價和提供友好的用戶接口。這種數(shù)據(jù)庫系統(tǒng)對傳統(tǒng)的商務(wù)和事務(wù)型應(yīng)用是有效、成功的，但對于新領(lǐng)域的實時數(shù)據(jù)和實時事務(wù)的應(yīng)用要求難以勝任。所以，需要結(jié)合數(shù)據(jù)庫技術(shù)和實時技術(shù)，研究具有顯式定時限制的實時數(shù)據(jù)庫系統(tǒng)［1］。

鍵值（key-value）型索引性能的好壞直接影響實時數(shù)據(jù)庫的穩(wěn)定性、可靠性、實時性。在衛(wèi)星地面設(shè)備監(jiān)控中，實時數(shù)據(jù)庫將面臨超大量的實時數(shù)據(jù)，最新的實時數(shù)據(jù)必須能在一定時間內(nèi)存入數(shù)據(jù)庫，相對陳舊的歷史數(shù)據(jù)在給定key時必須能在一定時間內(nèi)檢索到相應(yīng)的值。傳統(tǒng)的鍵值型索引并沒考慮到這種超大量實時數(shù)據(jù)的特點，導(dǎo)致其在內(nèi)存空間的利用效率、索引插入和查詢的實時性上很難達(dá)到要求。對此本文根據(jù)地面設(shè)備監(jiān)控中實時數(shù)據(jù)的特點以及檢索要求，采用內(nèi)存映射文件技術(shù)處理數(shù)據(jù)文件的讀取，提高了數(shù)據(jù)文件的I/O讀寫速度；利用位圖分配法代替操作系統(tǒng)的內(nèi)存分配，可以避免大量內(nèi)存碎片，提高數(shù)據(jù)庫文件存儲空間的利用率；采用混合索引取代數(shù)據(jù)庫中常用的哈希表、B+樹、T樹索引機制，實現(xiàn)了索引壓縮和有序存儲，并保證記錄的實時插入和查詢。

1 基于內(nèi)存映射文件的位圖分配法

1.1 內(nèi)存文件映射機制

內(nèi)存映射文件允許在進(jìn)程的虛擬地址空間中保留一段內(nèi)存區(qū)域，并將物理存儲器中的目標(biāo)文件提交給該區(qū)域，映射到這段虛擬內(nèi)存之中。這樣，物理存儲器來自一個已經(jīng)位于磁盤上的存儲近期實時歷史數(shù)據(jù)的文件，而不是系統(tǒng)的頁文件。一旦該文件被映射，就可以用存取內(nèi)存數(shù)據(jù)的方式直接操作文件中的數(shù)據(jù)，就像整個文件已經(jīng)被加載到內(nèi)存中一樣。因此使用內(nèi)存映射文件處理存儲在磁盤上的文件時，將不必再對文件執(zhí)行I/O操作，這意味著對文件進(jìn)行處理時將不必再為文件申請并分配緩存，所有的文件緩存操作均由系統(tǒng)直接管理，由于取消了將文件數(shù)據(jù)加載到內(nèi)存、數(shù)據(jù)從內(nèi)存到文件的回寫以及釋放內(nèi)存塊等步驟，使得內(nèi)存映射在處理實時數(shù)據(jù)庫這種有著大數(shù)據(jù)量的文件時有顯著的優(yōu)勢。

實時數(shù)據(jù)庫必須作為多個進(jìn)程共享數(shù)據(jù)的倉庫。內(nèi)存映射文件正是計算機操作系統(tǒng)提供的解決多個進(jìn)程間共享數(shù)據(jù)的最有效方法。數(shù)據(jù)共享通過讓多個進(jìn)程映射同一文件內(nèi)核對象的視圖來實現(xiàn)的，這意味著進(jìn)程間將共享物理存儲器中的同一個數(shù)據(jù)庫文件。因此，當(dāng)一個進(jìn)程將數(shù)據(jù)寫入一個共享文件映射對象的視圖時，其他進(jìn)程可以立即看到它們視圖中的數(shù)據(jù)變更情況。同時，內(nèi)存映射文件將作為數(shù)據(jù)庫持久存儲的手段。當(dāng)事務(wù)提交時，如果內(nèi)存中相應(yīng)于磁盤文件的頁面發(fā)生了改變，調(diào)用操作系統(tǒng)的內(nèi)外存交換機制，將事務(wù)對數(shù)據(jù)庫的更新操作保存在磁盤上。此時持久化到磁盤上的文件將作為數(shù)據(jù)庫的后端備份，一旦應(yīng)用程序出錯或掉電導(dǎo)致內(nèi)存數(shù)據(jù)丟失時，磁盤文件將被重新映射，使數(shù)據(jù)庫能盡可能快地從故障中恢復(fù)過來。

1.2 位圖分配法

實時數(shù)據(jù)庫系統(tǒng)中，內(nèi)存分配要求實時高效。本文借助位圖［2-3］實現(xiàn)內(nèi)存分配，根據(jù)系統(tǒng)配置大小設(shè)定共需多少個位圖頁面，每個位圖頁面為4KB，因此共有32K比特位，每個比特位可分配8B（也可以不是8B，可根據(jù)系統(tǒng)配置要求而定）。如果該位為0，表示該比特位代表的相應(yīng)位置的8B尚未分配，否則相應(yīng)位置的8B已分配出去，因此一個位圖頁面可分配的空間為256KB。文件頭包含數(shù)據(jù)庫文件的描述信息，頁面地址分別指向各自的位圖頁面首地址，n個位圖頁面連續(xù)集中在一起，可減少因位圖頁面過于分散而導(dǎo)致的內(nèi)存碎片較多的問題。每個位圖頁面負(fù)責(zé)其分配的區(qū)域，如位圖頁面0負(fù)責(zé)分配第一個256KB，位圖頁面1負(fù)責(zé)分配第2個256KB。

1）位圖頁面內(nèi)尋找可分配空間過程。

如下代碼所示，其中pos以字節(jié)為單位,i表示正搜尋的位圖頁面編號（從0開始）；offs指當(dāng)前位圖頁面搜尋的起始點，以字節(jié)為單位，其范圍是（0,…,4K-1）；mask為offs位置上的值，單字節(jié)長度；holeBitSize指目前搜尋到的連續(xù)的比特0數(shù)目；size指請求分配的字節(jié)數(shù)，objBitSize指分配size所需比特數(shù)；PageSize是頁面大小，4KB；firstHoleSize［mask］指mask中從最低位往最高位數(shù)起的第一個連續(xù)比特0個數(shù)；maxHoleSize［mask］表示mask中最多的連續(xù)比特0個數(shù)，代表可分配的最大空間；maxHoleOffset［mask］為最多的連續(xù)比特0個數(shù)區(qū)域在mask中的位置；lastHoleSize［mask］表示從最高位往最低位數(shù)起的連續(xù)的比特0個數(shù)；mask的值為（0,…,255），它們有各自的firstHoleSize、lastHoleSize、maxHoleSize、maxHoleOffset。

if（holeBitSize+firstHoleSize［mask］）≥objBitSize{

pos8×（（i×PageSize+offs）*8-holeBitSize）;

如果從pos開始size大小的區(qū)域尚未保留,保留這片區(qū)域,將位圖頁面中pos開始size大小的相應(yīng)位全置1,然后撤銷保留區(qū)域，內(nèi)存分配成功,返回pos；否則,offs增加（objBitSize+7）/8,holeBitSize置0,繼續(xù)搜索可分配空間

}else if（maxHoleSize［mask］≥objBitSize）{

pos8×（（i×PageSize+offs）×8-maxHoleOffset［mask］）;

如果從pos開始size大小的區(qū)域尚未保留,保留這片區(qū)域,將位圖頁面中pos開始size大小的相應(yīng)位全置1,然后撤銷保留區(qū)域，內(nèi)存分配成功,返回pos；否則,offs增加（objBitSize+7）/8,holeBitSize置0,繼續(xù)搜索可分配空間

}else if（上述兩條件都沒有滿足）{

如果lastHoleSize［mask］等于8,將holeBitSize加8；否則將holeBitSize設(shè)置為lastHoleSize［mask］

offs加1;

}

如果offs≥PageSize,這時搜尋到下個位圖頁面,置offs為0,i加1

2）擴展位圖頁面過程。

當(dāng)搜尋全部位圖頁面后，還沒能找到指定大小的空間，則需要增加新的位圖頁面，此時等于擴展可分配的內(nèi)存空間。extension為新擴展的內(nèi)存空間大小，morePages為重新開辟的位圖頁面數(shù)目，n是未擴展前系統(tǒng)中已有的位圖頁面?zhèn)€數(shù)。擴展內(nèi)存空間通過增加新的位圖頁面完成，為減少內(nèi)存碎片，也為了確保未擴展前已搜尋到的holeBitSize個比特0位同新擴展空間中的objBitSize個比特0位連續(xù)，在新位圖頁面前添加若干內(nèi)存頁面（如果holeBitSize為0，不必附加這片空間）。附加的內(nèi)存頁面?zhèn)€數(shù)skip（objBitSize×8）/PageSize。當(dāng)擴展完成后，找到足夠空間，返回剛分配空間的起始地址pos（以字節(jié)為單位）。當(dāng)holeBitSize不為0,因找不到足夠大小的空間而引起的內(nèi)存擴展過程描述如下所示：

1）令morePages為滿足morePages×PageSize×64≥extension+morePages×PageSize的最小整數(shù),將objBitSize減去holeBitSize;

2）令skip為滿足skip×PageSize≥objBitSize×8的最小整數(shù),置pos為n×PageSize×64+skip×PageSize;

3）將數(shù)據(jù)庫表文件中范圍為［0,pos+morePages×PageSize］的部分重新文件映射;

4）置pos位置后從第1到第objBitSize個比特位為1,置從第PageSize×skip/8個比特位開始的morePages×PageSize/8個比特位為1；

5）將每個位圖頁面的首地址賦給相應(yīng)的位圖頁面,令pos為（n×PageSize×8-holeBitSize）×8,并將［pos,pos+holeBitSize×8］這段區(qū)域在位圖頁面中的相應(yīng)比特位置1。

2 Judy array數(shù)字樹

通常情況下,數(shù)字樹［4］根據(jù)索引的范圍劃分為層次樹，當(dāng)插入或刪除索引時，不需要對樹進(jìn)行平衡操作；對索引的查找、插入、刪除等操作的執(zhí)行時間依賴于索引本身，而不依賴于整棵樹的節(jié)點個數(shù)。數(shù)字樹的每個節(jié)點都是一數(shù)組，不同層的數(shù)組存儲索引的不同連續(xù)N位信息。數(shù)字樹的缺點在于當(dāng)數(shù)字樹的分支較多時，空指針的相對比例較高，樹的內(nèi)存利用率較低；另一方面，當(dāng)樹的分支較少時，雖然空指針的相對比例降低，樹的內(nèi)存利用率高，但當(dāng)操作某個索引時，分支較少的數(shù)字樹需更多的指針來定位value，這將導(dǎo)致不能充分利用程序的局部性原理，使得CPU高速緩存（cache）的命中率降低［5］，大大減緩了指令執(zhí)行速度。

Judy array［6-7］采用一種壓縮256階數(shù)字樹（即數(shù)字樹的每層存儲的是索引的一字節(jié)），根據(jù)節(jié)點內(nèi)部存儲的索引個數(shù)自動調(diào)整節(jié)點內(nèi)部結(jié)構(gòu)和樹本身結(jié)構(gòu)，達(dá)到壓縮節(jié)點節(jié)省內(nèi)存的目的。節(jié)點的自適應(yīng)壓縮通過如下方式：1）當(dāng)前范圍索引數(shù)較少時，節(jié)點壓縮為線性節(jié)點或位圖型節(jié)點。2）“窄節(jié)點指針”指向的葉子節(jié)點或分支節(jié)點能跨越多層，即節(jié)點中索引的公共字節(jié)部分可以存放在“窄節(jié)點指針”里。3）借助“立即指針”，將索引直接存儲在分支節(jié)點里;同時所有調(diào)整是自適應(yīng)的，不需要輔助參數(shù)對其進(jìn)行性能上的優(yōu)化調(diào)整。

2.1 分支節(jié)點、葉子節(jié)點

Judy array數(shù)字樹有如下5種節(jié)點。其中線性葉子節(jié)點可存儲多字節(jié)（指索引中未解碼的字節(jié)個數(shù)）索引，位圖葉子節(jié)點只能存儲1字節(jié)索引。線性葉子節(jié)點溢出時會轉(zhuǎn)換成位圖葉子節(jié)點，這種轉(zhuǎn)換僅發(fā)生在索引中剩余的未解碼部分還剩一字節(jié)時。位圖被均勻劃分成8部分，每部分由32個比特位構(gòu)成，其中如果有任一比特位為1，則有一指針指向存儲了索引相應(yīng)信息的數(shù)組，否則該指針為空。因此必須依據(jù)位圖的比特位信息獲得索引在數(shù)組中的偏移。

1）線性分支節(jié)點。第1個字節(jié)存儲當(dāng)前數(shù)組中存儲的有效索引的數(shù)目，后面7字節(jié)存儲包含索引的子范圍的編號（0到255之間），接下來的56字節(jié)存儲至多7個“節(jié)點指針”，用于指向樹的下層葉子節(jié)點或分支節(jié)點。

2）位圖分支節(jié)點。首先存儲256個比特位，用比特位0或1表明相應(yīng)的子范圍是否包含有效索引，如果沒有用0表示，反之用1表示。接下來是8指針，分別指向至多存儲了32個“節(jié)點指針”的數(shù)組，依據(jù)數(shù)組元素多少，數(shù)組大小分別為2,4,6,8,12,16,24,32,48,64個word。

3）未壓縮分支節(jié)點。包含了256個“節(jié)點指針”的數(shù)組，“節(jié)點指針”指向下層的葉子節(jié)點或分支節(jié)點，該分支節(jié)點占用2048B空間。

4）線性葉子節(jié)點。當(dāng)前葉子節(jié)點包含的索引個數(shù)及索引字節(jié)數(shù)（1到3字節(jié)）存儲在指向葉子節(jié)點的“節(jié)點指針”里，首先存儲若干索引，然后存儲每個索引對應(yīng)的值域，值域中存放指向值的指針（對于大于4字節(jié)的值）或是值本身（小于等于4字節(jié)的值）。

5）位圖葉子節(jié)點。只有當(dāng)節(jié)點中未解碼字節(jié)數(shù)剩1時，線性葉子節(jié)點才會轉(zhuǎn)化為位圖葉子節(jié)點。類似位圖分支節(jié)點，指針為普通指針，每個指針指向存儲了值域的數(shù)組，該數(shù)組類似位圖分支節(jié)點中的數(shù)組，不同的是它存儲索引相應(yīng)的值。

2.2 “節(jié)點指針”

“節(jié)點指針”指向樹的分支節(jié)點或葉子節(jié)點，占2word?！肮?jié)點指針”中的1word是普通指針，用于指向下層節(jié)點，D域（存儲索引集合中公共字節(jié)）和P域（存儲的索引個數(shù)）共占3字節(jié)，T域（“節(jié)點指針”類型）占1字節(jié)，它們共同占用1word。“節(jié)點指針”總駐留在分支節(jié)點里，所以索引的首字節(jié)已經(jīng)確定，其尾字節(jié)在葉子節(jié)點中也可確定，因此分支節(jié)點所指索引集合的公共字節(jié)個數(shù)至多為2（針對32位平臺，64位平臺為6）。D域和P域的界限是浮動的，當(dāng)“節(jié)點指針”所指節(jié)點層次低時，P域字節(jié)少，D域字節(jié)多；當(dāng)節(jié)點層次高時，P域字節(jié)多，D域字節(jié)少，32位平臺上3字節(jié)足夠存儲D域和P域。

“窄節(jié)點指針”指的是跨越了多個層次的“節(jié)點指針”，其D域中存放了索引集合的公共字節(jié)?！肮?jié)點指針”可不指向葉子節(jié)點或分支節(jié)點，能直接將索引存放在“節(jié)點指針”里，這種存放了索引的“節(jié)點指針”稱為“立即節(jié)點指針”。“立即節(jié)點指針”只能存儲非常少量索引，32位平臺上“立即節(jié)點指針”只能存儲一個3字節(jié)的索引。當(dāng)插入索引引起“立即節(jié)點指針”溢出時，它轉(zhuǎn)換成一指向葉子節(jié)點的“節(jié)點指針”，這時葉子節(jié)點存放的是原先存儲在“立即節(jié)點指針”里的索引和新插入的索引。

2.3 插入索引過程

下面描述了當(dāng)插入索引時Judy array的節(jié)點變化過程，刪除索引等同于插入索引的逆過程。

1）空的根指針指向沒有存儲任何索引的數(shù)字樹。

2）插入第1到31個索引時，根指針指向單個樹根葉子節(jié)點（樹根葉子節(jié)點與線性和位圖葉子節(jié)點不同，但結(jié)構(gòu)類似于線性葉子節(jié)點）。依據(jù)索引個數(shù)不同，樹根葉子節(jié)點分別需占用2,4,6,8,12,16,24,32,48,64個word空間。

3）當(dāng)樹根葉子節(jié)點溢出時，即插入索引個數(shù)大于等于32時，葉子節(jié)點轉(zhuǎn)化為分支節(jié)點，分支節(jié)點存儲若干“節(jié)點指針”，“節(jié)點指針”指向下層分支節(jié)點或葉子節(jié)點或直接存儲索引。

4）當(dāng)“立即節(jié)點指針”溢出時，它轉(zhuǎn)換為普通“節(jié)點指針”，指向線性葉子節(jié)點。當(dāng)進(jìn)一步插入更多索引時，它可能會轉(zhuǎn)換為一指向位圖葉子節(jié)點的“節(jié)點指針”（只有當(dāng)線性葉子節(jié)點存儲的是1字節(jié)索引時才可能轉(zhuǎn)換為位圖葉子節(jié)點）。

5）當(dāng)插入索引導(dǎo)致葉子節(jié)點溢出時，算法檢查是否可將葉子節(jié)點中的索引和新插入的索引壓縮存儲在當(dāng)前葉子節(jié)點，因為索引字節(jié)數(shù)減少，葉子節(jié)點可容納更多索引。這時其“父節(jié)點指針”將轉(zhuǎn)換為“窄節(jié)點指針”或者當(dāng)“父節(jié)點指針”原先就是“窄節(jié)點指針”時將轉(zhuǎn)換為“更窄”的“節(jié)點指針”，圖1展示了32位平臺上數(shù)字樹的某一“節(jié)點指針”轉(zhuǎn)為“窄節(jié)點指針”的過程。

圖1 “節(jié)點指針”轉(zhuǎn)化為“窄節(jié)點指針”示例

6）隨著索引的更多插入，導(dǎo)致存儲2～4字節(jié)（針對32位平臺）索引的線性葉子節(jié)點溢出時，如果它不能降低自身層次而成為“窄節(jié)點指針”所指的線性葉子節(jié)點，那么會生成一新的分支節(jié)點，將新節(jié)點插在父“節(jié)點指針”和線性葉子節(jié)點間，這時線性葉子節(jié)點會分裂為至少兩個節(jié)點，如圖2所示。一般情況下新插入的分支節(jié)點將是線性分支節(jié)點，但如果先前的線性葉子節(jié)點中的索引具有較大隨機分布性質(zhì)時，新插入的分支節(jié)點將可能是位圖型分支節(jié)點。

圖2 線性葉節(jié)點分裂為低層葉節(jié)點示例

7）當(dāng)插入新索引到“窄節(jié)點指針”所指的葉子節(jié)點或分支節(jié)點時，如果新索引對“窄節(jié)點指針”所指節(jié)點是“外來者”（即新索引在“窄節(jié)點指針”能表示的范圍之外），算法生成一新的線性分支節(jié)點，將其插入在“窄節(jié)點指針”和“窄節(jié)點指針”所指節(jié)點之間，新插入索引將作為一“立即節(jié)點指針”而存放在新的線性分支節(jié)點里，此時新的線性分支節(jié)點具有兩個分支。圖3展示了在64位平臺上插入新索引到“窄節(jié)點指針”的過程。

圖3 插入“窄節(jié)點指針”示例

3 混合索引機制

數(shù)據(jù)庫表只能逐行訪問，如果要快速訪問表格中記錄，需對表中記錄建立索引。對衛(wèi)星地面設(shè)備監(jiān)控中需存儲的實時數(shù)據(jù)的查詢形式非常固定：即從時刻ts起，到時刻te結(jié)束，時間間隔為tspan，采集點集合S{S1,S2,…,Sn}在所有時刻的值。因此本文用哈希表、B+樹［8］和Judy array數(shù)字樹來建立索引，索引關(guān)鍵字為設(shè)備采集點描述符與設(shè)備采時刻，索引值為相應(yīng)實時記錄的oid。

當(dāng)為某采集點的實時記錄建立索引時，首先根據(jù)采集點的設(shè)備描述符在哈希表中找到采集點的B+樹，然后以實時記錄的采集時刻作為關(guān)鍵字在B+樹中插入索引，如圖4所示。本文的B+樹葉子節(jié)點中有兩種索引：一種是立即索引，直接與記錄關(guān)聯(lián)；另一種是壓縮樹索引，指向一棵Judy array壓縮樹。壓縮樹記錄占若干頁面，隨索引插入，壓縮樹會頻繁地刪除或生成內(nèi)部節(jié)點，為此本文以位圖法管理壓縮樹內(nèi)部空間的分配和刪除。如對64KB大小的壓縮樹，可在頁面首地址處以1024B（1B代表8b）管理整個頁面空間。當(dāng)索引關(guān)鍵字是嚴(yán)格遞增順序時，采集點的樹建立索引過程描述如下。

圖4 混合索引示意圖

1）初始時B+樹的高度為1，隨著索引陸續(xù)插入節(jié)點，該節(jié)點將溢出。溢出時節(jié)點不像普通B+樹節(jié)點會分裂成兩個節(jié)點，而是在數(shù)據(jù)庫表中插入一新的Judy array數(shù)字壓縮樹記錄，將葉子節(jié)點的全部索引轉(zhuǎn)存進(jìn)壓縮樹中，并將該壓縮樹索引插入到B+樹葉子節(jié)點里。

數(shù)據(jù)庫索引范文第3篇

【關(guān)鍵詞】XML 1-index F&B索引

可擴展標(biāo)記語言XML（eXtensible Markup Language）是一門新興的面向Internet應(yīng)用的標(biāo)記語言，是為在WEB上使用而優(yōu)化的SGML子集。XML是一種簡單、與平臺無關(guān)并被廣泛采用的標(biāo)準(zhǔn)，是用來定義其它語言的一種元語言。XML具有強大的描述能力，又有適應(yīng)網(wǎng)絡(luò)應(yīng)用的簡潔性，作為對SGML語言標(biāo)準(zhǔn)的一種改良，XML具有適于異構(gòu)應(yīng)用間數(shù)據(jù)共享，可以進(jìn)行數(shù)據(jù)檢索和提供多語種支持等特點。

XML及其相關(guān)技術(shù)的研究不僅在數(shù)據(jù)庫理論領(lǐng)域占有一席之地且其水平已成為衡量一個國家信息化程度的重要標(biāo)準(zhǔn)之一。目前很多XML索引技術(shù)已被提出，具體可以分為：

（1）基于路徑的XML索引方法，如DataGuide、1-index、A （k） 索引、D（k）索引、F&B索引等。

（2）基于編碼的XML 索引方法，如Anc_Desc_B + 、XR + XRStack 算法等。本文主要介紹了1-index以及F&B索引。

1 1-INDEX

為了解決DataGuide 的上述兩個問題，1-index提出“bisimulation”和“simulation”的概念。1-index 索引中將“相似”的節(jié)點存放在一個擴展集中，這可能造成DataGuide 中所有擴展集的節(jié)點總數(shù)是XML 數(shù)據(jù)圖中節(jié)點總數(shù)的指數(shù)倍。兩節(jié)點“相似”概念使得1-index 具有如下兩個優(yōu)點：

（1）索引大小和XML數(shù)據(jù)圖大小成線性關(guān)系。

（2）索引的擴展集之間不相交，所有擴展集的節(jié)點總數(shù)和XML 數(shù)據(jù)圖中節(jié)點總數(shù)相等。

2 F&B索引

DataGuide 和1-index 保存XML 數(shù)據(jù)圖中所有邊的信息，可稱為“覆蓋索引”，因為它們可以直接通過索引進(jìn)行查詢而不必訪問原來的數(shù)據(jù)。在本文里我們稱child axis 為PC axis，descendant-or-self 為AD axis，我們稱沒有分支謂語的或AD axis為簡單路徑。DataGuide 和1-index只能進(jìn)行簡單路徑查詢，因此提出了the forward-and-backward index，簡稱F&B索引可以被視為分支路徑表達(dá)式查詢的“覆蓋索引”。在所有的XML索引中，F(xiàn)&B索引是可以回答條件約束的最小索引。F&B索引是已有的XML索引中最有效、最強大的一種，F(xiàn)&B索引技術(shù)在不斷的改進(jìn)。

基于路徑索引的XML 查詢方法只能夠解決單路徑查詢，但路徑索引的創(chuàng)建不受XML文檔結(jié)構(gòu)的約束，即XML 文檔可以是樹結(jié)構(gòu)，也可以是圖結(jié)構(gòu)。基于編碼方式下的XML 索引查詢方法能夠有效地解決分支路徑查詢，但是這種方法都對相應(yīng)的XML 文檔有要求，其所要查詢的XML文檔為樹形結(jié)構(gòu)。

DataGuide的提出解決了這一問題。但是DataGuide僅限于一個常規(guī)表達(dá)式的查詢，對于多個表達(dá)式的復(fù)雜查詢不起作用。針對已提出的索引結(jié)構(gòu)的不足，Tova Milo和Dan Suciu提出了模板索引。與以前的方法相比，T-INDEX有以下幾方面的改進(jìn)：

（1）使交換空間普遍化。

（2）“bisimulation”和“simulation”的提出使索引可以有效的建立。

（3）索引的大小有保證。

（4）與DataGuide相比它是一個完美的一般化的索引結(jié)構(gòu)。

1-index和2-index是模板索引的兩個特殊的索引，模板索引是1-index和2-index的概括和一般化。

對于每個在DB中的節(jié)點v，用Lv（DB）或Lv表示從根節(jié)點到節(jié)點v的路徑字符集合：Lv（DB）={w|w=a1…an}， ? a path v0 …{v， v0 是根節(jié)點}。在DB中的節(jié)點vu則vu?Lv=Lu，我們用[v]來表示v的等價集合。

這種方法效率低，有兩個原因：

（1）計算等價類需要花費大量的時間。

（2）等價類之間存在重疊，浪費空間。為了解決構(gòu)建開銷問題，提出改進(jìn)：v≈u?vu。1-index索引中提出了“bisimulation”和 “simulation”的概念。

DB是一個數(shù)據(jù)圖。節(jié)點間的一個二進(jìn)制關(guān)系 ～是一個backwards bisimulation滿足以下四點：（1）如果v～v’和v是根節(jié)點，那么v’也是根節(jié)點；（2）相反的，如果v～v’和v’是根節(jié)點，那么v也是根節(jié)點；（3）如果v～v’，那么對于任意邊uv存在一個邊u’v’，滿足u～u’；（4）相反的，如果v～v’，那么對于任意邊u’v’存在一個邊uv，滿足u～u’。

通過廣度遍歷函數(shù)Bfsl（）對樹進(jìn)行層次遍歷，然后通過merge（）函數(shù)對祖先節(jié)點相同的同層節(jié)點進(jìn)行合并將XML數(shù)據(jù)建立成1-index樹，然后再通過Dfsl（）函數(shù)對1-index樹進(jìn)行前序遍歷，對樹的每個節(jié)點存儲兩個數(shù)值id和level。id用來表示它被遍歷的次序，level用來表示它所在的樹的層數(shù)。

3 結(jié)論

本文研究了XML存儲與索引技術(shù)，主要研究了兩種索引：

（1）板索引中的1-index。

（2）于磁盤的F&B索引。

1-index提出 bisimulation和simulation，索引大小和XML數(shù)據(jù)圖大小成線性關(guān)系，索引的擴展集之間不相交，所有擴展集的節(jié)點總數(shù)和XML 數(shù)據(jù)圖中節(jié)點總數(shù)相等。但1-index只適合查找固定常規(guī)表達(dá)式，對于多分支的表達(dá)式則不能準(zhǔn)確地查找。F&B索引是目前XML索引中最強大的一種，它以最小的索引覆蓋所有分支。

參考文獻(xiàn)

[1]劉雨洋，李建中，王宏志等.于后裔聚集F&B索引的XML數(shù)據(jù)查詢處理算法[J].計算機科學(xué)，2006，33（11）：363-365.

[2]孔令波，唐世渭，楊冬青.XML數(shù)據(jù)的查詢技術(shù)[J].Journal of Software，2007， 6（18）：1400-1418.

[3]劉顯敏，李建中，王宏志等.SAJ：以最小化空間代價為目標(biāo)的F&B索引構(gòu)建算法[J].計算機研究與發(fā)展，2006（43）：413-417.

數(shù)據(jù)庫索引范文第4篇

關(guān)鍵詞：海洋環(huán)境；數(shù)據(jù)庫系統(tǒng)；Oracle；性能優(yōu)化

中圖分類號：TP311.13

對于傳統(tǒng)數(shù)據(jù)庫系統(tǒng)進(jìn)行優(yōu)化一般遵循“數(shù)據(jù)庫配置優(yōu)化”―>“數(shù)據(jù)庫應(yīng)用優(yōu)化”的順序原則。而船載海洋環(huán)境數(shù)據(jù)庫系統(tǒng)是單用戶、單任務(wù)系統(tǒng)，I/O操作并不是很頻繁，在系統(tǒng)結(jié)構(gòu)設(shè)計合理的情況下，對數(shù)據(jù)庫配置的優(yōu)化效果并不十分明顯，同時許多優(yōu)化專家認(rèn)為對應(yīng)用程序的優(yōu)化可以得到80%的系統(tǒng)性能的提升。因此，數(shù)據(jù)庫應(yīng)用優(yōu)化成為了船載海洋環(huán)境數(shù)據(jù)庫系統(tǒng)性能優(yōu)化的關(guān)鍵技術(shù)。

本文將以O(shè)racle優(yōu)化技術(shù)為基礎(chǔ)，針對特殊需求，對船載海洋環(huán)境數(shù)據(jù)庫系統(tǒng)進(jìn)行應(yīng)用程序優(yōu)化技術(shù)研究，提出性能優(yōu)化關(guān)鍵技術(shù)，實現(xiàn)數(shù)據(jù)庫系統(tǒng)性能優(yōu)化。

1 系統(tǒng)功能特點

2 性能優(yōu)化技術(shù)研究

通過功能分析，針對實際需求，研究的工作重點為基于應(yīng)用程序?qū)用娴腟QL語句優(yōu)化技術(shù)和索引技術(shù)。

2.1 SQL語句優(yōu)化技術(shù)

應(yīng)用程序?qū)?shù)據(jù)庫的操作最終表現(xiàn)為SQL語句對數(shù)據(jù)庫的操作[1]。對于船載海洋環(huán)境數(shù)據(jù)庫系統(tǒng)而言，SQL語句是對海洋環(huán)境數(shù)據(jù)庫進(jìn)行操作的惟一途徑，它消耗了70%～90%的數(shù)據(jù)庫資源，SQL語句的執(zhí)行效率直接關(guān)系著船載海洋環(huán)境數(shù)據(jù)庫數(shù)據(jù)查詢的速度與效率。

針對查詢操作，SQL語句優(yōu)化的方法有：

（1）盡量使用占位符代替變量；

（2）where子句限定條件的放置順序應(yīng)與索引字保持一致；

（3）選擇最有效率的表作為基礎(chǔ)表；

（4）避免采用MATCHES和LIKE通配符匹配查詢；

（5）避免或簡化排序；

（6）避免非開始的子串；

（7）避免相關(guān)子查詢；

（8）消除對大型表行數(shù)據(jù)的順序存?。?/p>

船載海洋環(huán)境數(shù)據(jù)庫系統(tǒng)應(yīng)用主要應(yīng)用體現(xiàn)為海量數(shù)據(jù)信息的嵌套查詢，該模式工作效率的致命影響因素主要歸結(jié)為對大型表行數(shù)據(jù)的順序存取。以查詢潮流表中2012年3月的平均潮高信息為例，如果采用順序存取策略，該查詢操作即為三層嵌套查詢操作，假設(shè)每層僅查詢300行，該查詢操作仍會產(chǎn)生遍歷3億行數(shù)據(jù)的龐大工作量。研究發(fā)現(xiàn)，為避免該情況發(fā)生，我們可以建立索引在連接的字段上。例如，對索引表（年、月、層、……、表名）和統(tǒng)計數(shù)據(jù)表（表名、經(jīng)度、平均值……）這兩個表進(jìn)行跨表連接查詢時，兩個表建立連接，應(yīng)建立索引在“表名”這個連接字段上。

此外還可以使用并集來避免順序存取。即時建立索引在全部查詢列，然而where子句會自動強迫優(yōu)化器忽略全部索引而進(jìn)行順序存取查詢。例如，下面的查詢將會強迫對orders表執(zhí)行順序操作：

（9）對于大數(shù)據(jù)量的求和避免使用單一的sum命令處理，可采用groupby方式與其結(jié)合；

（10）避免可能會引起磁盤讀寫的rowid操作。

（11）使用臨時表加速查詢。

此外，可以使用Oracle提供的SQLTrace工具和EXPLAINPLAN命令來進(jìn)一步調(diào)整SQL代碼。

SQLTrace提供解析、執(zhí)行和返回數(shù)據(jù)次數(shù)；執(zhí)行SQL語句所花CPU時間和執(zhí)行語句經(jīng)歷的時間；處理的記錄數(shù)和庫緩沖區(qū)錯誤次數(shù)等有用信息。

EXPLAINPLAN命令可顯示Oracle優(yōu)化器為SELECT、UPDATE、INSERT和DELETE語句選擇的執(zhí)行計劃[2]。

2.2 索引優(yōu)化技術(shù)

索引的主要作用是提高索引數(shù)據(jù)的效率。合理地使用索引、優(yōu)化數(shù)據(jù)檢索是提高數(shù)據(jù)處理速度的一個重要方面。

Oracle中常用的索引類型是B-Tree索引。

2.2.1 B-Tree索引

B-Tree索引是按B數(shù)結(jié)構(gòu)組織并存放索引數(shù)據(jù)的。該索引結(jié)構(gòu)是一棵平衡二叉樹。以海洋環(huán)境數(shù)據(jù)庫中海面氣溫要素客觀分析數(shù)據(jù)為例，其B-Tree結(jié)構(gòu)示意圖如圖2所示。最頂層的索引塊為根，包含指向分支節(jié)點的信息；中間為分支節(jié)點，包含指向下級分支部分和指向葉子節(jié)點的信息；最底層索引塊為葉子節(jié)點，包含索引列和指向表中每個匹配行的ROWID信息。葉子節(jié)點是一個雙向鏈表，因此可以對它們進(jìn)行任何方面的范圍掃描。

2.2.2 使用索引時應(yīng)注意的問題

盡管在一個表上建立索引可能會加快查詢的速度，但是也必須注意到它的代價：

（1）索引會降低DML操作的速度[5]，因為每一條DML語句只要涉及到索引關(guān)鍵字，Oracle系統(tǒng)就得調(diào)整索引，這意味著每當(dāng)有記錄在表中增減或索引列被修改時，索引本身也會被修改并改變存儲次序，從而多占用CPU和磁盤I/O等系統(tǒng)資源。

（2）索引作為一個獨立的對象需要消耗磁盤空間，如果表很大的話，其索引消耗磁盤空間量也會很大。

因此，使用索引時一定要認(rèn)真分析數(shù)據(jù)的構(gòu)成、經(jīng)常使用的查詢數(shù)據(jù)列和條件列，仔細(xì)選擇索引列和列的組合，切忌對數(shù)據(jù)量需要頻繁更新的列建立索引[6]。同時，還要根據(jù)數(shù)據(jù)產(chǎn)生和使用的不同階段，適時打開或關(guān)閉某些索引，以優(yōu)化數(shù)據(jù)查詢和處理。

通過以上對比，說明優(yōu)化原則是有效的，應(yīng)用優(yōu)化原則可以使查詢速度加快。通過大量實驗證明當(dāng)測試數(shù)據(jù)的數(shù)量及數(shù)據(jù)表的項數(shù)足夠多時，查詢速度提高的幅度極其明顯，對于一個六百萬左右的數(shù)據(jù)查詢顯示優(yōu)化前需要60s，優(yōu)化后只需要12s左右。

3.2 索引優(yōu)化測試

索引的訪問分為索引唯一掃描和索引掃描范圍兩種模式。船載海洋環(huán)境數(shù)據(jù)庫系統(tǒng)主要應(yīng)用的是索引唯一掃描模式。在SQL語句中，優(yōu)化器常通過where子句訪問索引。

以海洋環(huán)境數(shù)據(jù)庫中潮流要素為例進(jìn)行優(yōu)化實驗。

在這里定義了一個二級索引機制，先從索引表中通過組合索引查詢到相應(yīng)的數(shù)據(jù)表名，然后將該數(shù)據(jù)表名以變量形式嵌入查詢語句中，并與num列唯一索引組合作為二次索引，這樣大大加快了數(shù)據(jù)查詢的效率。

同時，由于該SQL語句是用在海洋環(huán)境查詢顯示界面，進(jìn)行以上處理后，可以加快數(shù)據(jù)顯示的速度。

4 結(jié)論

本文通過分析船載海洋環(huán)境數(shù)據(jù)庫系統(tǒng)功能特點，針對其需求特點，提出了性能優(yōu)化關(guān)鍵技術(shù)SQL語句優(yōu)化技術(shù)和索引技術(shù)。使用這些關(guān)鍵技術(shù)成功地進(jìn)行了海洋環(huán)境數(shù)據(jù)庫系統(tǒng)性能的調(diào)整和程序的優(yōu)化，從而有效地提高了數(shù)據(jù)查詢顯示的速度，更好地保障了海洋環(huán)境數(shù)據(jù)的安全性和可靠性，為船舶的海上航行提供了必要的決策支持，具有一定的實際應(yīng)用價值。

參考文獻(xiàn)：

[1]袁愛梅.Oracle數(shù)據(jù)庫性能優(yōu)化研究[D].華東師范大學(xué)，2007.

[2]高艷春，周兆確，唐艷軍.Oracle性能調(diào)整與優(yōu)化[M].北京：人民郵電出版社，2002.

[3]路川，胡欣杰.Oracle10g寶典[M].北京：電子工業(yè)出版社，2008.

[4]毛選，魏海萍，孫思云.OCP：Oracle9i性能調(diào)整學(xué)習(xí)指南[M].北京：電子工業(yè)出版社，2003.

[5]何致億.Oracle9i實務(wù)管理講座――系統(tǒng)核心篇[M].北京：電子工業(yè)出版社，2003.

[6]Oracle.Oracle9iDBAFundamentalsIIVolume1StudentGuide[M].2002.

[7]高峰.基于Linux的船載海洋環(huán)境數(shù)據(jù)庫系統(tǒng)設(shè)計與實現(xiàn)[D].哈爾濱工程大學(xué)，2008.

[8]肖軍.ORACLE數(shù)據(jù)庫性能調(diào)整與優(yōu)化[D].武漢大學(xué)，2004.

[9]李捷.短信系統(tǒng)中的Oracle數(shù)據(jù)庫性能優(yōu)化及實施[D].重慶大學(xué)，2007.

數(shù)據(jù)庫索引范文第5篇

[關(guān)鍵詞]B樹；索引；數(shù)據(jù)庫管理軟件

中圖分類號：TQ1 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-914X（2014）23-0252-02

1 引言

索引是一個單獨的、物理的數(shù)據(jù)庫結(jié)構(gòu)，它是某個表中一列或若干列值的集合和相應(yīng)的指向表中物理標(biāo)識這些值的數(shù)據(jù)頁的邏輯指針清單。表的存儲由兩部分組成，一部分用來存放數(shù)據(jù)頁面，另一部分存放索引頁面。通常，索引頁面相對于數(shù)據(jù)頁面來說小得多。數(shù)據(jù)檢索花費的大部分開銷是磁盤讀寫，沒有索引就需要從磁盤上讀表的每一個數(shù)據(jù)頁，如果有索引，則只需查找索引頁面就可以了。所以建立合理的索引，就能加速數(shù)據(jù)的檢索過程。

數(shù)據(jù)庫索引就是加快檢索表中數(shù)據(jù)的方法。數(shù)據(jù)庫的索引類似于書籍的索引。在書籍中，索引允許用戶不必翻閱完整個書就能迅速地找到所需要的信息。在數(shù)據(jù)庫中，索引也允許數(shù)據(jù)庫程序迅速地找到表中的數(shù)據(jù)，而不必掃描整個數(shù)據(jù)庫。

2 B樹的定義

2.1 B樹的結(jié)構(gòu)

本文刪除記錄時引起的結(jié)點內(nèi)部數(shù)據(jù)變化，甚至整個結(jié)點內(nèi)的記錄都無效時，會調(diào)用刷新函數(shù)。該函數(shù)以樹的根為參數(shù)，在遍歷樹時調(diào)用結(jié)點類的寫入函數(shù)將新數(shù)據(jù)覆蓋到數(shù)據(jù)庫文件的原地址上。而有些被刪除了的結(jié)點，在內(nèi)存中的B樹已經(jīng)無法聯(lián)系到，所以無法寫入覆蓋，也無需操作。所以實際上本系統(tǒng)的刪除操作不會減少數(shù)據(jù)庫文件的大小。

4 總結(jié)

本文描述了設(shè)計和實現(xiàn)了一種基于B樹的小型數(shù)據(jù)庫管理系統(tǒng)的過程。詳細(xì)敘述了B樹在本系統(tǒng)中的實現(xiàn)和應(yīng)用，以及本系統(tǒng)如何構(gòu)造了如常見數(shù)據(jù)庫的表與字段，以及各個操作的流程。對B樹性能進(jìn)行分析計算。最終實驗表明，B樹非常適合作為存取輔助設(shè)備的數(shù)據(jù)結(jié)構(gòu)。

參考文獻(xiàn)

[1] Thomas H.Cormen， Charles E.Leiserson等著，潘金貴等譯.算法導(dǎo)論（第2版） [M].北京：機械工業(yè)出版社，2006.9.