常用網(wǎng)絡(luò)搜索引擎如Baidu、Google數(shù)據(jù)

1、.常用網(wǎng)絡(luò)搜索引擎 如 Baidu、Google 數(shù)據(jù)常用網(wǎng)絡(luò)搜索引擎如：Baidu、Google數(shù)據(jù)組織的特點(diǎn)2020-02-28 12：56google搜索原理論文這篇文章中，我們介紹了google，它是一個(gè)大型的搜索引擎of alarge-scale search engine的原型，搜索引擎在超文本中應(yīng)用廣泛。Google的設(shè)計(jì)可以高效地抓網(wǎng)頁并建立索引，它的查詢結(jié)果比其它現(xiàn)有系統(tǒng)都高明。這個(gè)原型的全文和超連接的數(shù)據(jù)庫至少包含24'000'000個(gè)網(wǎng)頁。我們可以從下載。設(shè)計(jì)搜索引擎是一項(xiàng)富有挑戰(zhàn)性的工作。搜索引擎為上億個(gè)網(wǎng)頁建立索引，其中包含大量迥然不同的詞匯。而且每天

2、要答復(fù)成千上萬個(gè)查詢。在網(wǎng)絡(luò)中，盡管大型搜索引擎非常重要，但是學(xué)術(shù)界卻很少研究它。此外由于技術(shù)的快速開展和網(wǎng)頁的大量增加，如今建立一個(gè)搜索引擎和三年前完全不同。本文詳細(xì)介紹了我們的大型搜索引擎，據(jù)我們所知，在公開發(fā)表的論文中，這是第一篇描繪地如此詳細(xì)。除了把傳統(tǒng)數(shù)據(jù)搜索技術(shù)應(yīng)用到如此大量級網(wǎng)頁中所遇到的問題，還有許多新的技術(shù)挑戰(zhàn)，包括應(yīng)用超文本中的附加信息改進(jìn)搜索結(jié)果。本文將解決這個(gè)問題，描繪如何運(yùn)用超文本中的附加信息，建立一個(gè)大型實(shí)用系統(tǒng)。任何人都可以在網(wǎng)上隨意發(fā)布信息，如何有效地處理這些無組織的超文本集合，也是本文要關(guān)注的問題。關(guān)鍵詞World Wide Web，搜索引擎，信息檢索，Pag

3、eRank,Google 1緒論Web給信息檢索帶來了新的挑戰(zhàn)。Web上的信息量快速增長，同時(shí)不斷有毫無經(jīng)歷的新用戶來體驗(yàn)Web這門藝術(shù)。人們喜歡用超級鏈接來網(wǎng)上沖浪，通常都以象Yahoo這樣重要的網(wǎng)頁或搜索引擎開場。大家認(rèn)為List目錄有效地包含了大家感興趣的主題，但是它具有主觀性，建立和維護(hù)的代價(jià)高，晉級慢，不能包括所有深?yuàn)W的主題?；陉P(guān)鍵詞的自動搜索引擎通常返回太多的低質(zhì)量的匹配。使問題更遭的是，一些廣告為了贏得人們的關(guān)注想方設(shè)法誤導(dǎo)自動搜索引擎。我們建立了一個(gè)大型搜索引擎解決了現(xiàn)有系統(tǒng)中的很多問題。應(yīng)用超文本構(gòu)造，大大進(jìn)步了查詢質(zhì)量。我們的系統(tǒng)命名為google，取名自googol的通

4、俗拼法，即10的100次方，這和我們的目的建立一個(gè)大型搜索引擎不謀而合。1.1網(wǎng)絡(luò)搜索引擎-晉級換代scaling up：1994-2000搜索引擎技術(shù)不得不快速晉級scale dramatically跟上成倍增長的web數(shù)量。1994年，第一個(gè)Web搜索引擎，World Wide Web WormWWWW可以檢索到110，000個(gè)網(wǎng)頁和Web的文件。到1994年11月，頂級的搜索引擎聲稱可以檢索到2'000'000WebCrawler至100'000'000個(gè)網(wǎng)絡(luò)文件來自Search Engine Watch?？梢灶A(yù)見到2000年，可檢索到的網(wǎng)頁將超過1

