《计算机学报》文章摘要   全文下载
文章题目	随机跳跃索引：一种支持随机插入的可信赖索引
作者	刘凤晨1) 黄河2) 刘庆文3) 丁永生1),4)
作者单位	1)(东华大学信息科学与技术学院 上海 201620) 2)(北京航空航天大学软件学院 北京 100083) 3)(北京科技大学信息工程学院 北京 100083) 4)(数字化纺织服装技术教育部工程研究中心 上海 201620)
发表年份	2009
发表月份	5期(974—981)
文章摘要	摘要 跳跃索引是一种可信赖性索引，但只能为严格单调递增的序列建立索引，不能处理非顺序序列.为了解决这个问题，文中提出了一种新的索引，它可以对任意顺序的序列建立索引，并且依然保证索引的可信赖性.通过在原有跳跃索引结构中加入左侧跳跃指针的方法，索引节点可以根据待加入节点值的大小将其纳入自己的左侧或右侧指针以处理随机序列；索引结构中的每一个节点到根节点的路径固定且唯一，保证了索引的可信赖性.实验结果和理论证明都表明该索引是可以处理随机序列的可信赖索引，相对原有索引，索引建立复杂度明显降低且具有相同的查找复杂度.文中的创新之处是在保证索引的可信赖性的基础上解决了跳跃索引不能为随机序列建立索引的问题. 关键词 可信赖性；倒排表；索引；B+树；检索；算法 中图法分类号 TP391 DOI号: 10.3724/SP.J.1016.2009.00974