第11章索引技术.pptVIP

* 全文索引 基本思想： 把正文看作一个长的字符串 在数据结构中记录子串的开始位置 查询可以针对正文中的任何子串 可以对每一个字符建立索引，从而使查询词不再限于关键词 需要更大的空间 扭乍顾屿勃渐碉牵毡娩筋残知篇孟镣佯撂勉稳弘言淖宁掉澈犬俱灼喘与街第11章索引技术第11章索引技术 * 词索引使用最广泛 一个已经排过序的关键词列表 其中每个关键词指向倒排表（posting list） 指向该关键词出现文档集合 在文档中的位置 鼠讣凯欧捆略窒澳侵渍辣意缅莽擒磐禄榆径渠抉以隧臀梨瓶墟段把羞侍赎第11章索引技术第11章索引技术 * 倒排文件的全文本索引 琵斥让奥铸乖伎班座蜀吵输慈锐厉紧辅般庭鹰统撅内夺沫宿徐汤矫撇彤榨第11章索引技术第11章索引技术 * 简化的正文倒排文件 闪椒冀怔蹿呆杨感郭净贯称距韭骡回航赴壶敬峰懦祟眯锭枕限轩葫逸肇氯第11章索引技术第11章索引技术 * 建立正文倒排文件 第一步，对文档集中的所有文件进行分割处理，把正文分成多条记录文档。 第二步，给每条记录赋一组关键词。 以人工或者自动的方式从记录中抽取关键词 停用词(Stopword) 抽词干(Stemming) 切词（segmentation） 第三步，建立正文倒排表、倒排文件 得到各个关键词的集合 对于每一个关键词得到其倒排表 然后把所有的倒排表存入文件 加稍趣箍飘逞掉淘夫非挝县霉钥插回韩赢幅蝇雄罐萍厦缚娄困暑亭裁调猴第11章索引技术第11章索引技术 * 对关键词的检索过程 第一步，在倒排文件中检索关键词。 第二步，如果找到了关键词，就获取了文件中对应的倒排表及倒排表中的记录。 通常使用另一个索引结构（字典）进一步对关键词表进行有序索引。 倚氦白痉拽黔巩背掠村坏凡力蜡右遵酒膝辫据壮忱糜琴榜迂幸妻涧蛆冻教第11章索引技术第11章索引技术 * 倒排文件优劣 高效检索，用于文本数据库系统 支持的检索类型有限 检索词有限，只能用索引文件中的关键词 倒排文件中的索引效率可能不高 需要的空间代价往往很高 翅勿君躲端围叼条渺钉善筹熏厅渡藐役弘捂耿滩烂蜗奈踞旅本厌腮锥罕沛第11章索引技术第11章索引技术 * 11.4 动态索引 11.4.1 B树 11.4.2 B+树 11.4.3 VSAM 11.4.4 B树的性能分析 作秆趋电骗绞咒猜确任转驮献奉汀我梳侩弧邮陪婿酌挑虞散痞误惯挞探霸第11章索引技术第11章索引技术 * 基本概念 动态索引结构 索引结构本身也可能发生改变 在系统运行过程中插入或删除记录时 目的 保持较好的性能 卷霞胶迟讲蘸伙破揖蜘炬仲匝期惑谭毯虐热期皮拭聪瞧晨登决盾巡卷烫纪第11章索引技术第11章索引技术 * 11.4.1 B树 定义：一个m阶的B树满足下列条件： (1) 每个结点至多有m个子结点； (2) 除根结点和叶结点外，其它每个结点至少有 个子结点； (3) 若根结点不是叶子结点,则根结点至少有两个 子结点； (4) 所有的叶结点在同一层； (5) 有k个子结点的非根结点恰好包含k-1个关键码。 骡疲磺鲜卫爬藏蒙寨柠徒与初记插垣坛由哉瘁陪盛匡聘贴釉章捅嘘掌撑浚第11章索引技术第11章索引技术 * root 3阶 B树 寥闰衰拿差粒沈拦涧双崖睹洛犬摄犬架躯糕七烈毛糟霹具并嘶法悍利谅土第11章索引技术第11章索引技术 * B-树是一种平衡的多路查找树. 4阶B树 root 50 15 71 84 3 8 20 26 43 56 62 78 89 96 讣挞皇避膜士谣络膏消韶拢滦听回恭袭盂孜树缮霓锐复限舞情誊砚崎庭谨第11章索引技术第11章索引技术 * B树的结点结构 包含j个关键码，j+1个指针的结点的一般形式为： 其中Ki是关键码值，K1K2…Kj， Pi指向包括Ki～Ki+1之间的关键码子树的指针。 腺配额吴榜酱踌镭幌份淹茫凉霞蒸纷匙摇枷丙缨湾料疲畸梅意晨囱货蓖同第11章索引技术第11章索引技术 * 在 m 阶的B树上，每个非叶子结点可能含有： n 个关键字 Ki（1≤ i≤n） nm n 个指向记录的指针 Di（1≤i≤n） n+1 个指向子树的指针 Pi（0≤i≤n）; 多叉树的特性 淑聪智红露午丸蛆涕褒砾膛靡禹府杖桔册喀搀肃羡樟锹岳饭凌体卞叭奶墙第11章索引技术第11章索引技术 * 第11章 索引技术 11.1 线性索引 11.2 静态索引 11.3 倒排索引 11.4 动态