5、9;000'000'000。同時(shí)，搜索引擎的訪問量也會以驚人的速度增長。在1997年的三四月份，World Wide Web Worm平均每天收到1500個(gè)查詢。在1997年11月，Altavista聲稱它每天要處理大約20'000'000個(gè)查詢。隨著網(wǎng)絡(luò)用戶的增長，到2000年，自動搜索引擎每天將處理上億個(gè)查詢。我們系統(tǒng)的設(shè)計(jì)目的要解決許多問題，包括質(zhì)量和可晉級性，引入晉級搜索引擎技術(shù)scaling search engine technology，把它晉級到如此大量的數(shù)據(jù)上。1.2 Google：跟上Web的步伐Scaling with the Web建立一

6、個(gè)可以和當(dāng)今web規(guī)模相適應(yīng)的搜索引擎會面臨許多挑戰(zhàn)。抓網(wǎng)頁技術(shù)必須足夠快，才能跟上網(wǎng)頁變化的速度keep them up to date。存儲索引和文檔的空間必須足夠大。索引系統(tǒng)必須可以有效地處理上千億的數(shù)據(jù)。處理查詢必須快，到達(dá)每秒能處理成百上千個(gè)查詢hundreds to thousands per second.。隨著Web的不斷增長，這些任務(wù)變得越來越艱巨。然而硬件的執(zhí)行效率和本錢也在快速增長，可以部分抵消這些困難。還有幾個(gè)值得注意的因素，如磁盤的尋道時(shí)間disk seek time，操作系統(tǒng)的效率operating system robustness。在設(shè)計(jì)Google的過程中，我

7、們既考慮了Web的增長速度，又考慮了技術(shù)的更新。Google的設(shè)計(jì)可以很好的晉級處理海量數(shù)據(jù)集。它可以有效地利用存儲空間來存儲索引。優(yōu)化的數(shù)據(jù)構(gòu)造可以快速有效地存取參考4.2節(jié)。進(jìn)一步，我們希望，相對于所抓取的文本文件和HTML網(wǎng)頁的數(shù)量而言，存儲和建立索引的代價(jià)盡可能的小參考附錄B。對于象Google這樣的集中式系統(tǒng)，采取這些措施得到了令人滿意的系統(tǒng)可晉級性scaling properties。1.3設(shè)計(jì)目的1.3.1進(jìn)步搜索質(zhì)量我們的主要目的是進(jìn)步Web搜索引擎的質(zhì)量。1994年，有人認(rèn)為建立全搜索索引a complete search index可以使查找任何數(shù)據(jù)都變得容易。根據(jù)Best

8、 of the Web 1994-Navigators，"最好的導(dǎo)航效勞可以使在Web上搜索任何信息都很容易當(dāng)時(shí)所有的數(shù)據(jù)都可以被登錄"。然而1997年的Web就迥然不同。近來搜索引擎的用戶已經(jīng)證實(shí)索引的完好性不是評價(jià)搜索質(zhì)量的唯一標(biāo)準(zhǔn)。用戶感興趣的搜索結(jié)果往往湮沒在"垃圾結(jié)果Junk result"中。實(shí)際上，到1997年11月為止，四大商業(yè)搜索引擎中只有一個(gè)可以找到它自己搜索自己名字時(shí)返回的前十個(gè)結(jié)果中有它自己。導(dǎo)致這一問題的主要原因是文檔的索引數(shù)目增加了好幾個(gè)數(shù)量級，但是用戶可以看的文檔數(shù)卻沒有增加。用戶仍然只希望看前面幾十個(gè)搜索結(jié)果。因此，當(dāng)集合

