摘  要： 對于一些查詢密集型的應用，查詢操作的響應速度往往是決定其系統性能的關鍵因素，因此如何提高查詢響應速度和系統吞吐率成為首要任務。經過實驗證明，通過將查詢數據緩存可以有效地解決這個問題。
關鍵詞： 數據集成；數據緩存；B_Link樹

　目前，在企業中由于開發時間或開發部門的不同，往往存在有多個異構的在不同軟硬件平臺上的信息系統同時運行，這些系統的數據源彼此獨立、相互封閉，使得數據難以在系統之間交流、共享和融合，從而形成了“信息孤島”問題。如何對這些數據進行有效的集成管理，屏蔽這些信息的異構部分，并給上層用戶或應用提供一個統一透明的訪問接口，以透明的方式訪問各信息源，成為當今企業和組織所關心的問題。數據集成也就是在這樣的情況下提出來的。
　通過復制的方式，將各種異構數據源中的數據抽取到一個統一的數據源中（如數據倉庫），同時維護數據源整體上數據的一致性。該方式實現了對物理數據庫異構的屏蔽和數據訪問的控制，以便于提供一個統一的訪問接口、提高訪問效率和系統的獨立性。圖1是一個典型的基于數據復制方式建立的數據倉庫體系結構圖。

　此外，在把數據倉庫應用于數據集成時，還需解決如何應對大量客戶端應用程序對數據倉庫進行訪問時能夠做出快速的響應。但是一個數據庫的連接資源是有限的，大量的并發查詢操作必定會導致查詢效率的下降，導致客戶端應用程序獲取數據的延遲時間大大增加。這樣的情況用戶是不想看到的，甚至有些對時間有一定限制的應用因為不能及時獲得所需的數據而無法正常工作而迫切需要解決這一問題。出現這個問題的原因是：由于連接數據庫是一件耗時的工作，而且一般數據庫服務器能同時提供的連接數也相當有限，出現了性能瓶頸。解決這個問題的有效方法可以通過將查詢過的數據緩存起來，若下次有同樣的查詢時則不需再連接數據庫，而是直接從緩存中獲得，這樣不但節省了連接數據庫的時間開銷，而且省略了查詢數據庫所帶來的時間和資源的消耗。但是對于數據緩存的組織不能簡單了事，必須得經過精心的設計。為此，本文提出一種基于B_Link樹的方法來管理緩存。下面將詳細介紹如何組織和管理緩存。
1 數據緩存的體系結構
　無論多么強大的服務器，其內存的數量都是有限的，故在考慮大數據量的緩存時，不可能將所有的數據都緩存在內存中，而要考慮使用二級緩存。基于B_Link樹緩存總體結構如圖2所示，為了解決內存有限的問題，采用了兩層緩存結構，用一張哈希表將查詢與索引表對應起來。若已經建立了緩存，則對應有一張緩存索引表，用于記錄數據記錄塊的位置（數據記錄塊是指把數據記錄打包成塊進行保存和傳輸）。若數據在內存中則直接取出發送給客戶端應用程序即可，否則需通過關鍵詞去磁盤中獲取。磁盤中的緩存是基于B_Link樹組織起來的。

2 B_Link樹的基本結構和操作
2.1 數據結構
　B_Link樹是在B+樹的基礎上加以改進的，主要添加了一個高值域和非葉子結點指向其右兄弟結點的Link指針。B_Link樹結構如圖3所示，其中帶下劃線的表示高值域，主要用于提升并發操作的性能。Link指針可以使得每個結點至少可以有兩條路徑訪問到，提高了查詢速度。

2.2 B_Link樹的查詢操作

　B_Link樹的查詢操作是比較容易的，具體操作可查閱參考文獻[1]。其基本思路是：首先檢查根結點，找到大于查詢關鍵字V的最小搜索碼值（假設搜索碼值為ki）；然后，順著指針pi到達另一個結點，如果查詢關鍵字比該結點所有關鍵字都大，則遍歷指針指向當前結點的右兄弟結點，在達到最后一層葉子結點時，若找到則返回該結點，否則返回空。
2.3 B_Link樹的插入操作
　B_Link樹的插入操作是一個比較復雜的過程，既要保證B_Link樹的基本結構不受到破壞，還要保證并發操作時不會出現錯誤，所以有必要進行加鎖處理。下面介紹幾種操作：
?。?）x←scannode（v，A）：掃描指針A指向的結點，找到能發現key值v的下一個節點并賦給x。
　（2）A←get（current）：表示將current結點讀入內存中并把其指針賦給A。
?。?）A←node.insert（A，w，v）：把指針w和帶關鍵字v插入指針A指向的結點。
?。?）u←allocate（B）：為結點B在磁盤中分配一新的頁，并將其指針賦給u。
?。?）A，B←rearrange old A：把需要分裂的A指向的結點分裂成新的由A和B指向的結點。
?。?）lock（current）：表示將current結點鎖住，防止其他并發操作對該結點進行修改，但這并不會鎖住查詢操作。需要說明的是：如果查詢某個結點時，這個結點進行了分裂操作，有可能會出現查詢關鍵字大于高值域的情況，這時只要將當前指針指向右兄弟結點即可，并在父結點中添加一搜索碼和指針指向右兄弟結點（細節可參考文獻[1]）。
　下面是插入算法的偽代碼：
    Procedure insert（v）
    initialize stack；//初始化一個堆棧，用于保存祖先結點
    current←root；
    A←get（current）；
