數據庫索引
前言：想要寫出一篇令人眼前一亮的文章嗎？我們特意為您整理了5篇數據庫索引范文，相信會為您的寫作帶來幫助，發現更多的寫作思路和靈感。
數據庫索引范文第1篇
中圖分類號:TP311文獻標識碼: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
因為出現許多需要有效對移動對象管理的應用,STDB受到很多關注。這些應用需要在不同的時間戳記錄對象的地理位置(有時也記錄對象的形狀),而且支持對它們歷史的和將來預期的特征進行查詢。
STDB的目的是根據數據的時間屬性作歷史性和預言性的檢索。具體地說,給定對象集合o1, o2,… , oN(N是基數),對于每個對象oi(1≤i≤N),歷史性STDB會存儲oi在歷史的所有時間戳t的有效范圍oi.E(t)。根據空間數據庫的原理,oi.E(t)能夠表示為一個描述對象在時刻t的真實形狀。尤其是,如果其形狀不是重要屬性,oi.E(t)則以一個點代替以表示oi在時刻t的位置。實際上,在連續時間戳,同一對象的有效范圍可以用不同的方法壓縮(例如:如果對象在幾個連續時間戳保持靜止,則它的有效范圍在該時間內只需存儲一次)。
另一方面,對每個對象oi,預期性STDB會存儲它的最新更新的位置oi.L(tupd)(tupd:對象最新更新的時間)和用于描述它當前移動特性時間函數。最適合的時間函數是線性函數,因為1)線性函數能夠近似描述任何運動軌跡,2)線性函數要求的參數個數最少。具體來說,除了oi.L(tupd),系統只需記錄對象的速度oi.vel,就可以計算出在將來任何時刻t>tupd對象的位置:
oi.L(t) = oi.L(tupd)+oi.vel(t-tupd)
用這種模型只需在對象的時間函數的參數(如:速度)發生變化時采取更新數據庫。
人們已經對作為支持時空查詢的輔助結構的時空索引方法做了很多研究。時空存取方法主要集中在兩個正交方向:1)對對象過去位置的索引,2)對現在的位置和將來預期位置的索引。
1 移動對象歷史數據的時空索引
考慮到移動對象連續不斷發送它們的位置,保持所有的更新幾乎是不可能的。有兩種方法可用來減少歷史數據:1)采樣,對數據流在某一時刻進行采樣。可以采用線性插值計算出相鄰采樣點間的線性軌跡。2)僅在變化時更新,移動對象僅當它們的數據屬性(速度或方向)發生變化時才發送數據。我們把對歷史數據的時空索引機制分為三類。
第一類是在現存的空間索引方法加入時間屬性。這類時空索引方法主要是處理空間維,時間維是第二要素。
RT-tree[1]結合了作為空間存取方法的R樹和作為時間存取方法的TSB樹。在RT樹中,時間和空間信息是分開維護的。不管是葉結點還是非葉結點,每個索引項都包含(S,T, P) 形式。S是空間信息,T是時態信息(時間間隔), P是指向子樹或對象的指針。隨著時間變化,如果對象空間位置不變,則它的空間信息S不變,僅對時態信息進行更新。如果對象空間位置發生變化,則需要創建一個新的索引項插入RT樹。這種方法有許多局限性,一方面,如果變化對象的數量很大,許多索引項被創建,RT樹會迅速膨脹;另一方面,當結點溢出時,怎樣分裂結點還沒有很好的解決辦法。
3D R-tree[2]把時間看作除了空間維以外的另一維。主要思想是為了避開時間和空間查詢之間的區別。3D R-tree可以直接利用現有的R樹算法來處理空間及時態查詢而無需修改,其前提是必須知道移動對象歷史軌跡存在的有效時間范圍,如果移動對象軌跡結束時刻不確定,那么3D R-tree將無法有效工作。比如若移動對象運動軌跡從某個歷史時刻開始一直延伸到當前時刻,顯然包圍移動對象軌跡的3D MBR將會非常巨大且造成空間區域的大量重疊,直接導致3D R-tree的查詢搜索性能下降。因此,在應用中要求移動對象軌跡是封閉的(closed),即移動對象歷史軌跡必須在某個過去時刻終止而不能延伸到當前時刻。由于3D R-tree將時間維與空間維等同索引,時間片查詢則必須掃描整個3D R-tree而非在此時間片下的有效子樹, 因此性能非常低下。
第二類是同時把空間和時間加入某一結構中,但它們是各自獨立的。這是為了使在某一時刻所有有效的空間數據同時在一個索引結構(R-tree)中。最高目標使為每一時間項都建立一個單獨的R-tree。這種方法需要很大的存儲量。
MR-tree[3]采用了在R-tree的背景下可重疊B-tree的思想。主要思想是避免每個時間戳都有單獨的R-tree而引起的存儲量過大。通過在連續的R-tree中不存儲相同的對象實現減少存儲量。作為替代,以不同根結點的鏈接指向同一結點,而所有的結點項都保存著它們在不同時間戳的值。這種思想對時間片查詢來說是完美的。搜索被指向適合的根結點,然后利用R-tree進行空間搜索。然而,它對時間窗口查詢的執行是無效的。而且,一個主要的缺陷是存在許多重復項。考慮到這樣的情況,在連續兩個時間戳僅有一個結點項發生變化,而在這連續兩個R-tree的所有其它結點也必須重新復制。
HR-tree與[4]MR-tree非常相似。HR-tree是一種采用重疊技術、將單一版本的結構轉換為部分固定結構的高效時空索引結構。該結構為兩級索引機制,分別對時空對象的時間信息和空間信息進行索引:1)HR-tree是對事務時間進行索引,它按時間遞增順序將時空對象的時間信息組織為有序表,并將時空對象不發生空間變化的那個時間片作為時空對象的時間信息值;2)用R-tree索引結構為每個時間片的空間對象建立索引,并將R-tree的存儲信息(根結點存儲地址)保存到對應時間片的時間索引結點中。為了節省空間,相鄰時間片的R-tree可能會重疊,即若相鄰時間片的R-tree有共同的分枝,則只保存該分枝的一個版本。
第三類是主要考慮時間維索引,其次考慮空間維。第三類方法主要集中在面向軌跡的查詢。在此類中處理空間查詢處于次要位置。
Trajectory-bundle(TB-tree)[5]是完全保持軌跡的類似R-tree結構。一個葉子結點僅能包含屬于同一軌跡的線段。存在一個缺陷:在空間上比較靠近的不同軌跡的線段將被存儲在不同的結點上。構建TB-tree是從左到右的原則。也就是說。最左邊的結點是最先插入的結點,最右邊的結點是最后插入的結點。
Scalable and Efficient Trajectory Index(SETI)[6]將空間區域分割成靜態且不重疊的分區,在每個分區下對移動對象的軌跡線段利用R樹進行索引。其考慮是,相對于無限連續變化的時間維而言,移動對象軌跡受空間范圍所限,那么可以把受限的空間區域利用某種規則靜態劃分以分而治之。良好的劃分函數應盡量把同一移動對象不同軌跡線段聚類在同一個分區中。若一條軌跡線段穿過多個分區,那么必須將此線段裁剪并分別存儲在不同分區R樹中,這樣會導致查詢結果的重復,在查詢處理后必須進行重復結果的剔出。相應地,時態查詢則被轉換為對折線段集合的空間窗口查詢,利用幾何計算方法可以得到空間窗口內的折線段集合,其對應的移動對象集合即是時態查詢結果。
2 移動對象當前位置軌跡索引
在現實應用中許多要求能夠有效地對移動對象當前位置進行管理和查詢。相對來說,檢索移動對象當前位置更具有挑戰性,其關鍵在于如何提高傳統空間索引的頻繁更新動態性能以滿足動態環境下的應用要求。標準R樹更新算法采用刪除-重插機制來實現移動對象位置更新,頻繁更新會導致R樹性能急劇下降。為了支持R樹的頻繁更新操作,近年來提出的方法包括LUR樹(Lazy Update R-tree)、自底向上更新策略(Bottomup Update)、哈希方法(Hash)等。LUR[7]提出了一種延遲更新(Lazy Update)策略,即若移動對象位置未超出當前節點MBR,算法僅僅更新移動對象所在的數據頁面并維持索引頁面不變;對于移出MBR之外的移動對象,根據其超出MBR程度大小,判斷是否將MBR進行有限擴展以包含移動對象新位置;或者利用標準R樹更新算法進行更新以盡量減少位置更新所帶來的索引樹更新操作。Bottom-up Updates的自底向上法擴展了LUR-tree思想。自底向上法比較適合處理移動對象的連續更新。例如:擴展MBR以包含新的值和移動當前對象到兄弟結點。
Song 等人利用空間劃分的思想來索引移動對象當前位置,首先靜態地把空間劃分為可以相互重疊的區域,然后根據當前位置將移動對象哈希映射到不同區域中去。只有當移動對象位置超出了當前區域才會更新此對象的索引記錄,數據庫中保存了移動對象位置近似視圖。
3 當前和將來軌跡查詢索引
在移動計算、位置服務等新興應用中,需要對移動對象當前及未來位置預測以提供相關服務,針對移動對象當前和未來軌跡的索引方法是目前研究的熱點。為了能夠預測移動對象未來軌跡,需要存儲一些額外的信息(如移動對象當前速度和目的地等)。然后根據移動對象當前的運動特性對未來軌跡進行預測,目前通常使用線性方程來描述移動對象的運動特性。在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索引結構,最大的特點是使用了軌跡共享技術來最大限度地減少數據的存儲數量,提高索引的更新效率。在這種樹中的葉子節點結構表示為(oid,軌跡的數量,起始坐標,結束坐標,起始時間,結束時間,其他信息)。對于在同一時間內的節點而言,如果它們的坐標位置相同或者接近,那么就可以采取共享策略把若干個節點的內容放入一個公共的節點內,這樣就可以明顯地減少存儲的空間。
使用PMR-quadtree[9]作為索引將來軌跡的基本空間存取方法,關鍵的一點是當移動對象發生更新時,整個索引結構被破壞,然后根據新的信息重建索引結構。為了避免過多的更新操作,索引每ΔT時間單元重建。在理論上,無限的時間維可以分割為大小為ΔT的相等的時間片。對于每一時間片,會構建一個新的基于運動方程的PMR-tree。然而,由于存儲設備的有限性,只有當前的PMR-tree會被存儲。
TPR-tree[10]使用時間參數化包圍框來包含移動對象,其索引結構與R樹類似。但TPR-tree采用謹慎的BR策略,在某些時刻(如構建時刻)包圍框是最小的,但在其后的時間內往往不是。從一維角度考慮,MBR最(大)小邊界速度為其范圍內所有點的最(大)小速度,從而保證所有點始終包含在同一個MBR中。TPR-tree索引節點記錄不僅存儲了移動對象(子樹)MBR,而且包含了移動對象(子樹)MBR速度矢量。由于節點MBR呈現出一種隨時間變化的動態性,隨著時間延伸包圍框會越來越大,導致空間區域的大量重疊從而使得性能下降。因此,必須在適當時候對TPR-tree進行重構以提高查詢性能。
TPR*-tree[11]修改了TPR-tree的動態操作算法。通過維護一個代價下降優先隊列保證插入路徑選擇的全局最優,保持TPR-tree MBR的緊致性以提高查詢性能。對于上溢節點的分裂算法,TPR*-tree只是在必要的時候才對節點分裂并重插。以二維空間移動對象為例,節點首先在所有可能的8個方向(4×d)上進行排序,并從中選擇一種最好的分裂方式,實際上此時節點并不分裂,而是把節點中30 %的記錄刪除后重插。如果在重插過程中發生上溢,那么就直接進行節點分裂以避免傳遞操作。TPR*-tree是目前最好的參數化空間訪問方法。
4 結束語
該文總結了移動對象軌跡索引的各種技術,并對它們進行了比較詳細的分類,對每種方法均找出了多個比較典型的模型進行介紹。近年來對移動對象歷史軌跡、當前位置與未來趨勢預測的索引方法研究較多,在如何同時解決上述三種查詢的索引方法上研究仍然欠缺。多種索引結構的結合是時空數據庫系統實際設計的主要趨勢,選擇哪幾種索引結構以及如何把它們有機地結合起來將是系統設計所面臨的主要難題。
參考文獻:
[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.
數據庫索引范文第2篇
作者簡介:劉波（1983-）,男，河南信陽人，博士研究生，主要研究方向：分布式實時數據庫、衛星遙感信息處理； 范士明（1945-）,男,上海人，研究員,碩士,主要研究方向：衛星遙感信息處理； 劉華（1969-）,男,重慶人，高級工程師,碩士,主要研究方向：衛星遙感信息處理。
文章編號:1001-9081（2011）08-02265-05doi:10.3724/SP.J.1087.2011.02265
（中國航天科技集團公司第五研究院 五零三研究所，北京100086）
（.cn）
摘 要:在衛星地面設備監控中，需要將大量實時數據實時地存進數據庫并提供實時查詢。針對實時數據和Judy array數字樹的特點，提出了一種基于內存映射文件的位圖分配法，然后設計了一種哈希表、B+樹和Judy array混合索引機制。通過大量記錄的插入和查詢，結果表明位圖分配法能避免大量不可利用的內存碎片的產生，結合內存位圖分配法的混合索引機制也為應用程序提供了實時的索引插入和查詢。
關鍵詞:實時數據庫；位圖分配法；內存映射文件；哈希表；B+樹;Judy array
中圖分類號: TP311.131文獻標志碼: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 引言
衛星地面設備監控系統需要對大量數據信息進行采集、傳輸、綜合分析、計算等處理。從監控系統組成可以看出，數據是聯系各功能模塊的紐帶。隨著衛星地面應用系統的發展，地面設備監控系統的功能需求也不斷增多、增強，數據量也不斷擴大，數據之間的關系也越來越復雜。因此需要將數據庫技術引入衛星地面設備監控，用數據庫技術來管理、處理監控過程中的數據。但衛星地面設備監控中數據的一個顯著特點是具有時間特性，且有效時間是短暫的，過時則失效。而以關系數據庫為代表的傳統數據庫的設計目標是維護數據的正確性、保證系統的低代價和提供友好的用戶接口。這種數據庫系統對傳統的商務和事務型應用是有效、成功的，但對于新領域的實時數據和實時事務的應用要求難以勝任。所以，需要結合數據庫技術和實時技術，研究具有顯式定時限制的實時數據庫系統［1］。
鍵值（key-value）型索引性能的好壞直接影響實時數據庫的穩定性、可靠性、實時性。在衛星地面設備監控中，實時數據庫將面臨超大量的實時數據，最新的實時數據必須能在一定時間內存入數據庫，相對陳舊的歷史數據在給定key時必須能在一定時間內檢索到相應的值。傳統的鍵值型索引并沒考慮到這種超大量實時數據的特點，導致其在內存空間的利用效率、索引插入和查詢的實時性上很難達到要求。對此本文根據地面設備監控中實時數據的特點以及檢索要求，采用內存映射文件技術處理數據文件的讀取，提高了數據文件的I/O讀寫速度；利用位圖分配法代替操作系統的內存分配，可以避免大量內存碎片，提高數據庫文件存儲空間的利用率；采用混合索引取代數據庫中常用的哈希表、B+樹、T樹索引機制，實現了索引壓縮和有序存儲，并保證記錄的實時插入和查詢。
1 基于內存映射文件的位圖分配法
1.1 內存文件映射機制
內存映射文件允許在進程的虛擬地址空間中保留一段內存區域，并將物理存儲器中的目標文件提交給該區域，映射到這段虛擬內存之中。這樣，物理存儲器來自一個已經位于磁盤上的存儲近期實時歷史數據的文件，而不是系統的頁文件。一旦該文件被映射，就可以用存取內存數據的方式直接操作文件中的數據，就像整個文件已經被加載到內存中一樣。因此使用內存映射文件處理存儲在磁盤上的文件時，將不必再對文件執行I/O操作，這意味著對文件進行處理時將不必再為文件申請并分配緩存，所有的文件緩存操作均由系統直接管理，由于取消了將文件數據加載到內存、數據從內存到文件的回寫以及釋放內存塊等步驟，使得內存映射在處理實時數據庫這種有著大數據量的文件時有顯著的優勢。
實時數據庫必須作為多個進程共享數據的倉庫。內存映射文件正是計算機操作系統提供的解決多個進程間共享數據的最有效方法。數據共享通過讓多個進程映射同一文件內核對象的視圖來實現的，這意味著進程間將共享物理存儲器中的同一個數據庫文件。因此，當一個進程將數據寫入一個共享文件映射對象的視圖時，其他進程可以立即看到它們視圖中的數據變更情況。同時，內存映射文件將作為數據庫持久存儲的手段。當事務提交時，如果內存中相應于磁盤文件的頁面發生了改變，調用操作系統的內外存交換機制，將事務對數據庫的更新操作保存在磁盤上。此時持久化到磁盤上的文件將作為數據庫的后端備份，一旦應用程序出錯或掉電導致內存數據丟失時，磁盤文件將被重新映射，使數據庫能盡可能快地從故障中恢復過來。
1.2 位圖分配法
實時數據庫系統中，內存分配要求實時高效。本文借助位圖［2-3］實現內存分配，根據系統配置大小設定共需多少個位圖頁面，每個位圖頁面為4KB，因此共有32K比特位，每個比特位可分配8B（也可以不是8B，可根據系統配置要求而定）。如果該位為0，表示該比特位代表的相應位置的8B尚未分配，否則相應位置的8B已分配出去，因此一個位圖頁面可分配的空間為256KB。文件頭包含數據庫文件的描述信息，頁面地址分別指向各自的位圖頁面首地址，n個位圖頁面連續集中在一起，可減少因位圖頁面過于分散而導致的內存碎片較多的問題。每個位圖頁面負責其分配的區域，如位圖頁面0負責分配第一個256KB，位圖頁面1負責分配第2個256KB。
1）位圖頁面內尋找可分配空間過程。
如下代碼所示，其中pos以字節為單位,i表示正搜尋的位圖頁面編號（從0開始）；offs指當前位圖頁面搜尋的起始點，以字節為單位，其范圍是（0,…,4K-1）；mask為offs位置上的值，單字節長度；holeBitSize指目前搜尋到的連續的比特0數目；size指請求分配的字節數，objBitSize指分配size所需比特數；PageSize是頁面大小，4KB；firstHoleSize［mask］指mask中從最低位往最高位數起的第一個連續比特0個數；maxHoleSize［mask］表示mask中最多的連續比特0個數，代表可分配的最大空間；maxHoleOffset［mask］為最多的連續比特0個數區域在mask中的位置；lastHoleSize［mask］表示從最高位往最低位數起的連續的比特0個數；mask的值為（0,…,255），它們有各自的firstHoleSize、lastHoleSize、maxHoleSize、maxHoleOffset。
if（holeBitSize+firstHoleSize［mask］）≥objBitSize{
pos8×（（i×PageSize+offs）*8-holeBitSize）;
如果從pos開始size大小的區域尚未保留,保留這片區域,將位圖頁面中pos開始size大小的相應位全置1,然后撤銷保留區域，內存分配成功,返回pos；否則,offs增加（objBitSize+7）/8,holeBitSize置0,繼續搜索可分配空間
}else if（maxHoleSize［mask］≥objBitSize）{
pos8×（（i×PageSize+offs）×8-maxHoleOffset［mask］）;
如果從pos開始size大小的區域尚未保留,保留這片區域,將位圖頁面中pos開始size大小的相應位全置1,然后撤銷保留區域，內存分配成功,返回pos；否則,offs增加（objBitSize+7）/8,holeBitSize置0,繼續搜索可分配空間
}else if（上述兩條件都沒有滿足）{
如果lastHoleSize［mask］等于8,將holeBitSize加8；否則將holeBitSize設置為lastHoleSize［mask］
offs加1;
}
如果offs≥PageSize,這時搜尋到下個位圖頁面,置offs為0,i加1
2）擴展位圖頁面過程。
當搜尋全部位圖頁面后，還沒能找到指定大小的空間，則需要增加新的位圖頁面，此時等于擴展可分配的內存空間。extension為新擴展的內存空間大小，morePages為重新開辟的位圖頁面數目，n是未擴展前系統中已有的位圖頁面個數。擴展內存空間通過增加新的位圖頁面完成，為減少內存碎片，也為了確保未擴展前已搜尋到的holeBitSize個比特0位同新擴展空間中的objBitSize個比特0位連續，在新位圖頁面前添加若干內存頁面（如果holeBitSize為0，不必附加這片空間）。附加的內存頁面個數skip（objBitSize×8）/PageSize。當擴展完成后，找到足夠空間，返回剛分配空間的起始地址pos（以字節為單位）。當holeBitSize不為0,因找不到足夠大小的空間而引起的內存擴展過程描述如下所示：
1）令morePages為滿足morePages×PageSize×64≥extension+morePages×PageSize的最小整數,將objBitSize減去holeBitSize;
2）令skip為滿足skip×PageSize≥objBitSize×8的最小整數,置pos為n×PageSize×64+skip×PageSize;
3）將數據庫表文件中范圍為［0,pos+morePages×PageSize］的部分重新文件映射;
4）置pos位置后從第1到第objBitSize個比特位為1,置從第PageSize×skip/8個比特位開始的morePages×PageSize/8個比特位為1；
5）將每個位圖頁面的首地址賦給相應的位圖頁面,令pos為（n×PageSize×8-holeBitSize）×8,并將［pos,pos+holeBitSize×8］這段區域在位圖頁面中的相應比特位置1。
2 Judy array數字樹
通常情況下,數字樹［4］根據索引的范圍劃分為層次樹，當插入或刪除索引時，不需要對樹進行平衡操作；對索引的查找、插入、刪除等操作的執行時間依賴于索引本身，而不依賴于整棵樹的節點個數。數字樹的每個節點都是一數組，不同層的數組存儲索引的不同連續N位信息。數字樹的缺點在于當數字樹的分支較多時，空指針的相對比例較高，樹的內存利用率較低；另一方面，當樹的分支較少時，雖然空指針的相對比例降低，樹的內存利用率高，但當操作某個索引時，分支較少的數字樹需更多的指針來定位value，這將導致不能充分利用程序的局部性原理，使得CPU高速緩存（cache）的命中率降低［5］，大大減緩了指令執行速度。
Judy array［6-7］采用一種壓縮256階數字樹（即數字樹的每層存儲的是索引的一字節），根據節點內部存儲的索引個數自動調整節點內部結構和樹本身結構，達到壓縮節點節省內存的目的。節點的自適應壓縮通過如下方式：1）當前范圍索引數較少時，節點壓縮為線性節點或位圖型節點。2）“窄節點指針”指向的葉子節點或分支節點能跨越多層，即節點中索引的公共字節部分可以存放在“窄節點指針”里。3）借助“立即指針”，將索引直接存儲在分支節點里;同時所有調整是自適應的，不需要輔助參數對其進行性能上的優化調整。
2.1 分支節點、葉子節點
Judy array數字樹有如下5種節點。其中線性葉子節點可存儲多字節（指索引中未解碼的字節個數）索引，位圖葉子節點只能存儲1字節索引。線性葉子節點溢出時會轉換成位圖葉子節點，這種轉換僅發生在索引中剩余的未解碼部分還剩一字節時。位圖被均勻劃分成8部分，每部分由32個比特位構成，其中如果有任一比特位為1，則有一指針指向存儲了索引相應信息的數組，否則該指針為空。因此必須依據位圖的比特位信息獲得索引在數組中的偏移。
1）線性分支節點。第1個字節存儲當前數組中存儲的有效索引的數目，后面7字節存儲包含索引的子范圍的編號（0到255之間），接下來的56字節存儲至多7個“節點指針”，用于指向樹的下層葉子節點或分支節點。
2）位圖分支節點。首先存儲256個比特位，用比特位0或1表明相應的子范圍是否包含有效索引，如果沒有用0表示，反之用1表示。接下來是8指針，分別指向至多存儲了32個“節點指針”的數組，依據數組元素多少，數組大小分別為2,4,6,8,12,16,24,32,48,64個word。
3）未壓縮分支節點。包含了256個“節點指針”的數組，“節點指針”指向下層的葉子節點或分支節點，該分支節點占用2048B空間。
4）線性葉子節點。當前葉子節點包含的索引個數及索引字節數（1到3字節）存儲在指向葉子節點的“節點指針”里，首先存儲若干索引，然后存儲每個索引對應的值域，值域中存放指向值的指針（對于大于4字節的值）或是值本身（小于等于4字節的值）。
5）位圖葉子節點。只有當節點中未解碼字節數剩1時，線性葉子節點才會轉化為位圖葉子節點。類似位圖分支節點，指針為普通指針，每個指針指向存儲了值域的數組，該數組類似位圖分支節點中的數組，不同的是它存儲索引相應的值。
2.2 “節點指針”
“節點指針”指向樹的分支節點或葉子節點，占2word。“節點指針”中的1word是普通指針，用于指向下層節點，D域（存儲索引集合中公共字節）和P域（存儲的索引個數）共占3字節，T域（“節點指針”類型）占1字節，它們共同占用1word。“節點指針”總駐留在分支節點里，所以索引的首字節已經確定，其尾字節在葉子節點中也可確定，因此分支節點所指索引集合的公共字節個數至多為2（針對32位平臺，64位平臺為6）。D域和P域的界限是浮動的，當“節點指針”所指節點層次低時，P域字節少，D域字節多；當節點層次高時，P域字節多，D域字節少，32位平臺上3字節足夠存儲D域和P域。
“窄節點指針”指的是跨越了多個層次的“節點指針”，其D域中存放了索引集合的公共字節。“節點指針”可不指向葉子節點或分支節點，能直接將索引存放在“節點指針”里，這種存放了索引的“節點指針”稱為“立即節點指針”。“立即節點指針”只能存儲非常少量索引，32位平臺上“立即節點指針”只能存儲一個3字節的索引。當插入索引引起“立即節點指針”溢出時，它轉換成一指向葉子節點的“節點指針”，這時葉子節點存放的是原先存儲在“立即節點指針”里的索引和新插入的索引。
2.3 插入索引過程
下面描述了當插入索引時Judy array的節點變化過程，刪除索引等同于插入索引的逆過程。
1）空的根指針指向沒有存儲任何索引的數字樹。
2）插入第1到31個索引時，根指針指向單個樹根葉子節點（樹根葉子節點與線性和位圖葉子節點不同，但結構類似于線性葉子節點）。依據索引個數不同，樹根葉子節點分別需占用2,4,6,8,12,16,24,32,48,64個word空間。
3）當樹根葉子節點溢出時，即插入索引個數大于等于32時，葉子節點轉化為分支節點，分支節點存儲若干“節點指針”，“節點指針”指向下層分支節點或葉子節點或直接存儲索引。
4）當“立即節點指針”溢出時，它轉換為普通“節點指針”，指向線性葉子節點。當進一步插入更多索引時，它可能會轉換為一指向位圖葉子節點的“節點指針”（只有當線性葉子節點存儲的是1字節索引時才可能轉換為位圖葉子節點）。
5）當插入索引導致葉子節點溢出時，算法檢查是否可將葉子節點中的索引和新插入的索引壓縮存儲在當前葉子節點，因為索引字節數減少，葉子節點可容納更多索引。這時其“父節點指針”將轉換為“窄節點指針”或者當“父節點指針”原先就是“窄節點指針”時將轉換為“更窄”的“節點指針”，圖1展示了32位平臺上數字樹的某一“節點指針”轉為“窄節點指針”的過程。
圖1 “節點指針”轉化為“窄節點指針”示例
6）隨著索引的更多插入，導致存儲2～4字節（針對32位平臺）索引的線性葉子節點溢出時，如果它不能降低自身層次而成為“窄節點指針”所指的線性葉子節點，那么會生成一新的分支節點，將新節點插在父“節點指針”和線性葉子節點間，這時線性葉子節點會分裂為至少兩個節點，如圖2所示。一般情況下新插入的分支節點將是線性分支節點，但如果先前的線性葉子節點中的索引具有較大隨機分布性質時，新插入的分支節點將可能是位圖型分支節點。
圖2 線性葉節點分裂為低層葉節點示例
7）當插入新索引到“窄節點指針”所指的葉子節點或分支節點時，如果新索引對“窄節點指針”所指節點是“外來者”（即新索引在“窄節點指針”能表示的范圍之外），算法生成一新的線性分支節點，將其插入在“窄節點指針”和“窄節點指針”所指節點之間，新插入索引將作為一“立即節點指針”而存放在新的線性分支節點里，此時新的線性分支節點具有兩個分支。圖3展示了在64位平臺上插入新索引到“窄節點指針”的過程。
圖3 插入“窄節點指針”示例
3 混合索引機制
數據庫表只能逐行訪問，如果要快速訪問表格中記錄，需對表中記錄建立索引。對衛星地面設備監控中需存儲的實時數據的查詢形式非常固定：即從時刻ts起，到時刻te結束，時間間隔為tspan，采集點集合S{S1,S2,…,Sn}在所有時刻的值。因此本文用哈希表、B+樹［8］和Judy array數字樹來建立索引，索引關鍵字為設備采集點描述符與設備采時刻，索引值為相應實時記錄的oid。
當為某采集點的實時記錄建立索引時，首先根據采集點的設備描述符在哈希表中找到采集點的B+樹，然后以實時記錄的采集時刻作為關鍵字在B+樹中插入索引，如圖4所示。本文的B+樹葉子節點中有兩種索引：一種是立即索引，直接與記錄關聯；另一種是壓縮樹索引，指向一棵Judy array壓縮樹。壓縮樹記錄占若干頁面，隨索引插入，壓縮樹會頻繁地刪除或生成內部節點，為此本文以位圖法管理壓縮樹內部空間的分配和刪除。如對64KB大小的壓縮樹，可在頁面首地址處以1024B（1B代表8b）管理整個頁面空間。當索引關鍵字是嚴格遞增順序時，采集點的樹建立索引過程描述如下。
圖4 混合索引示意圖
1）初始時B+樹的高度為1，隨著索引陸續插入節點，該節點將溢出。溢出時節點不像普通B+樹節點會分裂成兩個節點，而是在數據庫表中插入一新的Judy array數字壓縮樹記錄，將葉子節點的全部索引轉存進壓縮樹中，并將該壓縮樹索引插入到B+樹葉子節點里。
數據庫索引范文第3篇
【關鍵詞】XML 1-index F&B索引
可擴展標記語言XML（eXtensible Markup Language）是一門新興的面向Internet應用的標記語言，是為在WEB上使用而優化的SGML子集。XML是一種簡單、與平臺無關并被廣泛采用的標準，是用來定義其它語言的一種元語言。XML具有強大的描述能力，又有適應網絡應用的簡潔性，作為對SGML語言標準的一種改良，XML具有適于異構應用間數據共享，可以進行數據檢索和提供多語種支持等特點。
XML及其相關技術的研究不僅在數據庫理論領域占有一席之地且其水平已成為衡量一個國家信息化程度的重要標準之一。目前很多XML索引技術已被提出，具體可以分為：
（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 索引中將“相似”的節點存放在一個擴展集中，這可能造成DataGuide 中所有擴展集的節點總數是XML 數據圖中節點總數的指數倍。兩節點“相似”概念使得1-index 具有如下兩個優點：
（1）索引大小和XML數據圖大小成線性關系。
（2）索引的擴展集之間不相交，所有擴展集的節點總數和XML 數據圖中節點總數相等。
2 F&B索引
DataGuide 和1-index 保存XML 數據圖中所有邊的信息，可稱為“覆蓋索引”，因為它們可以直接通過索引進行查詢而不必訪問原來的數據。在本文里我們稱child axis 為PC axis，descendant-or-self 為AD axis，我們稱沒有分支謂語的或AD axis為簡單路徑。DataGuide 和1-index只能進行簡單路徑查詢，因此提出了the forward-and-backward index，簡稱F&B索引可以被視為分支路徑表達式查詢的“覆蓋索引”。在所有的XML索引中，F&B索引是可以回答條件約束的最小索引。F&B索引是已有的XML索引中最有效、最強大的一種，F&B索引技術在不斷的改進。
基于路徑索引的XML 查詢方法只能夠解決單路徑查詢，但路徑索引的創建不受XML文檔結構的約束，即XML 文檔可以是樹結構，也可以是圖結構。基于編碼方式下的XML 索引查詢方法能夠有效地解決分支路徑查詢，但是這種方法都對相應的XML 文檔有要求，其所要查詢的XML文檔為樹形結構。
DataGuide的提出解決了這一問題。但是DataGuide僅限于一個常規表達式的查詢，對于多個表達式的復雜查詢不起作用。針對已提出的索引結構的不足，Tova Milo和Dan Suciu提出了模板索引。與以前的方法相比，T-INDEX有以下幾方面的改進：
（1）使交換空間普遍化。
（2）“bisimulation”和“simulation”的提出使索引可以有效的建立。
（3）索引的大小有保證。
（4）與DataGuide相比它是一個完美的一般化的索引結構。
1-index和2-index是模板索引的兩個特殊的索引，模板索引是1-index和2-index的概括和一般化。
對于每個在DB中的節點v，用Lv（DB）或Lv表示從根節點到節點v的路徑字符集合：Lv（DB）={w|w=a1…an}， ? a path v0 …{v， v0 是根節點}。在DB中的節點vu則vu?Lv=Lu，我們用[v]來表示v的等價集合。
這種方法效率低，有兩個原因：
（1）計算等價類需要花費大量的時間。
（2）等價類之間存在重疊，浪費空間。為了解決構建開銷問題，提出改進：v≈u?vu。1-index索引中提出了“bisimulation”和 “simulation”的概念。
DB是一個數據圖。節點間的一個二進制關系 ～是一個backwards bisimulation滿足以下四點：（1）如果v～v’和v是根節點，那么v’也是根節點；（2）相反的，如果v～v’和v’是根節點，那么v也是根節點；（3）如果v～v’，那么對于任意邊uv存在一個邊u’v’，滿足u～u’；（4）相反的，如果v～v’，那么對于任意邊u’v’存在一個邊uv，滿足u～u’。
通過廣度遍歷函數Bfsl（）對樹進行層次遍歷，然后通過merge（）函數對祖先節點相同的同層節點進行合并將XML數據建立成1-index樹，然后再通過Dfsl（）函數對1-index樹進行前序遍歷，對樹的每個節點存儲兩個數值id和level。id用來表示它被遍歷的次序，level用來表示它所在的樹的層數。
3 結論
本文研究了XML存儲與索引技術，主要研究了兩種索引：
（1）板索引中的1-index。
（2）于磁盤的F&B索引。
1-index提出 bisimulation和simulation，索引大小和XML數據圖大小成線性關系，索引的擴展集之間不相交，所有擴展集的節點總數和XML 數據圖中節點總數相等。但1-index只適合查找固定常規表達式，對于多分支的表達式則不能準確地查找。F&B索引是目前XML索引中最強大的一種，它以最小的索引覆蓋所有分支。
參考文獻
[1]劉雨洋，李建中，王宏志等.于后裔聚集F&B索引的XML數據查詢處理算法[J].計算機科學，2006，33（11）：363-365.
[2]孔令波，唐世渭，楊冬青.XML數據的查詢技術[J].Journal of Software，2007， 6（18）：1400-1418.
[3]劉顯敏，李建中，王宏志等.SAJ：以最小化空間代價為目標的F&B索引構建算法[J].計算機研究與發展，2006（43）：413-417.
數據庫索引范文第4篇
關鍵詞：海洋環境；數據庫系統；Oracle；性能優化
中圖分類號：TP311.13
對于傳統數據庫系統進行優化一般遵循“數據庫配置優化”―>“數據庫應用優化”的順序原則。而船載海洋環境數據庫系統是單用戶、單任務系統，I/O操作并不是很頻繁，在系統結構設計合理的情況下，對數據庫配置的優化效果并不十分明顯，同時許多優化專家認為對應用程序的優化可以得到80%的系統性能的提升。因此，數據庫應用優化成為了船載海洋環境數據庫系統性能優化的關鍵技術。
本文將以Oracle優化技術為基礎，針對特殊需求，對船載海洋環境數據庫系統進行應用程序優化技術研究，提出性能優化關鍵技術，實現數據庫系統性能優化。
1 系統功能特點
2 性能優化技術研究
通過功能分析，針對實際需求，研究的工作重點為基于應用程序層面的SQL語句優化技術和索引技術。
2.1 SQL語句優化技術
應用程序對數據庫的操作最終表現為SQL語句對數據庫的操作[1]。對于船載海洋環境數據庫系統而言，SQL語句是對海洋環境數據庫進行操作的惟一途徑，它消耗了70%～90%的數據庫資源，SQL語句的執行效率直接關系著船載海洋環境數據庫數據查詢的速度與效率。
針對查詢操作，SQL語句優化的方法有：
（1）盡量使用占位符代替變量；
（2）where子句限定條件的放置順序應與索引字保持一致；
（3）選擇最有效率的表作為基礎表；
（4）避免采用MATCHES和LIKE通配符匹配查詢；
（5）避免或簡化排序；
（6）避免非開始的子串；
（7）避免相關子查詢；
（8）消除對大型表行數據的順序存取；
船載海洋環境數據庫系統應用主要應用體現為海量數據信息的嵌套查詢，該模式工作效率的致命影響因素主要歸結為對大型表行數據的順序存取。以查詢潮流表中2012年3月的平均潮高信息為例，如果采用順序存取策略，該查詢操作即為三層嵌套查詢操作，假設每層僅查詢300行，該查詢操作仍會產生遍歷3億行數據的龐大工作量。研究發現，為避免該情況發生，我們可以建立索引在連接的字段上。例如，對索引表（年、月、層、……、表名）和統計數據表（表名、經度、平均值……）這兩個表進行跨表連接查詢時，兩個表建立連接，應建立索引在“表名”這個連接字段上。
此外還可以使用并集來避免順序存取。即時建立索引在全部查詢列，然而where子句會自動強迫優化器忽略全部索引而進行順序存取查詢。例如，下面的查詢將會強迫對orders表執行順序操作：
（9）對于大數據量的求和避免使用單一的sum命令處理，可采用groupby方式與其結合；
（10）避免可能會引起磁盤讀寫的rowid操作。
（11）使用臨時表加速查詢。
此外，可以使用Oracle提供的SQLTrace工具和EXPLAINPLAN命令來進一步調整SQL代碼。
SQLTrace提供解析、執行和返回數據次數；執行SQL語句所花CPU時間和執行語句經歷的時間；處理的記錄數和庫緩沖區錯誤次數等有用信息。
EXPLAINPLAN命令可顯示Oracle優化器為SELECT、UPDATE、INSERT和DELETE語句選擇的執行計劃[2]。
2.2 索引優化技術
索引的主要作用是提高索引數據的效率。合理地使用索引、優化數據檢索是提高數據處理速度的一個重要方面。
Oracle中常用的索引類型是B-Tree索引。
2.2.1 B-Tree索引
B-Tree索引是按B數結構組織并存放索引數據的。該索引結構是一棵平衡二叉樹。以海洋環境數據庫中海面氣溫要素客觀分析數據為例，其B-Tree結構示意圖如圖2所示。最頂層的索引塊為根，包含指向分支節點的信息；中間為分支節點，包含指向下級分支部分和指向葉子節點的信息；最底層索引塊為葉子節點，包含索引列和指向表中每個匹配行的ROWID信息。葉子節點是一個雙向鏈表，因此可以對它們進行任何方面的范圍掃描。
2.2.2 使用索引時應注意的問題
盡管在一個表上建立索引可能會加快查詢的速度，但是也必須注意到它的代價：
（1）索引會降低DML操作的速度[5]，因為每一條DML語句只要涉及到索引關鍵字，Oracle系統就得調整索引，這意味著每當有記錄在表中增減或索引列被修改時，索引本身也會被修改并改變存儲次序，從而多占用CPU和磁盤I/O等系統資源。
（2）索引作為一個獨立的對象需要消耗磁盤空間，如果表很大的話，其索引消耗磁盤空間量也會很大。
因此，使用索引時一定要認真分析數據的構成、經常使用的查詢數據列和條件列，仔細選擇索引列和列的組合，切忌對數據量需要頻繁更新的列建立索引[6]。同時，還要根據數據產生和使用的不同階段，適時打開或關閉某些索引，以優化數據查詢和處理。
通過以上對比，說明優化原則是有效的，應用優化原則可以使查詢速度加快。通過大量實驗證明當測試數據的數量及數據表的項數足夠多時，查詢速度提高的幅度極其明顯，對于一個六百萬左右的數據查詢顯示優化前需要60s，優化后只需要12s左右。
3.2 索引優化測試
索引的訪問分為索引唯一掃描和索引掃描范圍兩種模式。船載海洋環境數據庫系統主要應用的是索引唯一掃描模式。在SQL語句中，優化器常通過where子句訪問索引。
以海洋環境數據庫中潮流要素為例進行優化實驗。
在這里定義了一個二級索引機制，先從索引表中通過組合索引查詢到相應的數據表名，然后將該數據表名以變量形式嵌入查詢語句中，并與num列唯一索引組合作為二次索引，這樣大大加快了數據查詢的效率。
同時，由于該SQL語句是用在海洋環境查詢顯示界面，進行以上處理后，可以加快數據顯示的速度。
4 結論
本文通過分析船載海洋環境數據庫系統功能特點，針對其需求特點，提出了性能優化關鍵技術SQL語句優化技術和索引技術。使用這些關鍵技術成功地進行了海洋環境數據庫系統性能的調整和程序的優化，從而有效地提高了數據查詢顯示的速度，更好地保障了海洋環境數據的安全性和可靠性，為船舶的海上航行提供了必要的決策支持，具有一定的實際應用價值。
參考文獻：
[1]袁愛梅.Oracle數據庫性能優化研究[D].華東師范大學，2007.
[2]高艷春，周兆確，唐艷軍.Oracle性能調整與優化[M].北京：人民郵電出版社，2002.
[3]路川，胡欣杰.Oracle10g寶典[M].北京：電子工業出版社，2008.
[4]毛選，魏海萍，孫思云.OCP：Oracle9i性能調整學習指南[M].北京：電子工業出版社，2003.
[5]何致億.Oracle9i實務管理講座――系統核心篇[M].北京：電子工業出版社，2003.
[6]Oracle.Oracle9iDBAFundamentalsIIVolume1StudentGuide[M].2002.
[7]高峰.基于Linux的船載海洋環境數據庫系統設計與實現[D].哈爾濱工程大學，2008.
[8]肖軍.ORACLE數據庫性能調整與優化[D].武漢大學，2004.
[9]李捷.短信系統中的Oracle數據庫性能優化及實施[D].重慶大學，2007.
數據庫索引范文第5篇
[關鍵詞]B樹；索引；數據庫管理軟件
中圖分類號：TQ1 文獻標識碼：A 文章編號：1009-914X（2014）23-0252-02
1 引言
索引是一個單獨的、物理的數據庫結構，它是某個表中一列或若干列值的集合和相應的指向表中物理標識這些值的數據頁的邏輯指針清單。表的存儲由兩部分組成，一部分用來存放數據頁面，另一部分存放索引頁面。通常，索引頁面相對于數據頁面來說小得多。數據檢索花費的大部分開銷是磁盤讀寫，沒有索引就需要從磁盤上讀表的每一個數據頁，如果有索引，則只需查找索引頁面就可以了。所以建立合理的索引，就能加速數據的檢索過程。
數據庫索引就是加快檢索表中數據的方法。數據庫的索引類似于書籍的索引。在書籍中，索引允許用戶不必翻閱完整個書就能迅速地找到所需要的信息。在數據庫中，索引也允許數據庫程序迅速地找到表中的數據，而不必掃描整個數據庫。
2 B樹的定義
2.1 B樹的結構
本文刪除記錄時引起的結點內部數據變化，甚至整個結點內的記錄都無效時，會調用刷新函數。該函數以樹的根為參數，在遍歷樹時調用結點類的寫入函數將新數據覆蓋到數據庫文件的原地址上。而有些被刪除了的結點，在內存中的B樹已經無法聯系到，所以無法寫入覆蓋，也無需操作。所以實際上本系統的刪除操作不會減少數據庫文件的大小。
4 總結
本文描述了設計和實現了一種基于B樹的小型數據庫管理系統的過程。詳細敘述了B樹在本系統中的實現和應用，以及本系統如何構造了如常見數據庫的表與字段，以及各個操作的流程。對B樹性能進行分析計算。最終實驗表明，B樹非常適合作為存取輔助設備的數據結構。
參考文獻
[1] Thomas H.Cormen， Charles E.Leiserson等著，潘金貴等譯.算法導論（第2版） [M].北京：機械工業出版社，2006.9.