9、增大時(shí)，我們就需要工具使結(jié)果準(zhǔn)確在返回的前幾十個(gè)結(jié)果中，有關(guān)文檔的數(shù)量。由于是從成千上萬個(gè)有點(diǎn)相關(guān)的文檔中選出幾十個(gè)，實(shí)際上，相關(guān)的概念就是指最好的文檔。高準(zhǔn)確非常重要，甚至以響應(yīng)系統(tǒng)可以返回的有關(guān)文檔的總數(shù)為代價(jià)。令人快樂的是利用超文本鏈接提供的信息有助于改進(jìn)搜索和其它應(yīng)用。尤其是鏈接構(gòu)造和鏈接文本，為相關(guān)性的判斷和高質(zhì)量的過濾提供了大量的信息。Google既利用了鏈接構(gòu)造又用到了anchor文本見2.1和2.2節(jié)。1.3.2搜索引擎的學(xué)術(shù)研究隨著時(shí)間的流逝，除了開展迅速，Web越來越商業(yè)化。1993年，只有1.5%的Web效勞是來自 域名。到1997年，超過了60%。同時(shí)，搜索引擎從學(xué)術(shù)領(lǐng)

10、域走進(jìn)商業(yè)。到如今大多數(shù)搜索引擎被公司所有，很少技公開術(shù)細(xì)節(jié)。這就導(dǎo)致搜索引擎技術(shù)很大程度上仍然是暗箱操作，并傾向做廣告見附錄A。Google的主要目的是推動學(xué)術(shù)領(lǐng)域在此方面的開展，和對它的理解。另一個(gè)設(shè)計(jì)目的是給大家一個(gè)實(shí)用的系統(tǒng)。應(yīng)用對我們來說非常重要，因?yàn)楝F(xiàn)代網(wǎng)絡(luò)系統(tǒng)中存在大量的有用數(shù)據(jù)us because we think some of the most interesting research will involve leveraging the vast amount of usage data that is available from modern web systems

11、。例如，每天有幾千萬個(gè)研究。然而，得到這些數(shù)據(jù)卻非常困難，主要因?yàn)樗鼈儧]有商業(yè)價(jià)值。我們最后的設(shè)計(jì)目的是建立一個(gè)體系構(gòu)造可以支持新的關(guān)于海量Web數(shù)據(jù)的研究。為了支持新研究，Google以壓縮的形式保存了實(shí)際所抓到的文檔。設(shè)計(jì)google的目的之一就是要建立一個(gè)環(huán)境使其他研究者可以很快進(jìn)入這個(gè)領(lǐng)域，處理海量Web數(shù)據(jù)，得到滿意的結(jié)果，而通過其它方法卻很難得到結(jié)果。系統(tǒng)在短時(shí)間內(nèi)被建立起來，已經(jīng)有幾篇論文用到了Google建的數(shù)據(jù)庫，更多的在起步中。我們的另一個(gè)目的是建立一個(gè)宇宙空間實(shí)驗(yàn)室似的環(huán)境，在這里研究者甚至學(xué)生都可以對我們的海量Web數(shù)據(jù)設(shè)計(jì)或做一些實(shí)驗(yàn)。2.系統(tǒng)特點(diǎn)Google搜索引擎

12、有兩個(gè)重要特點(diǎn)，有助于得到高精度的搜索結(jié)果。第一點(diǎn)，應(yīng)用Web的鏈接構(gòu)造計(jì)算每個(gè)網(wǎng)頁的Rank值，稱為PageRank，將在98頁詳細(xì)描繪它。第二點(diǎn)，Google利用超鏈接改進(jìn)搜索結(jié)果。2.1 PageRank：給網(wǎng)頁排序Web的引用鏈接圖是重要的資源，卻被當(dāng)今的搜索引擎很大程度上無視了。我們建立了一個(gè)包含518'000'000個(gè)超鏈接的圖，它是一個(gè)具有重要意義的樣本。這些圖可以快速地計(jì)算網(wǎng)頁的PageRank值，它是一個(gè)客觀的標(biāo)準(zhǔn)，較好的符合人們心目中對一個(gè)網(wǎng)頁重要程度的評價(jià)，建立的根底是通過引用判斷重要性。因此在web中，PageRank可以優(yōu)化關(guān)鍵詞查詢的結(jié)果。對于大多數(shù)

