http://s.sousb.com/2011/04/19/%E7%BB%B4%E6%8A%A4100%E4%BA%BF%E4%B8%AAurl/

題目：url地址 比如http://www.baidu.com/s?wd=baidu 的屬性，包括定長屬性（比如其被系統(tǒng)發(fā)現(xiàn)的時間）和不定長屬性（比如其描述）實現(xiàn)一個系統(tǒng)a.儲存和維護100億個url及其屬性。b.實現(xiàn)url及其屬性的增刪改。c.查一個url是否在系統(tǒng)中并給出信息。d.快速選出一個站點下所有url

提示：因為數(shù)據(jù)量大，可能存儲在多臺計算機中。

分析：這是一道百度的筆試題，這道題比較難，筆者只能給出幾個認識到的點。

• 首先，這些url要經(jīng)過partition分到X臺機器中：考慮使用一個hash函數(shù)hash(hostname(url))將url分配到X臺機器中，這樣做的目的：一是數(shù)據(jù)的分布式存儲，二是同一個站點的所有url保存到同一臺機器中。
• 其次，每臺機器應該如何組織這些數(shù)據(jù)？一種思路是用數(shù)據(jù)庫的思路去解決，這里提供另外一種思路。考慮將url直接放在內(nèi)存，接將url組織成樹狀結構，對于字符串來說，最長使用的是Trie tree，由于所占空間由最長url決定，在這里絕對不適用，再加上很多url擁有相同的屬性（如路徑等）這樣，使用trie tree 的一個變種radix tree，相比會非常節(jié)省空間，并且不會影響效率。
• 最后，給出了存儲模型，上面的abcd四問該怎么回答，這里就不一一解答了。

總結

以上是生活随笔為你收集整理的维护100亿个URL的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。