1031基于属性的倒 0I97.0204 ■对某属性按属性值建立索引表,称倒排 0375,0552 (attr, ptrList) 020A4 记录指骨可以是类健码,或该记录的主文件地址 颠摄主文件的顺序,因而称为倒排索引 ■属性往往是高散型的 0375.0552 对于连续型的索引,往往用B树 倒排文件:带有倒排索引的文件 张陪写 新。■印乡究 北京太 孔稳写 权新有轴命剑究 检索实例 玩具部中年齡在50岁以上或者工资在 ■优点:能够对于基于属性的检索 GE≥50oR ≥500 进行较高效率的处理 分型找 缺点: 对后两个丰 花费了保存倒排表的存储代价 降低了更新运算的效率 张铭帖编写 孔写 1032对正文文件的倒排 词索引 正文索引〔 Text Indexing处理 ■基本思想: 的就是“建立一个数据结构以提 把正文看作由符号和词所组成的集合,从正 后 供对文本内容的快速检索”。 些适合快速检索的数据结构。 方法 适用于多种文本类型,特别是那些可以 很容易就解析成一组词的集合的文本 词索引( word index) 适用于英文 全文索引fu- text index) ■中文等东方文字要经过“切词”处理 北京大息学 张铭 政■印究 张帖写6 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 31 10.3.1 基于属性的倒排 „ 对某属性按属性值建立索引表，称倒排 表 „ (attr, ptrList) „ （属性值，具有该属性值的各记录指针） „ 记录指针可以是关键码，或该记录的主文件地址 „ 颠覆主文件的顺序，因而称为倒排索引 „ 属性往往是离散型的 „ 对于连续型的索引，往往用B树 „ 倒排文件：带有倒排索引的文件 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 32 0375, 0552 0197 0204, 0673 0100, 0193 0172, 0201, 0221 2500 3000 3500 4000 5000 SAL list EMP# 0197, 0375, 0552 0100 0193, 0204 0673 0172 0221 0201 26 32 39 40 43 47 55 AGE list EMP# 0100, 0221, 0552 0172, 0201 0193, 0197, 0204 0375, 0673 玩具部 食品部 服装部 电器部 DEPT list EMP# 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 33 检索实例 列出玩具部中年龄在50岁以上或者工资在 5000元以上的职工记录 (DEPT=“Toy”AND(AGE≥50 OR SAL≥5000))。 分别找出满足条件DEPT=“Toy”， AGE≥50，和SAL≥5000的指针集合，然后 对后两个指针集合求并，并且将结果集合与第 一个指针集合求交，最后的结果集合中包含的 指针所指的各记录即为所求。 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 34 „ 优点：能够对于基于属性的检索 进行较高效率的处理 „ 缺点： „ 花费了保存倒排表的存储代价 „ 降低了更新运算的效率 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 35 10.3.2 对正文文件的倒排 „ 正文索引(Text Indexing)处理 的就是“建立一个数据结构以提 供对文本内容的快速检索”。 „ 方法 „ 词索引(word index) „ 全文索引(full-text index) 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 36 词索引 „ 基本思想： „ 把正文看作由符号和词所组成的集合，从正 文中抽取出关键词，然后用这些关键词组成 一些适合快速检索的数据结构。 „ 适用于多种文本类型，特别是那些可以 很容易就解析成一组词的集合的文本 „ 适用于英文 „ 中文等东方文字要经过“切词”处理