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

• 作者: 丁永生 刘凤晨 刘庆文 黄河
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: 可信赖性 倒排表 索引 B+树 检索 算法
• 年，卷（期）: 2009,（5）
• 所属期刊栏目: 研究论文与技术报告
• 页码范围: 974-981
• 页数: 8页
• 分类号: TP391
• 字数: 6912字
• 语种: 中文
• DOI: 10.3724/SP.J.1016.2009.00974

摘要

跳跃索引是一种可信赖性索引,但只能为严格单调递增的序列建立索引,不能处理非顺序序列.为了解决这个问题,文中提出了一种新的索引,它可以对任意顺序的序列建立索引,并且依然保证索引的可信赖性.通过在原有跳跃索引结构中加入左侧跳跃指针的方法,索引节点可以根据待加入节点值的大小将其纳入自己的左侧或右侧指针以处理随机序列;索引结构中的每一个节点到根节点的路径固定且唯一,保证了索引的可信赖性.实验结果和理论证明都表明该索引是可以处理随机序列的可信赖索引,相对原有索引,索引建立复杂度明显降低且具有相同的查找复杂度.文中的创新之处是在保证索引的可信赖性的基础上解决了跳跃索引不能为随机序列建立索引的问题.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	丁永生	东华大学信息科学与技术学院	196	2432	22.0	42.0
5	黄河	北京航空航天大学软件学院	30	279	7.0	16.0
6	刘庆文	北京科技大学信息工程学院	7	48	3.0	6.0
7	刘凤晨	东华大学信息科学与技术学院	1	0	0.0	0.0