文档介绍：付宁
搜索引擎索引简介
什么是索引?
起源:文献系统
计算机领域:数据库索引
搜索引擎领域:网页索引
数据索引+并行计算+计算机网络
分布式索引
数据库索引
结构:线性表索引、散列索引、树形索引
数据分派:划分、安排、二次分派
并行查询:分发、汇总
其他、、、
分布式索引处理框架
搜索引擎工作原理
web
网络爬虫
页面存储库
索引器
用户接口
输入分析器
排序器
搜索器
索引库
抓取网页
索引建立过程
网页内容提取与分析
文档索引
排序
关键词:过滤
关键词:标记
关键词:倒排
索引组织结构
正排索引
网页1
Word1
Word2
。。。
网页2
Word1
Word2
。。。
。。。
索引组织结构
倒排索引
Word1
网页1
网页2
。。。
Word2
网页1
网页2
。。。
。。。
倒排索引文件结构
字或词
逻辑记录指针集合
词1
4
词2
2
。。。
。。。
倒排索引文件结构
逻辑记录号
在主文件中的地址(指针)
1
4
2
9
。。。
。。。
文档
文件1
文件2
。。。
地址对照文件
倒排索引文件
主文件
索引合并
归并算法
普通归并 O(M+N)
跳跃比较O(M+N/k) O(M+2*N)
Skip List O(M+N/k) O(M+N+N/k)
bitmap O(M+N)
索引压缩
前提:增序差分存储(Delta编码)
固定长度压缩方法
数值范围头两个bit   压缩大小 0-63       00         1byte 64-16k     01         2byte 16k-4M     10         3byte 4M-1G      11         4byte
存储前
1 50 53 58 100 2000 2005 2007 2009
存储后
1 49 3 5 42 1900 5 2 2