在實(shí)際的工作環(huán)境下粉铐，許多人會遇到海量數(shù)據(jù)這個(gè)復(fù)雜而艱巨的問題父款，它的主要難點(diǎn)有以下幾個(gè)方面：?

一厢塘、數(shù)據(jù)量過大，數(shù)據(jù)中什么情況都可能存在瓶籽。

如果說有10條數(shù)據(jù)引润，那么大不了每條去逐一檢查，人為處理告抄，如果有上百條數(shù)據(jù)，也可以考慮嵌牺，如果數(shù)據(jù)上到千萬級別打洼，甚至 過億，那不是手工能解決的了逆粹，必須通過工具或者程序進(jìn)行處理募疮，尤其海量的數(shù)據(jù)中，什么情況都可能存在僻弹，例如阿浓，數(shù)據(jù)中某處格式出了問題，尤其在程序處理時(shí)蹋绽， 前面還能正常處理芭毙，突然到了某個(gè)地方問題出現(xiàn)了筋蓖，程序終止了。

二退敦、軟硬件要求高粘咖，系統(tǒng)資源占用率高。

對海量的數(shù)據(jù)進(jìn)行處理侈百，除了好的方法瓮下，最重要的就是合理使用工具，合理分配系統(tǒng)資源钝域。一般情況讽坏，如果處理的數(shù)據(jù)過TB級，小型機(jī)是要考慮的例证，普通的機(jī)子如果有好的方法可以考慮震缭，不過也必須加大CPU和內(nèi)存，就象面對著千軍萬馬战虏，光有勇氣沒有一兵一卒是很難取勝的拣宰。

三、要求很高的處理方法和技巧烦感。

這也是本文的寫作目的所在巡社，好的處理方法是一位工程師長期工作經(jīng)驗(yàn)的積累，也是個(gè)人的經(jīng)驗(yàn)的總結(jié)手趣。沒有通用的處理方法晌该，但有通用的原理和規(guī)則。

下面我們來詳細(xì)介紹一下處理海量數(shù)據(jù)的經(jīng)驗(yàn)和技巧：

一绿渣、選用優(yōu)秀的數(shù)據(jù)庫工具

現(xiàn)在的數(shù)據(jù)庫工具廠家比較多朝群，對海量數(shù)據(jù)的處理對所使用的數(shù)據(jù)庫工具要求比較高，一般使用Oracle或者DB2中符，微軟 公司最近發(fā)布的SQL Server 2005性能也不錯(cuò)姜胖。另外在BI領(lǐng)域：數(shù)據(jù)庫，數(shù)據(jù)倉庫淀散，多維數(shù)據(jù)庫右莱，數(shù)據(jù)挖掘等相關(guān)工具也要進(jìn)行選擇，象好的ETL工具和好的OLAP工具都十分必要档插， 例如Informatic慢蜓，Eassbase等。筆者在實(shí)際數(shù)據(jù)分析項(xiàng)目中郭膛，對每天6000萬條的日志數(shù)據(jù)進(jìn)行處理晨抡，使用SQL Server 2000需要花費(fèi)6小時(shí)，而使用SQL Server 2005則只需要花費(fèi)3小時(shí)。

二耘柱、編寫優(yōu)良的程序代碼

處理數(shù)據(jù)離不開優(yōu)秀的程序代碼圆雁，尤其在進(jìn)行復(fù)雜數(shù)據(jù)處理時(shí)，必須使用程序帆谍。好的程序代碼對數(shù)據(jù)的處理至關(guān)重要伪朽，這不僅僅是數(shù)據(jù)處理準(zhǔn)確度的問題，更是數(shù)據(jù)處理效率的問題汛蝙。良好的程序代碼應(yīng)該包含好的算法烈涮，包含好的處理流程，包含好的效率窖剑，包含好的異常處理機(jī)制等坚洽。

三、對海量數(shù)據(jù)進(jìn)行分區(qū)操作

對海量數(shù)據(jù)進(jìn)行分區(qū)操作十分必要西土，例如針對按年份存取的數(shù)據(jù)讶舰，我們可以按年進(jìn)行分區(qū)，不同的數(shù)據(jù)庫有不同的分區(qū)方式需了，不 過處理機(jī)制大體相同跳昼。例如SQL Server的數(shù)據(jù)庫分區(qū)是將不同的數(shù)據(jù)存于不同的文件組下，而不同的文件組存于不同的磁盤分區(qū)下肋乍，這樣將數(shù)據(jù)分散開鹅颊，減小磁盤I/O，減小了系統(tǒng)負(fù)荷墓造， 而且還可以將日志堪伍，索引等放于不同的分區(qū)下。

