随机跳跃索引:一种支持随机插入的可信赖索引  

A Trustworthy Index for Inserting Random Sequences

作　　者：刘凤晨[1] 黄河[2] 刘庆文[3] 丁永生[1,4] 

机构地区：[1]东华大学信息科学与技术学院,上海201620 [2]北京航空航天大学软件学院,北京100083 [3]北京科技大学信息工程学院,北京100083 [4]数字化纺织服装技术教育部工程研究中心,上海201620

出　　处：《计算机学报》2009年第5期974-981,共8页Chinese Journal of Computers

基　　金：国家项目(A2120061061);上海市科学技术委员会重点基础研究项目(08JC1400100);上海市人才发展资金(001);上海市领军人才后备人选专项资金资助~~

摘　　要：跳跃索引是一种可信赖性索引,但只能为严格单调递增的序列建立索引,不能处理非顺序序列.为了解决这个问题,文中提出了一种新的索引,它可以对任意顺序的序列建立索引,并且依然保证索引的可信赖性.通过在原有跳跃索引结构中加入左侧跳跃指针的方法,索引节点可以根据待加入节点值的大小将其纳入自己的左侧或右侧指针以处理随机序列;索引结构中的每一个节点到根节点的路径固定且唯一,保证了索引的可信赖性.实验结果和理论证明都表明该索引是可以处理随机序列的可信赖索引,相对原有索引,索引建立复杂度明显降低且具有相同的查找复杂度.文中的创新之处是在保证索引的可信赖性的基础上解决了跳跃索引不能为随机序列建立索引的问题.Jump Index is a kind of trustworthy index which can only build index for strictly monotonically increased sequences rather than unordered sequences. To solve this problem, this paper proposes a novel index supporting building index for random sequences, without losing the trustworthy of jump index. By adding left pointers on the node of jump index, the candidate node in random sequences can be indexed into one of the left or right pointers of a node in the index. The left jump pointers are used to index nodes with less value than current node＇s value, while right jump pointers point to those nodes with higher value. Every node in the index has the unique and permanent path from root node, which ensures the trustworthy in the index. Experiment results and proofs in this paper show that the index is trustworthy and supports indexing for random sequences, also it has more efficiency of building index and same complexity of search compared with jump index. The contribution of this paper is that the new index with trustworthy solve the problem that jump index cannot insert and build index for random sequences.

关 键 词：可信赖性 倒排表 索引 B+树 检索 算法 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]