亚洲免费av电影一区二区三区,日韩爱爱视频,51精品视频一区二区三区,91视频爱爱,日韩欧美在线播放视频,中文字幕少妇AV,亚洲电影中文字幕,久久久久亚洲av成人网址,久久综合视频网站,国产在线不卡免费播放

        ?

        基于CB+-tree索引的XML時態(tài)查詢技術

        2016-11-18 04:20:56徐海燕姚保峰朱洪浩
        關鍵詞:鏈表快照關鍵字

        馬 程 徐海燕 姚保峰 王 磊 朱洪浩

        (1. 蚌埠學院計算機科學與技術系, 安徽 蚌埠 233000;2. 華為軟件技術有限公司南京研究所, 南京 210008)

        ?

        基于CB+-tree索引的XML時態(tài)查詢技術

        馬 程1徐海燕2姚保峰1王 磊1朱洪浩1

        (1. 蚌埠學院計算機科學與技術系, 安徽 蚌埠 233000;2. 華為軟件技術有限公司南京研究所, 南京 210008)

        針對XML時態(tài)查詢問題,使用CB+-tree索引,將時態(tài)信息作為索引關鍵字,采用實體地址和長度隨機讀取查詢,在葉子節(jié)點處添加新的鏈表節(jié)點,對葉子節(jié)點中的關鍵字按照tend進行二次排序,減少了查詢比較次數(shù)。實驗結果表明,CB+-tree索引在實現(xiàn)實體軌跡、快照和時間段3類時態(tài)查詢時,優(yōu)于B+-tree索引,特別是對于大容量的XML文檔,其時態(tài)查詢效果更佳。

        CB+-tree索引; XML; 時態(tài)查詢

        隨著計算機和網(wǎng)絡技術的不斷發(fā)展,XML(Extensible Markup Language)成為Web上一種信息表示與交換的標準數(shù)據(jù)格式,其存儲、索引和查詢成為XML相關技術領域研究的熱點[1-3]。索引對查詢起著重要的作用,要實現(xiàn)某種查詢必須為其建立適當?shù)乃饕龣C制,為此,針對時態(tài)查詢效率問題,基于CB+-tree(Changing B+-tree)索引,分別實現(xiàn)了實體軌跡、快照和時間段查詢,該方法在實現(xiàn)時態(tài)查詢時,比B+-tree索引更高效。

        1 CB+-tree原理

        CB+-tree是改進B+-tree的平衡樹,根節(jié)點處至少有2個子節(jié)點,包含m個關鍵字的中間節(jié)點,m+1個指針Pi(每個指針指向下層子節(jié)點)[4-6]。CB+-tree不同于B+-tree,其葉子節(jié)點新增3種指針。

        (1) 第1種指針,用于指向同一層次節(jié)點,有前向指針和后向指針,即葉子節(jié)點之間形成一個雙向鏈表,如圖1所示。

        圖1 前向指針和后向指針

        (2) 第2種指針,用于指向處理重復鍵值的查詢鏈表(QList),每個葉子節(jié)點中包含1個指針數(shù)組m_pointer,添加QList之后的葉子節(jié)點如圖2所示。如插入的鍵值與葉子節(jié)點中的某個鍵值相同時,就在其后面分配1個鏈表,用來存儲剛插進的新鍵值,插入時按照tend從大到小的順序進行。

        圖2 處理重復鍵值指針

        (3) 第3種指針,仍然指向鏈表,但該鏈表的作用是,將該葉子節(jié)點中的所有數(shù)據(jù)(不包括m_pointer所指鏈表中的數(shù)據(jù))按照tend從大到小的順序,依次插入單鏈表。當進行快照查詢或時間段查詢時,可以減少與tend的比較時間,以提高查詢效率。

        2 CB+-tree查詢

        基于CB+-tree索引,針對實體軌跡的查詢、快照和時間段查詢比較高效。下面分別介紹CB+-tree如何實現(xiàn)這3類查詢。

        2.1 實體軌跡查詢

        定義實體軌跡查詢的索引關鍵字類型如下:

        public struct KeyType

        {public string id;∥ id為實體號

        public int addr;∥ addr為實體在文檔中的地址

        public int length;∥ length為實體的信息長度

        public string filename;∥ filename為XML文檔的路徑

        };

        實體軌跡查詢,需查詢某個實體的歷史和當前信息,以實體的ID號作為索引關鍵字,按照ID號從小到大的順序,依次將所有實體插入CB+-tree。

        實體軌跡查詢算法描述:

        Input:ID實體號;Output:滿足查詢條件為ID的實體歷史軌跡,即實體信息XML片段。

        Step1:從根節(jié)點開始,使pNode=根節(jié)點;

        Step2:循環(huán)查找到第一個關鍵字≥ID的位置i,取pNode=pNode.GetPointer(i)。如果pNode為葉子節(jié)點,則循環(huán)停止,否則繼續(xù)執(zhí)行Step2;

        Step3:在葉子節(jié)點中繼續(xù)查找,當找到滿足ID的關鍵字時,則通過該關鍵字中的addr和length,到filename中讀取滿足查詢條件的實體信息。

        2.2 快照和時間段查詢

        以下建立的索引,可以同時滿足快照和時間段查詢。

        快照和時間段查詢的關鍵字類型定義與實體軌跡關鍵字結構定義方式相同,但該處新增了tend和tstart字段,結構為(ID,tstart,tend,addr,length,filename)。其中tstart和tend分別表示實體號為ID的事務的開始時間和結束時間。

        快照和時間段查詢都需要跟時態(tài)屬性進行比較,因此以每個實體的tstart作為索引關鍵字,根據(jù)tstart從小到大的順序,依次將每個實體插入CB+-tree,最后在葉子節(jié)點的MPointer和m_pointer[i]的鏈表中將關鍵字根據(jù)tend進行第2次排序。

        快照查詢算法描述:

        Input:快照查詢時間snapshot;Output:滿足快照時間的所有實體信息。

        Step1:從根節(jié)點開始,將pNode指向根節(jié)點;

        Step2:通過while循環(huán)查找到第1個鍵值大于等于snapshot的位置i,pNode指向GetPointer(i)所指的下一層節(jié)點,若pNode為葉子節(jié)點,循環(huán)結束。否則,繼續(xù)執(zhí)行Step2;

        Step3:在pNode中繼續(xù)查找。若pNode是第1個滿足條件的葉子節(jié)點,則其中只有部分關鍵字的tstart滿足條件。通過循環(huán)統(tǒng)計出滿足條件的關鍵字個數(shù)nocount,循環(huán)nocount次可以輸出該關鍵字中滿足條件的實體信息。然后pNode通過前向指針m_PreNode指向其前一個葉子節(jié)點。若pNode非空,轉向Step3繼續(xù)執(zhí)行,否則,循環(huán)結束。若pNode非第1個滿足條件的葉子節(jié)點,到達pNode之后,通過MPointer和m_pointer[i]中關鍵字的tend與snapshot繼續(xù)比較, 找到符合tend>=snapshot的關鍵字,通過addr及l(fā)ength取出滿足條件的實體信息。pNode通過前向指針m_PreNode指向其前一個葉子節(jié)點。若pNode非空,則轉向Step3繼續(xù)執(zhí)行,否則循環(huán)結束。

        時間段查詢與快照查詢過程類似,找到tstart滿足條件的實體之后,將時間段結束時間與各實體的tend進行比較,而快照查詢直接用快照時間與tend進行二次比較篩選。時間段查詢算法與快照查詢算法原理相似。

        3 實驗結果及分析

        實驗環(huán)境:CPU為Intel Pentium D 930(1 G),系統(tǒng)為Windows XP Professional,生成和查詢XML文檔的開發(fā)環(huán)境為.NET2003中的C#。實驗數(shù)據(jù)來自于TimeCenter(http:∥timecenter.cs.aau.dksoftware.htm)的職工數(shù)據(jù)庫。該數(shù)據(jù)庫3個文件夾共有15 004個XML文件,300 000個職工的歷史和當前信息。為了驗證CB+-tree時態(tài)查詢的高效性,將其與B+-tree索引及DOM下的時態(tài)查詢作比較,其中DOM為無索引下的查詢。

        3.1 實驗過程

        (1) 分別取5 002、10 004、15 004個XML文檔進行合并,合并后大小依次為85、169、254 MB。

        (2) 在合并后的3個文檔上分別實現(xiàn)文中定義的實體軌跡查詢(簡稱Q1)、快照查詢(簡稱Q2)、時間段查詢(簡稱Q3)。

        3.2 查詢效率分析

        文檔大小分別為85、169、254 MB,基于DOM的實體軌跡查詢時間分別為7 804、15 719和67 490 ms,而基于B+-tree和CB+-tree的查詢時間幾乎為0 ms,由此可知隨著XML文檔的增大,基于CB+-tree的實體軌跡查詢效率提高顯著。

        表1給出了快照查詢和時間段查詢性能比較表。由表1可知:XML文檔越大,基于CB+-tree的查詢效率比基于DOM、B+-tree的查詢效率提高得越顯著;查詢的實體數(shù)目比較小時,效率提高得更明顯;基于CB+-tree的查詢效率比基于B+-tree的也有所提高?;贒OM的模型未使用索引,是把整個XML文檔調入內存,基于整個文檔進行遍歷查詢。當處理的XML文檔數(shù)據(jù)量較大時,存在大量無謂的數(shù)據(jù)遍歷和磁盤訪問問題,其性能較差?;贐+-tree查詢,減少了對XML文檔的遍歷,但因未對實體的tend時間及重復鍵值進行處理,快照查詢和時間段查詢需與tstart滿足條件的所有關鍵字的tend繼續(xù)比較。而CB+-tree中的MPointer和m_pointer[i]指向的鏈表對tend進行了從大到小的排序,查詢時遇到第1個tend不滿足條件的數(shù)據(jù)后,該鏈表后面的數(shù)據(jù)不需要繼續(xù)比較,減少了大量的遍歷,降低了查詢時間,而且能通過實體地址準確地隨機定位到實體,從而提高查詢效率。

        表1 快照查詢和時間段查詢性能比較表

        4 結 語

        CB+-tree索引將時態(tài)信息作為索引關鍵字,采用實體地址addr和長度length隨機讀取滿足查詢條件的信息,在CB+-tree的葉子節(jié)點處添加新的鏈表節(jié)點,對葉子節(jié)點中的關鍵字按照tend進行二次排序,極大地減少了查詢比較次數(shù),提高了查詢的響應時間。實驗結果表明,CB+-tree索引在時態(tài)查詢時查詢效率優(yōu)于B+-tree索引,尤其是對于大容量的XML文檔。

        [1] MENDELZON O A, RIZZOLO F, VAISMAN A.Indexing Temporal XML Documents[C]∥VLDB.Proceedings of the 30th VLDB Conference.San Francisco:Margan Kaufmann,2004:216-227.

        [2] 葉小平,陳鎧原,湯庸,等.時態(tài)XML索引技術[J].計算機學報,2007,30(7):1074-1085.

        [3] 湯娜,劉瑞君,陳羅武,等.XML文檔中時態(tài)信息存儲方法研究與比較[J].計算機科學,2008,35(5):226-228.

        [4] 徐紅波,姚念民,韓啟龍,等.支持線段查詢索引結構CB樹[J].計算機工程與應用,2015,51(11):114-123.

        [5] 肖蒙,王梅.SHB+樹:一種面向時態(tài)數(shù)據(jù)的分段混合索引[J].計算機研究與發(fā)展,2015,52(增刊l):28-36.

        [6] 葉小平,林衍崇,陳釗瀅,等.時態(tài)索引Txmlsindex[J].華南師范大學學報(自然科學版),2015,47(1):116-12.

        XML Temporal Query Technology Based on CB+-tree Index

        MACheng1XUHaiyan2YAOBaofeng1WANGLei1ZHUHonghao1

        (1.Department of Computer Science and Technology of Bengbu College, Bengbu Anhui 233000, China; 2.Nanjing Research Institute of Huawei Software Technology Limited Company, Nanjing 210008, China)

        Aiming at the problem of XML temporal query, this paper uses the entity address and length to access query conditions based on CB+-tree randomly. By adding new node in the leaf node, it can sort the keyword in the leaf node according to tend for two times to reduce the query times. The experimental results show that the CB+-tree index method is better than B+-tree index in the implementation of three kinds of temporal queries, such as entity track, snapshot and time period, especially for large capacity XML documents.

        CB+-tree index; XML; temporal query

        2016-05-30

        2014年度蚌埠學院院級自然科學研究重點項目“基于時空XML數(shù)據(jù)庫存儲和索引技術研究”(2014ZR03ZD);2015年度安徽省教育廳項目“基于XML的Web信息抽取關鍵技術研究”(11305215KJ09);2016年度安徽省自然科學研究重點項目“XML交互式信息檢索系統(tǒng)關鍵技術研究”(KJ2016A456)

        馬程(1980 — ),女,安徽阜陽人,碩士,講師,研究方向為數(shù)據(jù)挖掘、時空數(shù)據(jù)庫索引。

        TP311.13

        A

        1673-1980(2016)05-0075-03

        猜你喜歡
        鏈表快照關鍵字
        EMC存儲快照功能分析
        天津科技(2022年5期)2022-05-31 02:18:08
        履職盡責求實效 真抓實干勇作為——十個關鍵字,盤點江蘇統(tǒng)戰(zhàn)的2021
        華人時刊(2022年1期)2022-04-26 13:39:28
        成功避開“關鍵字”
        基于二進制鏈表的粗糙集屬性約簡
        跟麥咭學編程
        基于鏈表多分支路徑樹的云存儲數(shù)據(jù)完整性驗證機制
        創(chuàng)建磁盤組備份快照
        數(shù)據(jù)恢復的快照策略
        一張“快照”搞定人體安檢
        鏈表方式集中器抄表的設計
        電測與儀表(2014年1期)2014-04-04 12:00:22
        精品国产一区二区三区不卡在线| 波多野结衣一区二区三区视频 | 九九日本黄色精品视频| 国产精品一区二区韩国av| 亚洲av无码一区二区三区网址| 亚洲人成无码www久久久| 国产女奸网站在线观看| av在线资源一区二区| 欧洲美女黑人粗性暴交视频| 全免费a级毛片免费看网站| 中文字幕大屁股熟女乱| 白嫩少妇在线喷水18禁| 欧美性猛交aaaa片黑人| 国产在线观看www污污污| 日韩成人精品日本亚洲| 亚洲专区路线一路线二网| 国产精品白浆在线观看免费| 欧美疯狂做受xxxxx高潮| 亚洲国产成人aⅴ毛片大全| 日本久久精品福利视频| 成人aaa片一区国产精品| 四虎影视亚洲精品| av资源在线永久免费观看| 久久在一区二区三区视频免费观看| 中文字幕无线码| 亚洲天堂资源网| 精品奇米国产一区二区三区| 伊人久久精品无码av一区| 国产一线二线三线女| 亚洲无线码一区在线观看| 大尺度极品粉嫩嫩模免费| 午夜精品久久久久久久无码| 色94色欧美sute亚洲线路二| 亚洲综合精品在线观看中文字幕 | aaaaaa级特色特黄的毛片| 乱人伦人妻中文字幕不卡| 深夜一区二区三区视频在线观看| 久热国产vs视频在线观看| 亚洲综合久久久| 国产一区二区在线观看av| 性做久久久久久免费观看|