13、的主題，在網(wǎng)頁標(biāo)題查詢中用PageRank優(yōu)化簡單文本匹配，我們得到了令人驚嘆的結(jié)果從可以得到演示。對于Google主系統(tǒng)中的全文搜索，PageRank也幫了不少忙。2.1.1計(jì)算PageRank文獻(xiàn)檢索中的引用理論用到Web中，引用網(wǎng)頁的鏈接數(shù)，一定程度上反映了該網(wǎng)頁的重要性和質(zhì)量。PageRank開展了這種思想，網(wǎng)頁間的鏈接是不平等的。PageRank定義如下：我們假設(shè)T1Tn指向網(wǎng)頁A例如，被引用。參數(shù)d是制動因子，使結(jié)果在0，1之間。通常d等于0.85。在下一節(jié)將詳細(xì)介紹d。CA定義為網(wǎng)頁A指向其它網(wǎng)頁的鏈接數(shù)，網(wǎng)頁A的PageRank值由下式給出

14、：PRA=1-d+dPRT1/CT1+.+PRTn/CTn注意PageRank的形式，分布到各個(gè)網(wǎng)頁中，因此所有網(wǎng)頁的PageRank和是1。PageRank或PRA可以用簡單的迭代算法計(jì)算，相應(yīng)規(guī)格化Web鏈接矩陣的主特征向量。中等規(guī)模的網(wǎng)站計(jì)算26'000'000網(wǎng)頁的PageRank值要花費(fèi)幾小時(shí)。還有一些技術(shù)細(xì)節(jié)超出了本文闡述的范圍。2.1.2直覺判斷PageRank被看作用戶行為的模型。我們假設(shè)網(wǎng)上沖浪是隨機(jī)的，不斷點(diǎn)擊鏈接，從不返回，最終煩了，另外隨機(jī)選一個(gè)網(wǎng)頁重新開場沖浪。隨機(jī)訪問一個(gè)網(wǎng)頁的可能性就是它的PageRank值。制動因子d是隨機(jī)訪問一個(gè)網(wǎng)頁煩了的可能性

15、，隨機(jī)另選一個(gè)網(wǎng)頁。對單個(gè)網(wǎng)頁或一組網(wǎng)頁，一個(gè)重要的變量參加到制動因子d中。這允許個(gè)人可以成心地誤導(dǎo)系統(tǒng)，以得到較高的PageRank值。我們還有其它的PageRank算法，見98頁。另外的直覺判斷是一個(gè)網(wǎng)頁有很多網(wǎng)頁指向它，或者一些PageRank值高的網(wǎng)頁指向它，那么這個(gè)網(wǎng)頁很重要。直覺地，在Web中，一個(gè)網(wǎng)頁被很多網(wǎng)頁引用，那么這個(gè)網(wǎng)頁值得一看。一個(gè)網(wǎng)頁被象Yahoo這樣重要的主頁引用即使一次，也值得一看。假設(shè)一個(gè)網(wǎng)頁的質(zhì)量不高，或者是死鏈接，象Yahoo這樣的主頁不會鏈向它。PageRank處理了這兩方面因素，并通過網(wǎng)絡(luò)鏈接遞歸地傳遞。&nbsp；2.2鏈接描繪文字Anchor

16、 Text我們的搜索引擎對鏈接文本進(jìn)展了特殊的處理。大多數(shù)搜索引擎把鏈接文字和它所鏈向的網(wǎng)頁the page that the link is on聯(lián)絡(luò)起來。另外，把它和鏈接所指向的網(wǎng)頁聯(lián)絡(luò)起來。這有幾點(diǎn)好處。第一，通常鏈接描繪文字比網(wǎng)頁本身更準(zhǔn)確地描繪該網(wǎng)頁。第二，鏈接描繪文字可能鏈向的文檔不能被文本搜索引擎檢索到，例如圖像，程序和數(shù)據(jù)庫。有可能使返回的網(wǎng)頁不能被抓到。注意哪些抓不到的網(wǎng)頁將會帶來一些問題。在返回給用戶前檢測不了它們的有效性。這種情況搜索引擎可能返回一個(gè)根本不存在的網(wǎng)頁，但是有超級鏈接指向它。然而這種結(jié)果可以被挑出來的，所以此類的問題很少發(fā)生。鏈接描繪文字是對被鏈向網(wǎng)頁的宣傳