四觅闽、建立廣泛的索引

對海量的數(shù)據(jù)處理帝雇，對大表建立索引是必行的，建立索引要考慮到具體情況蛉拙，例如針對大表的分組尸闸、排序等字段，都要建立相應(yīng) 索引刘离，一般還可以建立復(fù)合索引室叉，對經(jīng)常插入的表則建立索引時(shí)要小心，筆者在處理數(shù)據(jù)時(shí)硫惕，曾經(jīng)在一個(gè)ETL流程中，當(dāng)插入表時(shí)野来，首先刪除索引恼除，然后插入完 畢，建立索引，并實(shí)施聚合操作豁辉，聚合完成后令野，再次插入前還是刪除索引，所以索引要用到好的時(shí)機(jī)徽级，索引的填充因子和聚集气破、非聚集索引都要考慮。

五餐抢、建立緩存機(jī)制

當(dāng)數(shù)據(jù)量增加時(shí)现使，一般的處理工具都要考慮到緩存問題。緩存大小設(shè)置的好差也關(guān)系到數(shù)據(jù)處理的成敗旷痕，例如碳锈，筆者在處理2億條數(shù)據(jù)聚合操作時(shí)，緩存設(shè)置為100000條/Buffer欺抗，這對于這個(gè)級別的數(shù)據(jù)量是可行的售碳。

六、加大虛擬內(nèi)存

如果系統(tǒng)資源有限绞呈，內(nèi)存提示不足贸人，則可以靠增加虛擬內(nèi)存來解決。筆者在實(shí)際項(xiàng)目中曾經(jīng)遇到針對18億條的數(shù)據(jù)進(jìn)行處理佃声， 內(nèi)存為1GB灸姊，1個(gè)P42.4G的CPU，對這么大的數(shù)據(jù)量進(jìn)行聚合操作是有問題的秉溉，提示內(nèi)存不足力惯，那么采用了加大虛擬內(nèi)存的方法來解決，在6塊磁盤分區(qū) 上分別建立了6個(gè)4096M的磁盤分區(qū)召嘶，用于虛擬內(nèi)存父晶，這樣虛擬的內(nèi)存則增加為 4096*6 + 1024 =25600 M，解決了數(shù)據(jù)處理中的內(nèi)存不足問題弄跌。

七甲喝、分批處理

海量數(shù)據(jù)處理難因?yàn)閿?shù)據(jù)量大，那么解決海量數(shù)據(jù)處理難的問題其中一個(gè)技巧是減少數(shù)據(jù)量铛只〔号郑可以對海量數(shù)據(jù)分批處理，然后處 理后的數(shù)據(jù)再進(jìn)行合并操作淳玩，這樣逐個(gè)擊破直撤，有利于小數(shù)據(jù)量的處理，不至于面對大數(shù)據(jù)量帶來的問題蜕着，不過這種方法也要因時(shí)因勢進(jìn)行谋竖，如果不允許拆分?jǐn)?shù)據(jù)红柱，還 需要另想辦法。不過一般的數(shù)據(jù)按天蓖乘、按月锤悄、按年等存儲的，都可以采用先分后合的方法嘉抒，對數(shù)據(jù)進(jìn)行分開處理零聚。

八、使用臨時(shí)表和中間表

數(shù)據(jù)量增加時(shí)些侍，處理中要考慮提前匯總隶症。這樣做的目的是化整為零，大表變小表娩梨，分塊處理完成后沿腰，再利用一定的規(guī)則進(jìn)行合 并，處理過程中的臨時(shí)表的使用和中間結(jié)果的保存都非常重要狈定，如果對于超海量的數(shù)據(jù)颂龙，大表處理不了，只能拆分為多個(gè)小表纽什。如果處理過程中需要多步匯總操作措嵌， 可按匯總步驟一步步來，不要一條語句完成芦缰，一口氣吃掉一個(gè)胖子企巢。

九、優(yōu)化查詢SQL語句

