索引( indexing)的方法 索引函数Y:z→D 结点的整数索引值z∈z 索引法是顺序存储法的一种推广,它也 结点的存储地址d∈D 使用整数编码来访问数据结点位置 紫引衰 救库记 举位▲张倍墙写 北大单张铭写 叔新有,命邮 倒排文件 倒排文件与线性索引 ment Location Term Pointer to 19 Inverted elk 43 真大影张帖写 叔新有,量究 散列( hashing)的方法 散列( hashing)的方法 散列是索引方法的一种延伸和扩展 散列函数h(s)除了它取非负整数值外,关 更快的检索速度 键的问题 受数组元素地址计算启发 Loc( A[D= Loc(A[OD+i* sizeof(Element); 恰当地选择散列函数 ■散列函数是将字符串s映射到非负整数z的一类 ■如何建造散列表 函数h:s→z, 在构建散列表的中间解决碰撞的办法 对任意的s∈S,散列函数h(s)=z,z∈2 北真大学张铭编写 聊张帖写 权新有,究9 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 49 索引（indexing）的方法 „ 索引法是顺序存储法的一种推广，它也 使用整数编码来访问数据结点位置 01 2 3 4 5 6 7 数据节点的存储区域 索引表 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 50 back 92 73 37 55 数据库记录 线形索引文件 „ 索引函数Y：ZÆD „ 结点的整数索引值 z∈Z „ 结点的存储地址 d∈D 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 51 倒排文件 Word Postings Document Location abacus 4 3 94 19 7 19 212 22 56 actor 3 2 66 19 213 29 45 aspen 1 5 43 atoll 3 11 3 11 70 34 40 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 52 倒排文件与线性索引 Term Pointer to list of postings ant bee cat dog elk fox gnu hog Inverted lists 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 53 散列（hashing）的方法 „ 散列是索引方法的一种延伸和扩展 „ 更快的检索速度 „ 受数组元素地址计算启发 „ Loc(A[i]) = Loc(A[0]) + i * sizeof(Element); „ 散列函数是将字符串s映射到非负整数z的一类 函数h: S Æ Z ， 对任意的 s∈ S，散列函数 h(s)=z，z∈ Z 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 54 散列（hashing）的方法 „ 散列函数h(s)除了它取非负整数值外，关 键的问题： „ 恰当地选择散列函数 „ 如何建造散列表 „ 在构建散列表的中间解决‘碰撞’的办法