17、，這個(gè)思想被用在World Wide Web Worm中，主要因?yàn)樗兄谒阉鞣俏谋拘畔ⅲ梢杂蒙倭康囊严螺d文檔擴(kuò)大搜索范圍。我們大量應(yīng)用鏈接描繪文字，因?yàn)樗兄谶M(jìn)步搜索結(jié)果的質(zhì)量。有效地利用鏈接描繪文字技術(shù)上存在一些困難，因?yàn)楸仨毺幚泶罅康臄?shù)據(jù)。如今我們能抓到24'000'000個(gè)網(wǎng)頁，已經(jīng)檢索到259'000'000多個(gè)鏈接描繪文字。2.3其它特點(diǎn)除了PageRank和應(yīng)用鏈接描繪文字外，Google還有一些其它特點(diǎn)。第一,所有hit都有位置信息，所以它可以在搜索中廣泛應(yīng)用鄰近性proximity。第二，Google跟蹤一些可視化外表細(xì)節(jié)，例如字號。黑體大

18、號字比其它文字更重要。第三，知識庫存儲了原始的全文html網(wǎng)頁。3有關(guān)工作Web檢索研究的歷史簡短。World Wide Web Worm是最早的搜索引擎之一。后來出現(xiàn)了一些用于學(xué)術(shù)研究的搜索引擎，如今它們中的大多數(shù)被上市公司擁有。與Web的增長和搜索引擎的重要性相比，有關(guān)當(dāng)今搜索引擎技術(shù)的優(yōu)秀論文相當(dāng)少。根據(jù)Michael MauldinLycos Inc的首席科學(xué)家，"各種各樣的效勞包括Lycos非常關(guān)注這些數(shù)據(jù)庫的細(xì)節(jié)。"雖然在搜索引擎的某些特點(diǎn)上做了大量工作。具有代表性的工作有，對現(xiàn)有商業(yè)搜索引擎的結(jié)果進(jìn)展傳遞，或建立小型的個(gè)性化的搜索引擎。最后有關(guān)信息檢索系統(tǒng)的研

19、究很多，尤其在有組織機(jī)構(gòu)集合well controlled collections方面。在下面兩節(jié)，我們將討論在信息檢索系統(tǒng)中的哪些領(lǐng)域需要改進(jìn)以便更好的工作在Web上。3.1信息檢索信息檢索系統(tǒng)誕生在幾年前，并開展迅速。然而大多數(shù)信息檢索系統(tǒng)研究的對象是小規(guī)模的單一的有組織構(gòu)造的集合，例如科學(xué)論文集，或相關(guān)主題的新聞故事。實(shí)際上，信息檢索的主要基準(zhǔn)，the Text Retrieval Conference，用小規(guī)模的、有組織構(gòu)造的集合作為它們的基準(zhǔn)。大型文集基準(zhǔn)只有20GB，相比之下，我們抓到的24000000個(gè)網(wǎng)頁占147GB。在TREC上工作良好的系統(tǒng)，在Web上卻不一定產(chǎn)生好的結(jié)果。

20、例如，標(biāo)準(zhǔn)向量空間模型企圖返回和查詢懇求最相近的文檔，把查詢懇求和文檔都看作由出如今它們中的詞匯組成的向量。在Web環(huán)境下，這種策略常常返回非常短的文檔，這些文檔往往是查詢詞再加幾個(gè)字。例如，查詢"Bill Clinton"，返回的網(wǎng)頁只包含"Bill Clinton Sucks"，這是我們從一個(gè)主要搜索引擎中看到的。網(wǎng)絡(luò)上有些爭議，用戶應(yīng)該更準(zhǔn)確地表達(dá)他們想查詢什么，在他們的查詢懇求中用更多的詞。我們強(qiáng)烈反對這種觀點(diǎn)。假設(shè)用戶提出象"Bill Clinton"這樣的查詢懇求，應(yīng)該得到理想的查詢結(jié)果，因?yàn)檫@個(gè)主題有許多高質(zhì)量的信息。象

