计算机学报
計算機學報
계산궤학보
CHINESE JOURNAL OF COMPUTERS
2009年
5期
974-981
,共8页
刘凤晨%黄河%刘庆文%丁永生
劉鳳晨%黃河%劉慶文%丁永生
류봉신%황하%류경문%정영생
可信赖性%倒排表%索引%B+树%检索%算法
可信賴性%倒排錶%索引%B+樹%檢索%算法
가신뢰성%도배표%색인%B+수%검색%산법
跳跃索引是一种可信赖性索引,但只能为严格单调递增的序列建立索引,不能处理非顺序序列.为了解决这个问题,文中提出了一种新的索引,它可以对任意顺序的序列建立索引,并且依然保证索引的可信赖性.通过在原有跳跃索引结构中加入左侧跳跃指针的方法,索引节点可以根据待加入节点值的大小将其纳入自己的左侧或右侧指针以处理随机序列;索引结构中的每一个节点到根节点的路径固定且唯一,保证了索引的可信赖性.实验结果和理论证明都表明该索引是可以处理随机序列的可信赖索引,相对原有索引,索引建立复杂度明显降低且具有相同的查找复杂度.文中的创新之处是在保证索引的可信赖性的基础上解决了跳跃索引不能为随机序列建立索引的问题.
跳躍索引是一種可信賴性索引,但隻能為嚴格單調遞增的序列建立索引,不能處理非順序序列.為瞭解決這箇問題,文中提齣瞭一種新的索引,它可以對任意順序的序列建立索引,併且依然保證索引的可信賴性.通過在原有跳躍索引結構中加入左側跳躍指針的方法,索引節點可以根據待加入節點值的大小將其納入自己的左側或右側指針以處理隨機序列;索引結構中的每一箇節點到根節點的路徑固定且唯一,保證瞭索引的可信賴性.實驗結果和理論證明都錶明該索引是可以處理隨機序列的可信賴索引,相對原有索引,索引建立複雜度明顯降低且具有相同的查找複雜度.文中的創新之處是在保證索引的可信賴性的基礎上解決瞭跳躍索引不能為隨機序列建立索引的問題.
도약색인시일충가신뢰성색인,단지능위엄격단조체증적서렬건립색인,불능처리비순서서렬.위료해결저개문제,문중제출료일충신적색인,타가이대임의순서적서렬건립색인,병차의연보증색인적가신뢰성.통과재원유도약색인결구중가입좌측도약지침적방법,색인절점가이근거대가입절점치적대소장기납입자기적좌측혹우측지침이처리수궤서렬;색인결구중적매일개절점도근절점적로경고정차유일,보증료색인적가신뢰성.실험결과화이론증명도표명해색인시가이처리수궤서렬적가신뢰색인,상대원유색인,색인건립복잡도명현강저차구유상동적사조복잡도.문중적창신지처시재보증색인적가신뢰성적기출상해결료도약색인불능위수궤서렬건립색인적문제.