//將current讀入內存中并將其指針賦給A
    while current is not a leaf do
    //從上至下遍歷結點，直到葉子結點
    Begin
        t←current；
        current←scannode（v，A）；
        if new current was not link pointer in A then
            push（t）；
        A ← get（current）；
    end；
    lock（current）；    //將該結點鎖住
    A←get（current）；    
    move.right；
//如果有必要將當前結點指向其右兄弟結點
    if v is in A then stop    
//如果原來的樹中存在關鍵字為v的結點，則算法停止
    w←pointer to pages allocated for record associated with v；    //把與v相關聯的指針賦給w
    Doinsertion：
    if A not need to split  //若結點無須分裂
    Begin
        A←node.insert（A. w. v）；
//把w指針和關鍵字v插入A指向的結點中，返回新的指針A
        put（A， current）；
//把指針A放入current結點適當的位置
        unlock（current）；
    end else begin
        u←allocate（1 new page for B）；
        A，B←rearrange old A，adding v and w， to make 2 nodes；//把A指向的結點    分裂成2個結點，
//分別由A和B指向
（link ptr of A， link ptr of B）←（u， link ptr of old A）；
//把分裂出的新結點的右兄弟結點指針
//指向未分裂前A的右兄弟結點
        y←getmaxvalue（A）；
//取出A指向的結點中的最大的值（注意不是高值域）
        put（B，u）；
        put（A， current）；  //開始將指針放入父結點中
        v ← y；
        w ← u；
current ← pop（stack）；  
//進行回溯處理，檢測父親是否需要繼續分裂
        lock（current）；
        A ← get（current）；
        move.right；
        unlock（oldnode）；
        goto Doinsertion； 
end
　其中的move.right操作表示將指針指向其右兄弟結點。對于刪除算法，基本思路與插入算法類相同，要保持樹結構和并發操作的正確性，具體可參閱文獻[2]。此外，充分利用內存中的緩存也是很是重要的，在這里可以采用一種預讀取的辦法，即在磁盤緩存中檢索到要讀的結點時，在傳輸數據這段時間里可以將接下來的一些記錄數據塊讀入內存緩存中，這樣在下次取數據時可以減少一些磁盤IO操作，提高讀取性能。
3 性能測試分析
　測試環境如下：
　數據庫服務器端配置：數據庫Oracle 10g，操作系統Linux 2.6，CPU 2.1 GHz X4，內存4 GB，硬盤串口500 GB。查詢中間件服務器與數據庫服務器是同樣的配置，但不在同一臺服務器上，對查詢中間件的介紹可以參閱文獻[3]。
　客戶端配置：CPU 2.6 GHz X2，內存2 GB，硬盤串口160 GB。表1和表2是在不同的并發查詢數目和不同的查詢規模下經過緩存和未經緩存所需時間的對比。表1中查詢記錄數固定為10萬條，表2中并發查詢數固定為50個。

　通過對比直接查詢數據庫和經過緩存優化后進行查詢的實驗數據可知，通對對數據進行緩存處理，效率提升是非常明顯的，尤其是在并發查詢的數量比較大時，效率提升更為明顯。
　本文把數據緩存應用于基于數據倉庫方式的數據集成中，而且，在組織緩存時采用了兩級緩存結構，并采用了B_Link樹來組織磁盤中的緩存中的結構。因此提高了并發查詢數據的效率、縮短了客戶端查詢數據的響應時間、提高了工作效率。但本文方法還存在一些不足，例如，如何更有效地協調磁盤和內存中的緩存交互，這一設計的好壞也直接關系到查詢的性能，這有待以后進一步完善和優化。
參考文獻
[1] PHILIP L， LEHMAN S， Bing Yao. Efficient locking for concurrent operations on B-trees[M]. ACM Transactions on Database Systems，1981：655-663.
[2] 孫兆玉，黃宇光，朱鴻宇. 一種基于B_Link樹結構的高性能緩存機制[J].高性能計算技術，2007，186：23-24.
[3] 房元平，許嬌陽，葛珂.流水線處理技術在數據集成中的應用[J].微型機與應用，2010（24）：67-69.
[4] JOHNSON T. A highly concurrent priority queue based on the B_Link tree[R]. Technical Report，University of Florida，1991.
[5] CORMEN T H， CHARLES E. LEISERSON R L， et al. Introduction to algorithms（second edition）[M]. The MIT Press， 2009：434-453.