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

摘要：

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

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

所属期刊栏目：32

分类号：TP391(计算技术、计算机技术)

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

在线出版日期：2009-06-16（万方平台首次上网日期，不代表论文的发表时间）

页数：共8页

页码：974-981