在對海量數(shù)據(jù)進(jìn)行查詢處理過程中让蕾，查詢的SQL語句的性能對查詢效率的影響是非常大的浪规，編寫高效優(yōu)良的SQL腳本和存儲 過程是數(shù)據(jù)庫工作人員的職責(zé)，也是檢驗(yàn)數(shù)據(jù)庫工作人員水平的一個(gè)標(biāo)準(zhǔn)探孝，在對SQL語句的編寫過程中笋婿，例如減少關(guān)聯(lián)，少用或不用游標(biāo)顿颅，設(shè)計(jì)好高效的數(shù)據(jù)庫表 結(jié)構(gòu)等都十分必要缸濒。筆者在工作中試著對1億行的數(shù)據(jù)使用游標(biāo)，運(yùn)行3個(gè)小時(shí)沒有出結(jié)果粱腻，這是一定要改用程序處理了庇配。

十、使用文本格式進(jìn)行處理

對一般的數(shù)據(jù)處理可以使用數(shù)據(jù)庫绍些，如果對復(fù)雜的數(shù)據(jù)處理捞慌，必須借助程序，那么在程序操作數(shù)據(jù)庫和程序操作文本之間選擇遇革， 是一定要選擇程序操作文本的卿闹，原因?yàn)椋撼绦虿僮魑谋舅俣瓤旖腋猓粚ξ谋具M(jìn)行處理不容易出錯(cuò)萝快；文本的存儲不受限制等锻霎。例如一般的海量的網(wǎng)絡(luò)日志都是文本格式或者 csv格式（文本格式），對它進(jìn)行處理牽扯到數(shù)據(jù)清洗揪漩，是要利用程序進(jìn)行處理的旋恼，而不建議導(dǎo)入數(shù)據(jù)庫再做清洗。

十一奄容、定制強(qiáng)大的清洗規(guī)則和出錯(cuò)處理機(jī)制

海量數(shù)據(jù)中存在著不一致性冰更，極有可能出現(xiàn)某處的瑕疵。例如昂勒，同樣的數(shù)據(jù)中的時(shí)間字段蜀细，有的可能為非標(biāo)準(zhǔn)的時(shí)間，出現(xiàn)的原因可能為應(yīng)用程序的錯(cuò)誤戈盈，系統(tǒng)的錯(cuò)誤等奠衔，這是在進(jìn)行數(shù)據(jù)處理時(shí)，必須制定強(qiáng)大的數(shù)據(jù)清洗規(guī)則和出錯(cuò)處理機(jī)制塘娶。

十二归斤、建立視圖或者物化視圖

視圖中的數(shù)據(jù)來源于基表，對海量數(shù)據(jù)的處理刁岸，可以將數(shù)據(jù)按一定的規(guī)則分散到各個(gè)基表中脏里，查詢或處理過程中可以基于視圖進(jìn)行，這樣分散了磁盤I/O虹曙，正如10根繩子吊著一根柱子和一根吊著一根柱子的區(qū)別迫横。

十三、避免使用32位機(jī)子（極端情況）

目前的計(jì)算機(jī)很多都是32位的酝碳，那么編寫的程序?qū)?nèi)存的需要便受限制矾踱，而很多的海量數(shù)據(jù)處理是必須大量消耗內(nèi)存的，這便要求更好性能的機(jī)子击敌，其中對位數(shù)的限制也十分重要介返。

十四、考慮操作系統(tǒng)問題

海量數(shù)據(jù)處理過程中沃斤，除了對數(shù)據(jù)庫圣蝎，處理程序等要求比較高以外，對操作系統(tǒng)的要求也放到了重要的位置衡瓶，一般是必須使用服務(wù)器的徘公，而且對系統(tǒng)的安全性和穩(wěn)定性等要求也比較高。尤其對操作系統(tǒng)自身的緩存機(jī)制哮针，臨時(shí)空間的處理等問題都需要綜合考慮关面。

十五坦袍、使用數(shù)據(jù)倉庫和多維數(shù)據(jù)庫存儲

數(shù)據(jù)量加大是一定要考慮OLAP的，傳統(tǒng)的報(bào)表可能5等太、6個(gè)小時(shí)出來結(jié)果捂齐，而基于Cube的查詢可能只需要幾分鐘，因此處理海量數(shù)據(jù)的利器是OLAP多維分析缩抡，即建立數(shù)據(jù)倉庫奠宜，建立多維數(shù)據(jù)集，基于多維數(shù)據(jù)集進(jìn)行報(bào)表展現(xiàn)和數(shù)據(jù)挖掘等瞻想。

十六压真、使用采樣數(shù)據(jù)，進(jìn)行數(shù)據(jù)挖掘

