[技术文章]搜索引擎试验之一

<>文章较长，请耐心阅读！</P>
On Bots（中文翻译）




<>May 16th, 2006 mimiqiao--&gt;</P>
<>原文链接：http://drunkmenworkhere.org/219.php
中文翻译：benhur</P>
<>持续修正中……欢迎多提意见！</P>
ContentsIntroduction
Setup
Overall results
Yahoo! Slurp
Googlebot
MSNbot
Spam bots Introduction




<>关于搜索引擎的大规模试验在持续了一年之后于2006-4-13结束。该试验的目的是分析搜索引擎行为模式，共使用了基于二叉查找树结构- Binary Search Tree 2 -而组织的20亿页面。在一年的时间内，三个主要搜索引擎向超过十万个不同的URL提交了超过一百万次页面请求。由于显示在页面上的访问记录和留言的增长，drunkmenworkhere.org的主页也从最初的1.6kB增长到了4MB。</P>
<>本文即为这次试验的结果。</P>
<>^</P>
Setup




<>这次试验共准备了2,147,483,647个页面，这些页面(结点)以二叉查找树的结构组织在一起。对于某一特定结点来说，它自身的值大于其左子树上任意一结点的值，而小于右子树上任意一结点的值。在这次试验中，最左叶结点的值为1，而最右叶结点的值为2,147,483,647。</P>
<>二叉树的深度是指从根结点访问到最远的叶结点所经历的结点数量。如果二叉树的深度是n，那在这棵二叉树上最多能排列2n+1个结点。在本次试验中，二叉树的深度定为30(231= 2,147,483,648)，所以根结点的值为1073741824(230)。在持续一年的时间里(从2005-4-13到2006-4-13)，我们跟踪了三大搜索机器人(Yahoo!Slurp、Googlebot和msnbot)在每个页面上的访问量。</P>
<>为了让搜索引擎对页面内容更感兴趣，每个结点的值都用short scale(短级差制英语表示，billion=“十亿”，译者注)表示，每一次搜索机器人对于任意结点的访问记录都会按时间排序显示在该结点的页面上。每个页面上添加了一个留言板(已于被2006-4-13被移除)。上一版二叉查找树结构- Binary Search Tree - 因为使用了长URL而造成不便，现在这些措施都是对其的进一步改进。</P>
<P>每个结点上首先显示了三张访问树图。这是被搜索引擎抓取的结点的图形化表示。图中的每条线代表一个结点，线的长度代表搜索机器人的访问次数。下文中所使用的图片是访问树全图的修改版，除去了拥有最大访问量的根结点，但没有连接到根结点的树枝仍会被表示。</P>
<P>^</P>
Overall results




<P>到目前为止，Yahoo! Slurp是最活跃的搜索机器人。在一年时间里总共请求了超过一百万次页面，抓取了超过十万个不同的结点。这是一个很大的数字，但也只占了总结点数的0.0049%。所有机器人的统计数据如下：</P>
<P>
overall statistics by search engineYahoo!</P>

Google

MSNtotal number of pageviews
(页面总请求数)1,030,39620,6334,699number of nodes crawled
(抓取结点数)105,9717,5561,390percentage of tree crawled
(抓取率)0.0049%0.00035%0.000065%number of indexed nodes
(索引结点数)120,0005541indexed/crawled ratio
(索引/抓取比)113.23%7.33%0.07%





<P>页面总请求数和抓取结点总数在一年内的增长趋势如图1和图2所示。在随后几节中将具体分析搜索机器人抓取结点的方式(配有动画演示)。
</P>
<P><B>Fig. 1</B> - The cumulative number of pageviews by the search bots in time.</P>
<P><B>Fig. 2</B> - The cumulative number of nodes crawled by the search bots in time.</P>
<P>图3中显示了二叉树中的不同层结点被抓取的数据统计(注：纵轴为对数表示)。根结点在level 0，最远叶结点(如结点1)在level 30。二叉树的结构决定了在第n层有2n个结点，所以从理论上说，搜索机器人抓取整个二叉树的行为会在图中表示为一条单调上升的直线。</P>
<P><B>Fig. 3</B> - The number of nodes crawled after 1 year, grouped by node level.</P>
<P>Googlebot的抓取模式基本上接近于这条直线，直到在第12级发生转折。它所抓取的大多数结点在第12层或12层以下(8191中的5524个)，少有深层的结点被抓取。MSNbot的行为模式与Googlebot类似但拐点出现得更早，在第9级(1023中的656个)。Yahoo没有发生明显的转折，不过在深层抓取新结点的行为逐渐放缓。</P>
<P>与其他搜索机器人相比，Yahoo更频繁地向其所抓取的深层结点发送请求：在14层到30层的结点平均请求次数为10次。(见图4)</P>
<P><B>Fig. 4</B> - The average number of pageviews per node after 1 year, grouped by node level.</P>
<P>^</P>


Yahoo! Slurp




<P>
<P>
large version (4273×3090, 1.5MB)
animated version over 1 year (2005-04-13 - 2006-04-13, 13MB)
animated version of the first 2 hours (2006-04-14 00:40:00-02:40:00, 2.2MB) </P>
<P><B>Fig. 5</B> - The Yahoo! Slurp tree.</P>
<P>Yahoo! Slurp是第一个发现Binary Search Tree 2的引擎。在其后的几个小时里Yahoo! Slurp每秒2.3个结点(见动画演示(2 hours ))的速度精力旺盛地抓取着每一个结点。到第一天结束它已经抓取了大约30,000个结点。</P>
<P>在接下来的一个月里Slurp表现得没有第一天那么活跃，但一个月以后它重新请求了它先前访问的每一页。在动画演示中可以看到：访问树在2005-05-14增长了一倍。这一现象在一个月后再次重复：在2005-06-13访问树增长到原来规模的三倍。Yahoo! Slurp在请求数已经达到90,000时抓取的结点数仍然维持在30,000。图6显示了在最初几个月里请求数的阶梯式增长。
</P>
<P><B>Fig. 6</B> - The cumulative number of pageviews by Yahoo! Slurp in time.</P>
<P>4个月后，Slurp重复了其第一回合的行为，请求了大量的“新”结点。它请求了所有访问过的结点。因为已经建立了30000个结点的索引而每一个结点都链接到更深一层的两个子结点，在8月底它请求了60000个页面(请求数由100,000跳到160,000，见图6)，同时抓取页面总数也翻了一番。(见图7)</P>
<P>5个月后Yahoo! Slurp开始显得更有规律发送请求，从图7中上仍然可以看到新的“发现期”(例：10个月以后)。
</P>
<P><B>Fig. 7</B> - The cumulative number of nodes crawled by Yahoo! Slurp in time.</P>
<P>Yahoo在索引中报告了120,000个页面(current value)。考虑到它只访问了105,971 个结点，这看起来有点不可思议，但实际上每个结点都有两个域名：www.drunkmenworkhere.org和drunkmenworkhere.org</P>
<P>Note: 从返回的查询结果上看，Google和MSN与Yahoo的35,600条记录相比明显落于下风。截止到试验结束为止，Yahoo是唯一一个对上述查询返回结果的搜索引擎。</P>
<P>^未完待续...</P>

<b>[技术文章]搜索引擎试验之一</b>

<b>[技术文章]搜索引擎试验之一</b>

<b>[技术文章]搜索引擎试验之一</b>

[此贴子已经被作者于2006-7-1 12:05:18编辑过]