对关键词的检索 ■3.建立正文倒排表、倒排文件 ■第一步,在倒排文件中检索关键词 得到各个关键词的集合 步,如果找到了关键词,那么获 倒排表,并获取倒排 对于每一个关键词得到其倒排表 然后把所有的倒排表存入文件 记录在每个倒排表在索引文件中开 筹集阻表建霜菱麴字典)进 始的位置以及每个表的大小(也可 以记录每个关键词的出现次数) 散列 张陪写 新。■印乡究 北京太 孔稳写 权新有轴命剑究 倒排文件优劣 104动态索引 高效检索,用于文本数据库系统 ①基本概念 ■支持的检索类型有限 Q1041B树 检索词有限 Q10.4.2B树 只能用索引文件中的关键词 10.4.3ⅤsSAM 倒排文件中的索引效率可能不高 044B树的性能分析 需要的空间代价往往很高 张铭帖编写 孔写 基本概念 104.1B树 ■动态索引结构 种平衡的多分树( Balanced tre 索引结构本身也可能发生改变 3阶B树 在系统运行过程中插入或删除记录时 2-3树 ■目的 保持较好的性能 例如较高的检索效率 [2023,[44[50s1 北京大息学 张铭 权质有,印究 张帖写 权新有:命些8 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 43 „ 3. 建立正文倒排表、倒排文件 „ 得到各个关键词的集合 „ 对于每一个关键词得到其倒排表 „ 然后把所有的倒排表存入文件 „ 记录在每个倒排表在索引文件中开 始的位置以及每个表的大小（也可 以记录每个关键词的出现次数） 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 44 对关键词的检索 „ 第一步，在倒排文件中检索关键词 „ 第二步，如果找到了关键词，那么获取 文件中的对应的倒排表，并获取倒排表 中的记录 „ 通常使用另一个索引结构（字典）进一 步对关键词表进行有效索引 „ Trie „ 散列 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 45 倒排文件优劣 „ 高效检索，用于文本数据库系统 „ 支持的检索类型有限 „ 检索词有限 „ 只能用索引文件中的关键词 „ 倒排文件中的索引效率可能不高 „ 需要的空间代价往往很高 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 46 10.4 动态索引 „ 基本概念 „ 10.4.1 B树 „ 10.4.2 B+树 „ 10.4.3 VSAM „ 10.4.4 B树的性能分析 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 47 基本概念 „ 动态索引结构 „ 索引结构本身也可能发生改变 „ 在系统运行过程中插入或删除记录时 „ 目的 „ 保持较好的性能 „ 例如较高的检索效率 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 48 10.4.1 B树 „ 一种平衡的多分树 (Balanced Tree) 18 33 12 23 30 48 10 15 20 21 24 31 45 47 50 52 3阶B树 2-3树