基于海量數(shù)據(jù)的數(shù)據(jù)挖掘正在逐步興起蘑险，面對著超海量的數(shù)據(jù)滴肿，一般的挖掘軟件或算法往往采用數(shù)據(jù)抽樣的方式進(jìn)行處理，這樣 的誤差不會很高佃迄，大大提高了處理效率和處理的成功率泼差。一般采樣時(shí)要注意數(shù)據(jù)的完整性和，防止過大的偏差和屎。筆者曾經(jīng)對1億2千萬行的表數(shù)據(jù)進(jìn)行采樣拴驮，抽取出 400萬行，經(jīng)測試軟件測試處理的誤差為千分之五柴信，客戶可以接受套啤。

還有一些方法，需要在不同的情況和場合下運(yùn)用随常，例如使用代理鍵等操作潜沦，這樣的好處是加快了聚合時(shí)間，因?yàn)閷?shù)值型的聚合比對字符型的聚合快得多绪氛。類似的情況需要針對不同的需求進(jìn)行處理唆鸡。

海量數(shù)據(jù)是發(fā)展趨勢，對數(shù)據(jù)分析和挖掘也越來越重要枣察，從海量數(shù)據(jù)中提取有用信息重要而緊迫争占，這便要求處理要準(zhǔn)確，精度要高序目，而且處理時(shí)間要短臂痕，得到有價(jià)值信息要快，所以猿涨，對海量數(shù)據(jù)的研究很有前途握童，也很值得進(jìn)行廣泛深入的研究。

一叛赚、Bloom filter

適用范圍：可以用來實(shí)現(xiàn)數(shù)據(jù)字典澡绩，進(jìn)行數(shù)據(jù)的判重稽揭，或者集合求交集

基本原理及要點(diǎn)：

對于原理來說很簡單，位數(shù)組+k個(gè)獨(dú)立hash函數(shù)肥卡。將hash函數(shù)對應(yīng)的值的位數(shù)組置1溪掀，查找時(shí)如果發(fā)現(xiàn)所有hash函數(shù)對應(yīng)位都是1說明存在，很明顯這個(gè)過程并不保證查找的結(jié)果是100%正確的召调。同時(shí)也不支持刪除一個(gè)已經(jīng)插入的關(guān)鍵字膨桥，因?yàn)樵撽P(guān)鍵字對應(yīng)的位會牽動到其他的關(guān)鍵字蛮浑。所以一個(gè)簡單的改進(jìn)就是 counting Bloom filter唠叛，用一個(gè)counter數(shù)組代替位數(shù)組，就可以支持刪除了沮稚。

還有一個(gè)比較重要的問題艺沼，如何根據(jù)輸入元素個(gè)數(shù)n，確定位數(shù)組m的大小及hash函數(shù)個(gè)數(shù)蕴掏。當(dāng)hash函數(shù)個(gè)數(shù)k=(ln2)*(m/n)時(shí)錯(cuò)誤率最小障般。在錯(cuò)誤率不大于E的情況下，m至少要等于n*lg(1/E)才能表示任意n個(gè)元素的集合盛杰。但m還應(yīng)該更大些挽荡，因?yàn)檫€要保證bit數(shù)組里至少一半為0，則m應(yīng)該>=nlg(1/E)*lge 大概就是nlg(1/E)1.44倍(lg表示以2為底的對數(shù))即供。

舉個(gè)例子我們假設(shè)錯(cuò)誤率為0.01定拟，則此時(shí)m應(yīng)大概是n的13倍。這樣k大概是8個(gè)逗嫡。

注意這里m與n的單位不同青自，m是bit為單位，而n則是以元素個(gè)數(shù)為單位(準(zhǔn)確的說是不同元素的個(gè)數(shù))驱证。通常單個(gè)元素的長度都是有很多bit的延窜。所以使用bloom filter內(nèi)存上通常都是節(jié)省的。

擴(kuò)展：

Bloom filter將集合中的元素映射到位數(shù)組中抹锄，用k（k為哈希函數(shù)個(gè)數(shù)）個(gè)映射位是否全1表示元素在不在這個(gè)集合中逆瑞。Counting bloom filter（CBF）將位數(shù)組中的每一位擴(kuò)展為一個(gè)counter，從而支持了元素的刪除操作伙单。Spectral Bloom Filter（SBF）將其與集合元素的出現(xiàn)次數(shù)關(guān)聯(lián)获高。SBF采用counter中的最小值來近似表示元素的出現(xiàn)頻率。

問題實(shí)例：給你A,B兩個(gè)文件车份，各存放50億條URL谋减，每條URL占用64字節(jié)，內(nèi)存限制是4G扫沼，讓你找出A,B文件共同的URL出爹。如果是三個(gè)乃至n個(gè)文件呢庄吼？

