The Anatomy of a Large-Scale Hypertextual Web

wangfans

由索引器和排序器负责建立索引index function。索引器从知识库中读取文档，对其解压缩和分析。每个文档被转换成一组词的出现情况，称作命中hits。Hits纪录了词，词在文档中的位置，最接近的字号，大小写。索引器把这些hits分配到一组桶barrel中，产生经过部分排序后的索引。

wangfans

索引器的另一个重要功能是分析网页中所有的链接，将有关的重要信息存在链接描述anchors文件中。该文件包含了足够的信息，可以用来判断每个链接链出链入节点的信息，和链接文本。 URL分解器resolver阅读链接描述anchors文件，并把相对URL转换成绝对URL，再转换成docID。为链接描述文本编制索引，并与它所 指向的docID关联起来。同时建立由docID对组成的链接数据库。

wangfans

用于计算所有文档的PageRank值。用docID分类后的barrels，送给 排序器sorter，再根据wordID进行分类，建立反向索引inverted index。这个操作要恰到好处，以便几乎不需要暂存空间。排序器还给出docID和偏移量列表，建立反向索引。一个叫DumpLexicon的程序把这 个列表和由索引器产生的字典结合在一起，建立一个新的字典，供搜索器使用。这个搜索器就是利用一个Web服务器，使用由DumpLexicon所生成的字典，利用上述反向索引以及页面等级PageRank来回答用户的提问。

wangfans

4.2  主要数据结构
经过优化的Google数据结构，能够用较小的代价抓取大量文档，建立索引和查询。虽然近几年CPU和输入输出速率迅速提高。磁盘寻道仍然需要10ms。任何时候Google系统的设计都尽可能地避免磁盘寻道。这对数据结构的设计影响很大。

wangfans

4.2.1  大文件
BigFiles是跨越多个文件系统的虚拟文件，用长度是64位的整型数据寻址。多文件系统之间的空间分配是自动完成的。BigFiles包也处理文件描述符的分配。由于操纵系统不能满足我们的需要，BigFiles也支持基本的压缩选项。

wangfans

4.2.2  知识库
知识库包含每个网页的全部HTML。每个网页用zlib（见RFC1950）压缩。 压缩技术的选择既要考虑速度又要考虑压缩率。我们选择zlib的速度而不是压缩率很高的bzip。知识库用bzip的压缩率接近4：1。而用zlib的压 缩率是3：1。文档一个挨着一个的存储在知识库中，前缀是docID，长度，URL，见图2。访问知识库不需要其它的数据结构。这有助于数据一致性和升级。用其它数据结构重构系统，我们只需要修改知识库和crawler错误列表文件。

wangfans

4.2.3 文档索引
文档的索引保持每个文档有关的信息。 它是固定的宽度 ISAM (索引顺序访问模式)索引。每条记录包括当前文件状态，一个指向知识库的指针，文件校验和，各种统计表。如果一个文档已经被抓到，指针指向docinfo文件，该文件的宽度可变，包含了URL和标题。否则指针指向包含这个URL的URL列表。这种设计考虑到简洁的数据结构，以及在查询中只需要一个磁盘寻道时间就能够访问一条记录。

wangfans

还有一个文件用于把URL转换成docID。它是URL校验和与相应docID的列表，并按照校验排序。要想知道某个URL的docID，需要计算URL的校验和，然后在校验和文件中执行二进制查找，找到它的docID。通过对这个文件进行合并，可以把一批URL转换成对应的docID。URL分析器用这项技 术把URL转换成docID。这种成批更新的模式是至关重要的，否则每个链接都需要一次查询，假如用一块磁盘，322百万个链接的数据集合将 花费一个多月的时间。

wangfans

4.2.4 辞典
词典有几种不同的形式。和以前系统的重要改进是，词典对内存的要求可以在合理的价格内。当前实现中，一台256M内存的机器就可以把词典装入到内存中。现在的词典包含14万词汇（虽然一些很少用的词汇没有加入到词典中）。它执行分两部分—词汇表（串联在一起，但使用空值隔开）和指针的哈希表的列表的实现。不同的函数词列表有一些辅助的信息，超出了本文以详细解释的范围。

wangfans

4.2.5点击列表
一个命中列表对应着一个单词在一个文档中出现的位置、字体和大小写信息的列表。命中列表占用了正向索引和反向索引的大部分空间，所以怎样尽可能有效的表示是很重要的。我们考虑了对位置，字体和大小写信息的多种编码方式——简单编码（3个整数），压缩编码（手工优化分配比特）和霍夫曼编码（Huffman coding）。命中（hit）的详情见图3。