21、所給的例子，我們認(rèn)為信息檢索標(biāo)準(zhǔn)需要開展，以便有效地處理Web數(shù)據(jù)。3.2有組織構(gòu)造的集合Well Controlled Collections與Web的不同點(diǎn)Web是完全無組織的異構(gòu)的大量文檔的集合。Web中的文檔無論內(nèi)在信息還是隱含信息都存在大量的異構(gòu)性。例如，文檔內(nèi)部就用了不同的語言既有人類語言又有程序，詞匯email地址，鏈接，郵政編碼， 號碼，產(chǎn)品號，類型文本，HTML，PDF，圖像，聲音，有些甚至是機(jī)器創(chuàng)立的文件log文件，或數(shù)據(jù)庫的輸出?？梢詮奈臋n中推斷出來，但并不包含在文檔中的信息稱為隱含信息。隱含信息包括來源的信譽(yù)，更新頻率，質(zhì)量，訪問量和引用。不但隱含信息的可能來源各種各樣

22、，而且被檢測的信息也大不一樣，相差可達(dá)好幾個(gè)數(shù)量級。例如，一個(gè)重要主頁的使用量，象Yahoo每天閱讀數(shù)到達(dá)上百萬次，于此相比無名的歷史文章可能十年才被訪問一次。很明顯，搜索引擎對這兩類信息的處理是不同的。Web與有組織構(gòu)造集合之間的另外一個(gè)明顯區(qū)別是，事實(shí)上，向Web上傳信息沒有任何限制。靈敏利用這點(diǎn)可以發(fā)布任何對搜索引擎影響重大的信息，使路由阻塞，加上為牟利成心操縱搜索引擎，這些已經(jīng)成為一個(gè)嚴(yán)重的問題。這些問題還沒有被傳統(tǒng)的封閉的信息檢索系統(tǒng)所提出來。它關(guān)心的是元數(shù)據(jù)的努力，這在Web搜索引擎中卻不適用，因?yàn)榫W(wǎng)頁中的任何文本都不會向用戶聲稱企圖操縱搜索引擎。甚至有些公司為牟利專門操縱搜索引擎

23、。4系統(tǒng)分析System Anatomy首先，我們提供高程度的有關(guān)體系構(gòu)造的討論。然后，詳細(xì)描繪重要的數(shù)據(jù)構(gòu)造。最后，主要應(yīng)用：抓網(wǎng)頁，索引，搜索將被嚴(yán)格地檢查。Figure 1.High Level Google Architecture 4.1Google體系構(gòu)造概述這一節(jié)，我們將看看整個(gè)系統(tǒng)是如何工作的give ahigh level，見圖1。本節(jié)不討論應(yīng)用和數(shù)據(jù)構(gòu)造，在后幾節(jié)中討論。為了效率大部分Google是用c或c+實(shí)現(xiàn)的，既可以在Solaris也可以在Linux上運(yùn)行。Google系統(tǒng)中，抓網(wǎng)頁下載網(wǎng)頁是由幾個(gè)分布式crawlers完成的。一個(gè)URL效勞器負(fù)責(zé)向crawlers提

24、供URL列表。抓來的網(wǎng)頁交給存儲效勞器storeserver。然后，由存儲效勞器壓縮網(wǎng)頁并把它們存到知識庫repository中。每個(gè)網(wǎng)頁都有一個(gè)ID，稱作docID，當(dāng)新URL從網(wǎng)頁中分析出時(shí)，就被分配一個(gè)docID。由索引器和排序器負(fù)責(zé)建立索引index function。索引器從知識庫中讀取文檔，對其解壓縮和分析。每個(gè)文檔被轉(zhuǎn)換成一組詞的出現(xiàn)情況，稱作命中hits。Hits紀(jì)錄了詞，詞在文檔中的位置，最接近的字號，大小寫。索引器把這些hits分配到一組桶barrel中，產(chǎn)生經(jīng)過部分排序后的索引。索引器的另一個(gè)重要功能是分析網(wǎng)頁中所有的鏈接，將有關(guān)的重要信息存在鏈接描繪anchors文件中