根據(jù)這個(gè)問題我們來計(jì)算下內(nèi)存的占用，4G=2^32大概是40億*8大概是340億严就，n=50億总寻，如果按出錯(cuò)率0.01算需要的大概是650億個(gè)bit。現(xiàn)在可用的是340億梢为，相差并不多渐行，這樣可能會使出錯(cuò)率上升些。另外如果這些urlip是一一對應(yīng)的铸董，就可以轉(zhuǎn)換成ip祟印，則大大簡單了。

二粟害、Hashing

適用范圍：快速查找蕴忆，刪除的基本數(shù)據(jù)結(jié)構(gòu)，通常需要總數(shù)據(jù)量可以放入內(nèi)存

基本原理及要點(diǎn)：

hash函數(shù)選擇悲幅，針對字符串套鹅，整數(shù)，排列汰具，具體相應(yīng)的hash方法卓鹿。

碰撞處理，一種是open hashing留荔，也稱為拉鏈法吟孙；另一種就是closed hashing，也稱開地址法存谎，opened addressing拔疚。

擴(kuò)展：

d-left hashing中的d是多個(gè)的意思，我們先簡化這個(gè)問題既荚，看一看2-left hashing稚失。2-left hashing指的是將一個(gè)哈希表分成長度相等的兩半，分別叫做T1和T2恰聘，給T1和T2分別配備一個(gè)哈希函數(shù)句各，h1和h2。在存儲一個(gè)新的key時(shí)晴叨，同時(shí)用兩個(gè)哈希函數(shù)進(jìn)行計(jì)算凿宾，得出兩個(gè)地址h1[key]和h2[key]。這時(shí)需要檢查T1中的h1[key]位置和T2中的h2[key]位置兼蕊，哪一個(gè)位置已經(jīng)存儲的（有碰撞的）key比較多初厚，然后將新key存儲在負(fù)載少的位置。如果兩邊一樣多，比如兩個(gè)位置都為空或者都存儲了一個(gè)key产禾，就把新key存儲在左邊的T1子表中排作，2-left也由此而來。在查找一個(gè)key時(shí)亚情，必須進(jìn)行兩次hash妄痪，同時(shí)查找兩個(gè)位置。

問題實(shí)例：

1).海量日志數(shù)據(jù)楞件，提取出某日訪問百度次數(shù)最多的那個(gè)IP衫生。

IP的數(shù)目還是有限的，最多2^32個(gè)土浸，所以可以考慮使用hash將ip直接存入內(nèi)存罪针，然后進(jìn)行統(tǒng)計(jì)。

三栅迄、bit-map

適用范圍：可進(jìn)行數(shù)據(jù)的快速查找站故，判重，刪除毅舆，一般來說數(shù)據(jù)范圍是int的10倍以下

基本原理及要點(diǎn)：使用bit數(shù)組來表示某些元素是否存在，比如8位電話號碼

擴(kuò)展：bloom filter可以看做是對bit-map的擴(kuò)展

問題實(shí)例：

1)已知某個(gè)文件內(nèi)包含一些電話號碼愈腾，每個(gè)號碼為8位數(shù)字憋活，統(tǒng)計(jì)不同號碼的個(gè)數(shù)。

8位最多99 999 999虱黄，大概需要99m個(gè)bit悦即，大概10幾m字節(jié)的內(nèi)存即可。

2)2.5億個(gè)整數(shù)中找出不重復(fù)的整數(shù)的個(gè)數(shù)橱乱，內(nèi)存空間不足以容納這2.5億個(gè)整數(shù)辜梳。

將bit-map擴(kuò)展一下，用2bit表示一個(gè)數(shù)即可泳叠，0表示未出現(xiàn)作瞄，1表示出現(xiàn)一次，2表示出現(xiàn)2次及以上危纫∽诨樱或者我們不用2bit來進(jìn)行表示，我們用兩個(gè)bit-map即可模擬實(shí)現(xiàn)這個(gè)2bit-map种蝶。

四契耿、堆

適用范圍：海量數(shù)據(jù)前n大，并且n比較小螃征，堆可以放入內(nèi)存

基本原理及要點(diǎn)：最大堆求前n小搪桂，最小堆求前n大。方法盯滚，比如求前n小踢械，我們比較當(dāng)前元素與最大堆里的最大元素拙泽，如果它小于最大元素，則應(yīng)該替換那個(gè)最大元素裸燎。這樣最后得到的n個(gè)元素就是最小的n個(gè)顾瞻。適合大數(shù)據(jù)量，求前n小德绿，n的大小比較小的情況荷荤，這樣可以掃描一遍即可得到所有的前n元素，效率很高移稳。

