問(wèn)：
有1000億條記錄烈和，每條記錄由url,ip,時(shí)間組成，設(shè)計(jì)一個(gè)系統(tǒng)能夠快速查詢以下內(nèi)容
1.給定url和時(shí)間段（精確到分鐘）統(tǒng)計(jì)url的訪問(wèn)次數(shù)
2.給定ip和時(shí)間段（精確到分鐘）統(tǒng)計(jì)ip的訪問(wèn)次數(shù)
答：
首先切端，1000億條記錄全部放到內(nèi)存肯定不夠磅轻，那就是分成小文件了拐格，然后整合掉分；
公共的時(shí)間段俭缓，因?yàn)榫_到分鐘，我們把這每一分鐘建成一個(gè)小文件酥郭，每個(gè)小文件肯定會(huì)有許多重復(fù)的ip华坦，url；
現(xiàn)在統(tǒng)計(jì)每個(gè)小的文件中url的訪問(wèn)量和ip的訪問(wèn)次數(shù)不从，方法就是建立索引惜姐；
（建立索引的目的是為了減少查詢次數(shù)，但是隨著索引級(jí)數(shù)增多也會(huì)造成花更多的時(shí)間在建立索引上）椿息；
建立url的索引载弄，假如是www.nowcoder.com/question,可以分別給www.nowcoder.com和question建立索引，那么來(lái)了一條url撵颊，先看一級(jí)索引是不是匹配，匹配再看二級(jí)索引惫叛，相同的話就是我們要的url目標(biāo)倡勇；
ip的索引也是一樣，ip分成4段建立索引嘉涌；
所以這里影響效率的就是在索引建立這塊妻熊，索引建立好那就是查詢的事了的，就會(huì)變得非陈刈睿快扔役。
假定給定了某個(gè)時(shí)間段，找出url的訪問(wèn)量警医，那么先找到給定的時(shí)間段亿胸，對(duì)應(yīng)著剛開(kāi)始分割的小的文件（每一個(gè)分鐘）中搜索，通過(guò)索引找到相同的url之后预皇，開(kāi)始統(tǒng)計(jì)侈玄，直到搜索完所有的給定時(shí)間段內(nèi)的所有的小的文件；
求ip的訪問(wèn)次數(shù)也是一樣吟温，按照給定的時(shí)間段序仙，找到對(duì)應(yīng)的小的文件，通過(guò)索引找到相同的ip后統(tǒng)計(jì)鲁豪，直到搜索完了給定時(shí)間段內(nèi)的所有的小的文件潘悼。
問(wèn)：
海量數(shù)據(jù)處理 - 10億個(gè)數(shù)中找出最大的10000個(gè)數(shù)（top K問(wèn)題）
答：
先拿10000個(gè)數(shù)建堆律秃，然后一次添加剩余元素，如果大于堆頂?shù)臄?shù)（10000中最小的）治唤，將這個(gè)數(shù)替換堆頂棒动，并調(diào)整結(jié)構(gòu)使之仍然是一個(gè)最小堆，這樣肝劲，遍歷完后迁客，堆中的10000個(gè)數(shù)就是所需的最大的10000個(gè)。建堆時(shí)間復(fù)雜度是O（mlogm）辞槐，算法的時(shí)間復(fù)雜度為O（nmlogm）（n為10億掷漱，m為10000）。
優(yōu)化的方法：可以把所有10億個(gè)數(shù)據(jù)分組存放榄檬，比如分別放在1000個(gè)文件中卜范。這樣處理就可以分別在每個(gè)文件的10^6個(gè)數(shù)據(jù)中找出最大的10000個(gè)數(shù)，合并到一起在再找出最終的結(jié)果鹿榜。
以上就是面試時(shí)簡(jiǎn)單提到的內(nèi)容海雪，下面整理一下這方面的問(wèn)題：
top K問(wèn)題
在大規(guī)模數(shù)據(jù)處理中，經(jīng)常會(huì)遇到的一類問(wèn)題：在海量數(shù)據(jù)中找出出現(xiàn)頻率最好的前k個(gè)數(shù)舱殿，或者從海量數(shù)據(jù)中找出最大的前k個(gè)數(shù)奥裸，這類問(wèn)題通常被稱為top K問(wèn)題。例如沪袭，在搜索引擎中湾宙，統(tǒng)計(jì)搜索最熱門的10個(gè)查詢?cè)~；在歌曲庫(kù)中統(tǒng)計(jì)下載最高的前10首歌等冈绊。
針對(duì)top K類問(wèn)題侠鳄，通常比較好的方案是分治+Trie樹(shù)/hash+小頂堆（就是上面提到的最小堆），即先將數(shù)據(jù)集按照Hash方法分解成多個(gè)小數(shù)據(jù)集死宣，然后使用Trie樹(shù)活著Hash統(tǒng)計(jì)每個(gè)小數(shù)據(jù)集中的query詞頻伟恶，之后用小頂堆求出每個(gè)數(shù)據(jù)集中出現(xiàn)頻率最高的前K個(gè)數(shù)，最后在所有top K中求出最終的top K毅该。