25、。該文件包含了足夠的信息，可以用來判斷每個(gè)鏈接鏈出鏈入節(jié)點(diǎn)的信息，和鏈接文本。URL分解器resolver閱讀鏈接描繪anchors文件，并把相對URL轉(zhuǎn)換成絕對URL，再轉(zhuǎn)換成docID。為鏈接描繪文本編制索引，并與它所指向的docID關(guān)聯(lián)起來。同時(shí)建立由docID對組成的鏈接數(shù)據(jù)庫。用于計(jì)算所有文檔的PageRank值。用docID分類后的barrels，送給排序器sorter，再根據(jù)wordID進(jìn)展分類，建立反向索引inverted index。這個(gè)操作要恰到好處，以便幾乎不需要暫存空間。排序器還給出docID和偏移量列表，建立反向索引。一個(gè)叫DumpLexicon的程序把這個(gè)列表和由索

26、引器產(chǎn)生的字典結(jié)合在一起，建立一個(gè)新的字典，供搜索器使用。這個(gè)搜索器就是利用一個(gè)Web效勞器，使用由DumpLexicon所生成的字典，利用上述反向索引以及頁面等級PageRank來答復(fù)用戶的提問。4.2主要數(shù)據(jù)構(gòu)造經(jīng)過優(yōu)化的Google數(shù)據(jù)構(gòu)造，可以用較小的代價(jià)抓取大量文檔，建立索引和查詢。雖然近幾年CPU和輸入輸出速率迅速進(jìn)步。磁盤尋道仍然需要10ms。任何時(shí)候Google系統(tǒng)的設(shè)計(jì)都盡可能地防止磁盤尋道。這對數(shù)據(jù)構(gòu)造的設(shè)計(jì)影響很大。4.2.1大文件大文件BigFiles是指虛擬文件生成的多文件系統(tǒng)，用長度是64位的整型數(shù)據(jù)尋址。多文件系統(tǒng)之間的空間分配是自動完成的。BigFiles包也處

27、理已分配和未分配文件描繪符。由于操縱系統(tǒng)不能滿足我們的需要，BigFiles也支持根本的壓縮選項(xiàng)。4.2.2知識庫Figure 2.Repository Data Structure知識庫包含每個(gè)網(wǎng)頁的全部HTML。每個(gè)網(wǎng)頁用zlib見RFC1950壓縮。壓縮技術(shù)的選擇既要考慮速度又要考慮壓縮率。我們選擇zlib的速度而不是壓縮率很高的bzip。知識庫用bzip的壓縮率接近4：1。而用zlib的壓縮率是3：1。文檔一個(gè)挨著一個(gè)的存儲在知識庫中，前綴是docID，長度，URL，見圖2。訪問知識庫不需要其它的數(shù)據(jù)構(gòu)造。這有助于數(shù)據(jù)一致性和晉級。用其它數(shù)據(jù)構(gòu)造重構(gòu)系統(tǒng)，我們只需要修改知識庫和craw

28、ler錯(cuò)誤列表文件。4.2.3文件索引文件索引保存了有關(guān)文檔的一些信息。索引以docID的順序排列，定寬ISAMIndex sequential access mode。每條記錄包括當(dāng)前文件狀態(tài)，一個(gè)指向知識庫的指針，文件校驗(yàn)和，各種統(tǒng)計(jì)表。假設(shè)一個(gè)文檔已經(jīng)被抓到，指針指向docinfo文件，該文件的寬度可變，包含了URL和標(biāo)題。否那么指針指向包含這個(gè)URL的URL列表。這種設(shè)計(jì)考慮到簡潔的數(shù)據(jù)構(gòu)造，以及在查詢中只需要一個(gè)磁盤尋道時(shí)間就可以訪問一條記錄。還有一個(gè)文件用于把URL轉(zhuǎn)換成docID。它是URL校驗(yàn)和與相應(yīng)docID的列表，按校驗(yàn)和排序。要想知道某個(gè)URL的docID，需要計(jì)算URL