擴(kuò)展：雙堆蕴纳，一個(gè)最大堆與一個(gè)最小堆結(jié)合，可以用來維護(hù)中位數(shù)个粱。

問題實(shí)例：

1)100w個(gè)數(shù)中找最大的前100個(gè)數(shù)古毛。

用一個(gè)100個(gè)元素大小的最小堆即可。

五都许、雙層桶劃分-—其實(shí)本質(zhì)上就是【分而治之】的思想稻薇，重在分的技巧上！

適用范圍：第k大胶征，中位數(shù)塞椎，不重復(fù)或重復(fù)的數(shù)字

基本原理及要點(diǎn)：因?yàn)樵胤秶艽螅荒芾弥苯訉ぶ繁砭Φ停酝ㄟ^多次劃分案狠，逐步確定范圍，然后最后在一個(gè)可以接受的范圍內(nèi)進(jìn)行钱雷÷钐可以通過多次縮小，雙層只是一個(gè)例子罩抗。

擴(kuò)展：

問題實(shí)例：

1).2.5億個(gè)整數(shù)中找出不重復(fù)的整數(shù)的個(gè)數(shù)拉庵，內(nèi)存空間不足以容納這2.5億個(gè)整數(shù)。

有點(diǎn)像鴿巢原理澄暮，整數(shù)個(gè)數(shù)為2^32,也就是名段，我們可以將這2^32個(gè)數(shù)，劃分為2^8個(gè)區(qū)域(比如用單個(gè)文件代表一個(gè)區(qū)域)泣懊，然后將數(shù)據(jù)分離到不同的區(qū)域伸辟，然后不同的區(qū)域在利用bitmap就可以直接解決了。也就是說只要有足夠的磁盤空間馍刮，就可以很方便的解決信夫。

2).5億個(gè)int找它們的中位數(shù)。

這個(gè)例子比上面那個(gè)更明顯。首先我們將int劃分為2^16個(gè)區(qū)域静稻，然后讀取數(shù)據(jù)統(tǒng)計(jì)落到各個(gè)區(qū)域里的數(shù)的個(gè)數(shù)警没，之后我們根據(jù)統(tǒng)計(jì)結(jié)果就可以判斷中位數(shù)落到那個(gè)區(qū)域，同時(shí)知道這個(gè)區(qū)域中的第幾大數(shù)剛好是中位數(shù)振湾。然后第二次掃描我們只統(tǒng)計(jì)落在這個(gè)區(qū)域中的那些數(shù)就可以了杀迹。

實(shí)際上，如果不是int是int64押搪，我們可以經(jīng)過3次這樣的劃分即可降低到可以接受的程度树酪。即可以先將int64分成2^24個(gè)區(qū)域，然后確定區(qū)域的第幾大數(shù)大州，在將該區(qū)域分成2^20個(gè)子區(qū)域续语，然后確定是子區(qū)域的第幾大數(shù)，然后子區(qū)域里的數(shù)的個(gè)數(shù)只有2^20厦画，就可以直接利用direct addr table進(jìn)行統(tǒng)計(jì)了疮茄。

六、數(shù)據(jù)庫索引

適用范圍：大數(shù)據(jù)量的增刪改查

基本原理及要點(diǎn)：利用數(shù)據(jù)的設(shè)計(jì)實(shí)現(xiàn)方法根暑，對海量數(shù)據(jù)的增刪改查進(jìn)行處理力试。

七、倒排索引(Inverted index)

適用范圍：搜索引擎购裙，關(guān)鍵字查詢

基本原理及要點(diǎn)：為何叫倒排索引懂版？一種索引方法，被用來存儲在全文搜索下某個(gè)單詞在一個(gè)文檔或者一組文檔中的存儲位置的映射躏率。

以英文為例，下面是要被索引的文本： T0 = “it is what it is” T1 = “what is it” T2 = “it is a banana”

我們就能得到下面的反向文件索引：

“a”: {2} “banana”: {2} “is”: {0, 1, 2} “it”: {0, 1, 2} “what”: {0, 1}

檢索的條件”what”,”is”和”it”將對應(yīng)集合的交集民鼓。

正向索引開發(fā)出來用來存儲每個(gè)文檔的單詞的列表薇芝。正向索引的查詢往往滿足每個(gè)文檔有序頻繁的全文查詢和每個(gè)單詞在校驗(yàn)文檔中的驗(yàn)證這樣的查詢。在正向索引中丰嘉，文檔占據(jù)了中心的位置夯到，每個(gè)文檔指向了一個(gè)它所包含的索引項(xiàng)的序列。也就是說文檔指向了它包含的那些單詞饮亏，而反向索引則是單詞指向了包含它的文檔耍贾，很容易看到這個(gè)反向的關(guān)系。

擴(kuò)展：

問題實(shí)例：文檔檢索系統(tǒng)路幸，查詢那些文件包含了某單詞荐开，比如常見的學(xué)術(shù)論文的關(guān)鍵字搜索。

八简肴、外排序

適用范圍：大數(shù)據(jù)的排序晃听，去重

基本原理及要點(diǎn)：外排序的歸并方法，置換選擇敗者樹原理，最優(yōu)歸并樹

擴(kuò)展：

問題實(shí)例：

1).有一個(gè)1G大小的一個(gè)文件能扒，里面每一行是一個(gè)詞佣渴，詞的大小不超過16個(gè)字節(jié)，內(nèi)存限制大小是1M初斑。返回頻數(shù)最高的100個(gè)詞辛润。

這個(gè)數(shù)據(jù)具有很明顯的特點(diǎn)，詞的大小為16個(gè)字節(jié)见秤，但是內(nèi)存只有1m做hash有些不夠砂竖，所以可以用來排序。內(nèi)存可以當(dāng)輸入緩沖區(qū)使用秦叛。

九晦溪、trie樹

適用范圍：數(shù)據(jù)量大，重復(fù)多挣跋，但是數(shù)據(jù)種類小可以放入內(nèi)存

基本原理及要點(diǎn)：實(shí)現(xiàn)方式三圆，節(jié)點(diǎn)孩子的表示方式

擴(kuò)展：壓縮實(shí)現(xiàn)。

問題實(shí)例：

1).有10個(gè)文件避咆，每個(gè)文件1G舟肉，每個(gè)文件的每一行都存放的是用戶的query，每個(gè)文件的query都可能重復(fù)查库。要你按照query的頻度排序路媚。

2).1000萬字符串，其中有些是相同的(重復(fù)),需要把重復(fù)的全部去掉樊销，保留沒有重復(fù)的字符串整慎。請問怎么設(shè)計(jì)和實(shí)現(xiàn)？

3).尋找熱門查詢：查詢串的重復(fù)度比較高围苫，雖然總數(shù)是1千萬裤园，但如果除去重復(fù)后，不超過3百萬個(gè)剂府，每個(gè)不超過255字節(jié)拧揽。

十、分布式處理 mapreduce

適用范圍：數(shù)據(jù)量大腺占，但是數(shù)據(jù)種類小可以放入內(nèi)存

基本原理及要點(diǎn)：將數(shù)據(jù)交給不同的機(jī)器去處理淤袜，數(shù)據(jù)劃分，結(jié)果歸約衰伯。

擴(kuò)展：

問題實(shí)例：

1).The canonical example application of MapReduce is a process to count the appearances ofeach different word in a set of documents:

2).海量數(shù)據(jù)分布在100臺電腦中铡羡，想個(gè)辦法高效統(tǒng)計(jì)出這批數(shù)據(jù)的TOP10。

3).一共有N個(gè)機(jī)器嚎研，每個(gè)機(jī)器上有N個(gè)數(shù)蓖墅。每個(gè)機(jī)器最多存O(N)個(gè)數(shù)并對它們操作库倘。如何找到N^2個(gè)數(shù)的中數(shù)(median)？

經(jīng)典問題分析

上千萬or億數(shù)據(jù)（有重復(fù)）论矾，統(tǒng)計(jì)其中出現(xiàn)次數(shù)最多的前N個(gè)數(shù)據(jù),分兩種情況：可一次讀入內(nèi)存教翩，不可一次讀入。

可用思路：trie樹+堆贪壳，數(shù)據(jù)庫索引饱亿，劃分子集分別統(tǒng)計(jì)，hash闰靴，分布式計(jì)算彪笼，近似統(tǒng)計(jì)，外排序

所謂的是否能一次讀入內(nèi)存蚂且，實(shí)際上應(yīng)該指去除重復(fù)后的數(shù)據(jù)量配猫。如果去重后數(shù)據(jù)可以放入內(nèi)存，我們可以為數(shù)據(jù)建立字典杏死，比如通過 map泵肄，hashmap，trie淑翼，然后直接進(jìn)行統(tǒng)計(jì)即可腐巢。當(dāng)然在更新每條數(shù)據(jù)的出現(xiàn)次數(shù)的時(shí)候，我們可以利用一個(gè)堆來維護(hù)出現(xiàn)次數(shù)最多的前N個(gè)數(shù)據(jù)玄括，當(dāng)然這樣導(dǎo)致維護(hù)次數(shù)增加冯丙，不如完全統(tǒng)計(jì)后在求前N大效率高。

如果數(shù)據(jù)無法放入內(nèi)存遭京。一方面我們可以考慮上面的字典方法能否被改進(jìn)以適應(yīng)這種情形胃惜，可以做的改變就是將字典存放到硬盤上，而不是內(nèi)存哪雕，這可以參考數(shù)據(jù)庫的存儲方法蛹疯。

當(dāng)然還有更好的方法，就是可以采用分布式計(jì)算热监，基本上就是map-reduce過程，首先可以根據(jù)數(shù)據(jù)值或者把數(shù)據(jù)hash(md5)后的值饮寞，將數(shù)據(jù)按照范圍劃分到不同的機(jī)子孝扛，最好可以讓數(shù)據(jù)劃分后可以一次讀入內(nèi)存，這樣不同的機(jī)子負(fù)責(zé)處理各種的數(shù)值范圍幽崩，實(shí)際上就是map苦始。得到結(jié)果后，各個(gè)機(jī)子只需拿出各自的出現(xiàn)次數(shù)最多的前N個(gè)數(shù)據(jù)慌申，然后匯總陌选，選出所有的數(shù)據(jù)中出現(xiàn)次數(shù)最多的前N個(gè)數(shù)據(jù)理郑，這實(shí)際上就是reduce過程。

實(shí)際上可能想直接將數(shù)據(jù)均分到不同的機(jī)子上進(jìn)行處理咨油，這樣是無法得到正確的解的您炉。因?yàn)橐粋€(gè)數(shù)據(jù)可能被均分到不同的機(jī)子上，而另一個(gè)則可能完全聚集到一個(gè)機(jī)子上役电，同時(shí)還可能存在具有相同數(shù)目的數(shù)據(jù)赚爵。比如我們要找出現(xiàn)次數(shù)最多的前100個(gè)，我們將1000萬的數(shù)據(jù)分布到10臺機(jī)器上法瑟，找到每臺出現(xiàn)次數(shù)最多的前 100個(gè)冀膝，歸并之后這樣不能保證找到真正的第100個(gè)，因?yàn)楸热绯霈F(xiàn)次數(shù)最多的第100個(gè)可能有1萬個(gè)霎挟，但是它被分到了10臺機(jī)子窝剖，這樣在每臺上只有1千個(gè)，假設(shè)這些機(jī)子排名在1000個(gè)之前的那些都是單獨(dú)分布在一臺機(jī)子上的酥夭，比如有1001個(gè)赐纱，這樣本來具有1萬個(gè)的這個(gè)就會被淘汰，即使我們讓每臺機(jī)子選出出現(xiàn)次數(shù)最多的1000個(gè)再歸并采郎，仍然會出錯(cuò)千所，因?yàn)榭赡艽嬖诖罅總€(gè)數(shù)為1001個(gè)的發(fā)生聚集。因此不能將數(shù)據(jù)隨便均分到不同機(jī)子上蒜埋，而是要根據(jù)hash 后的值將它們映射到不同的機(jī)子上處理淫痰，讓不同的機(jī)器處理一個(gè)數(shù)值范圍嗡载。

而外排序的方法會消耗大量的IO慎颗，效率不會很高。而上面的分布式方法会钝，也可以用于單機(jī)版本烈评，也就是將總的數(shù)據(jù)根據(jù)值的范圍火俄，劃分成多個(gè)不同的子文件，然后逐個(gè)處理讲冠。處理完畢之后再對這些單詞的及其出現(xiàn)頻率進(jìn)行一個(gè)歸并瓜客。實(shí)際上就可以利用一個(gè)外排序的歸并過程。

另外還可以考慮近似計(jì)算竿开，也就是我們可以通過結(jié)合自然語言屬性谱仪，只將那些真正實(shí)際中出現(xiàn)最多的那些詞作為一個(gè)字典，使得這個(gè)規(guī)姆癫剩可以放入內(nèi)存疯攒。