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

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

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

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

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

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

這也是本文的寫作目的所在，好的處理方法是一位工程師長(zhǎng)期工作經(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ù)庫工具廠家比較多，對(duì)海量數(shù)據(jù)的處理對(duì)所使用的數(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)目中，對(duì)每天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í)，必須使用程序。好的程序代碼對(duì)數(shù)據(jù)的處理至關(guān)重要，這不僅僅是數(shù)據(jù)處理準(zhǔn)確度的問題，更是數(shù)據(jù)處理效率的問題。良好的程序代碼應(yīng)該包含好的算法，包含好的處理流程，包含好的效率，包含好的異常處理機(jī)制等。

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

對(duì)海量數(shù)據(jù)進(jìn)行分區(qū)操作十分必要，例如針對(duì)按年份存取的數(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ū)下。

四、建立廣泛的索引

對(duì)海量的數(shù)據(jù)處理，對(duì)大表建立索引是必行的，建立索引要考慮到具體情況，例如針對(duì)大表的分組、排序等字段，都要建立相應(yīng) 索引，一般還可以建立復(fù)合索引，對(duì)經(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，這對(duì)于這個(gè)級(jí)別的數(shù)據(jù)量是可行的。

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

如果系統(tǒng)資源有限，內(nèi)存提示不足，則可以靠增加虛擬內(nèi)存來解決。筆者在實(shí)際項(xiàng)目中曾經(jīng)遇到針對(duì)18億條的數(shù)據(jù)進(jìn)行處理， 內(nèi)存為1GB，1個(gè)P42.4G的CPU，對(duì)這么大的數(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ù)量。可以對(duì)海量數(shù)據(jù)分批處理，然后處 理后的數(shù)據(jù)再進(jìn)行合并操作，這樣逐個(gè)擊破，有利于小數(shù)據(jù)量的處理，不至于面對(duì)大數(shù)據(jù)量帶來的問題，不過這種方法也要因時(shí)因勢(shì)進(jìn)行，如果不允許拆分?jǐn)?shù)據(jù)，還 需要另想辦法。不過一般的數(shù)據(jù)按天、按月、按年等存儲(chǔ)的，都可以采用先分后合的方法，對(duì)數(shù)據(jù)進(jìn)行分開處理。

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

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

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

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

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

對(duì)一般的數(shù)據(jù)處理可以使用數(shù)據(jù)庫，如果對(duì)復(fù)雜的數(shù)據(jù)處理，必須借助程序，那么在程序操作數(shù)據(jù)庫和程序操作文本之間選擇， 是一定要選擇程序操作文本的，原因?yàn)椋撼绦虿僮魑谋舅俣瓤?；?duì)文本進(jìn)行處理不容易出錯(cuò)；文本的存儲(chǔ)不受限制等。例如一般的海量的網(wǎng)絡(luò)日志都是文本格式或者 csv格式（文本格式），對(duì)它進(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ù)來源于基表，對(duì)海量數(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ī)子，其中對(duì)位數(shù)的限制也十分重要。

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

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

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

數(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ù)挖掘正在逐步興起，面對(duì)著超海量的數(shù)據(jù)，一般的挖掘軟件或算法往往采用數(shù)據(jù)抽樣的方式進(jìn)行處理，這樣 的誤差不會(huì)很高，大大提高了處理效率和處理的成功率。一般采樣時(shí)要注意數(shù)據(jù)的完整性和，防止過大的偏差。筆者曾經(jīng)對(duì)1億2千萬行的表數(shù)據(jù)進(jìn)行采樣，抽取出 400萬行，經(jīng)測(cè)試軟件測(cè)試處理的誤差為千分之五，客戶可以接受。

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

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

海量數(shù)據(jù)處理專題（一）——開篇

　　大數(shù)據(jù)量的問題是很多面試筆試中經(jīng)常出現(xiàn)的問題，比如baidu google 騰訊 這樣的一些涉及到海量數(shù)據(jù)的公司經(jīng)常會(huì)問到。

　　下面的方法是我對(duì)海量數(shù)據(jù)的處理方法進(jìn)行了一個(gè)一般性的總結(jié)，當(dāng)然這些方法可能并不能完全覆蓋所有的問題，但是這樣 的一些方法也基本可以處理絕大多數(shù)遇到的問題。下面的一些問題基本直接來源于公司的面試筆試題目，方法不一定最優(yōu)，如果你有更好的處理方法，歡迎與我討 論。

　　本貼從解決這類問題的方法入手，開辟一系列專題來解決海量數(shù)據(jù)問題。擬包含 以下幾個(gè)方面。

1. Bloom Filter
2. Hash
3. Bit-Map
4. 堆(Heap)
5. 雙層桶劃分
6. 數(shù)據(jù)庫索引
7. 倒排索引（Inverted Index）
8. 外排序
9. Trie樹
10. MapReduce

　　在這些解決方案之上，再借助一定的例子來剖析海量數(shù)據(jù)處理問題的解決方案。

海量數(shù)據(jù)處理專題（二）——Bloom Filter

【什么是Bloom Filter】 
Bloom Filter是一種空間效率很高的隨機(jī)數(shù)據(jù)結(jié)構(gòu)，它利用位數(shù)組很簡(jiǎn)潔地表示一個(gè)集合，并能判斷一個(gè)元素是否屬于這個(gè)集合。Bloom Filter的這種高效是有一定代價(jià)的：在判斷一個(gè)元素是否屬于某個(gè)集合時(shí)，有可能會(huì)把不屬于這個(gè)集合的元素誤認(rèn)為屬于這個(gè)集合（false positive）。因此，Bloom Filter不適合那些“零錯(cuò)誤”的應(yīng)用場(chǎng)合。而在能容忍低錯(cuò)誤率的應(yīng)用場(chǎng)合下，Bloom Filter通過極少的錯(cuò)誤換取了存儲(chǔ)空間的極大節(jié)省。 這里有一篇關(guān)于Bloom Filter的詳細(xì)介紹，不太懂的博友可以看看。 
【適用范圍】 
可以用來實(shí)現(xiàn)數(shù)據(jù)字典，進(jìn)行數(shù)據(jù)的判重，或者集合求交集 
【基本原理及要點(diǎn)】 
對(duì)于原理來說很簡(jiǎn)單，位數(shù)組+k個(gè)獨(dú)立hash函數(shù)。將hash函數(shù)對(duì)應(yīng)的值的位數(shù)組置1，查找時(shí)如果發(fā)現(xiàn)所有hash函數(shù)對(duì)應(yīng)位都是1說明存在，很明顯 這 個(gè)過程并不保證查找的結(jié)果是100%正確的。同時(shí)也不支持刪除一個(gè)已經(jīng)插入的關(guān)鍵字，因?yàn)樵撽P(guān)鍵字對(duì)應(yīng)的位會(huì)牽動(dòng)到其他的關(guān)鍵字。所以一個(gè)簡(jiǎn)單的改進(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為底的對(duì)數(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è)元素的長(zhǎng)度都是有很多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億bit，n=50億，如果按出錯(cuò)率0.01算需要的大概是650億個(gè) bit。 現(xiàn)在可用的是340億，相差并不多，這樣可能會(huì)使出錯(cuò)率上升些。另外如果這些urlip是一一對(duì)應(yīng)的，就可以轉(zhuǎn)換成ip，則大大簡(jiǎn)單了。

海量數(shù)據(jù)處理專題（三）——Hash

【什么是Hash】 
  Hash，一般翻譯做“散列”，也有直接音譯為“哈?！钡?，就是把任意長(zhǎng)度的輸入（又叫做預(yù)映射， pre-image），通過散列算法，變換成固定長(zhǎng)度的輸出，該輸出就是散列值。這種轉(zhuǎn)換是一種壓縮映射，也就是，散列值的空間通常遠(yuǎn)小于輸入的空間，不 同的輸入可能會(huì)散列成相同的輸出，而不可能從散列值來唯一的確定輸入值。簡(jiǎn)單的說就是一種將任意長(zhǎng)度的消息壓縮到某一固定長(zhǎng)度的消息摘要的函數(shù)。 
HASH主要用于信息安全領(lǐng)域中加密算法，它把一些不同長(zhǎng)度的信息轉(zhuǎn)化成雜亂的128位的編碼,這些編碼值叫做HASH值. 也可以說，hash就是找到一種數(shù)據(jù)內(nèi)容和數(shù)據(jù)存放地址之間的映射關(guān)系。 
  數(shù)組的特點(diǎn)是：尋址容易，插入和刪除困難；而鏈表的特點(diǎn)是：尋址困難，插入和刪除容易。那么我們能不能綜合兩者的特性，做出一種尋址容易，插入刪除也容易 的數(shù)據(jù)結(jié)構(gòu)？答案是肯定的，這就是我們要提起的哈希表，哈希表有多種不同的實(shí)現(xiàn)方法，我接下來解釋的是最常用的一種方法——拉鏈法，我們可以理解為“鏈表 的數(shù)組”，如圖： 

 很明顯，用斐波那契散列法調(diào)整之后要比原來的取摸散列法好很多。 

【適用范圍】 
快速查找，刪除的基本數(shù)據(jù)結(jié)構(gòu)，通常需要總數(shù)據(jù)量可以放入內(nèi)存。 
【基本原理及要點(diǎn)】 
hash函數(shù)選擇，針對(duì)字符串，整數(shù)，排列，具體相應(yīng)的hash方法。 
碰撞處理，一種是open hashing，也稱為拉鏈法；另一種就是closed hashing，也稱開地址法，opened addressing。 
【擴(kuò)展】 
d-left hashing中的d是多個(gè)的意思，我們先簡(jiǎn)化這個(gè)問題，看一看2-left hashing。2-left hashing指的是將一個(gè)哈希表分成長(zhǎng)度相等的兩半，分別叫做T1和T2，給T1和T2分別配備一個(gè)哈希函數(shù)，h1和h2。在存儲(chǔ)一個(gè)新的key時(shí)，同 時(shí)用兩個(gè)哈希函數(shù)進(jìn)行計(jì)算，得出兩個(gè)地址h1[key]和h2[key]。這時(shí)需要檢查T1中的h1[key]位置和T2中的h2[key]位置，哪一個(gè) 位置已經(jīng)存儲(chǔ)的（有碰撞的）key比較多，然后將新key存儲(chǔ)在負(fù)載少的位置。如果兩邊一樣多，比如兩個(gè)位置都為空或者都存儲(chǔ)了一個(gè)key，就把新key 存儲(chǔ)在左邊的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ì)。

海量數(shù)據(jù)處理專題（四）——Bit-map

【什么是Bit-map】 
所謂的Bit-map就是用一個(gè)bit位來標(biāo)記某個(gè)元素對(duì)應(yīng)的Value， 而Key即是該元素。由于采用了Bit為單位來存儲(chǔ)數(shù)據(jù)，因此在存儲(chǔ)空間方面，可以大大節(jié)省。 
如果說了這么多還沒明白什么是Bit-map，那么我們來看一個(gè)具體的例子，假設(shè)我們要對(duì)0-7內(nèi)的5個(gè)元素(4,7,2,5,3)排序（這里假設(shè)這些元 素沒有重復(fù)）。那么我們就可以采用Bit-map的方法來達(dá)到排序的目的。要表示8個(gè)數(shù)，我們就只需要8個(gè)Bit（1Bytes），首先我們開辟 1Byte的空間，將這些空間的所有Bit位都置為0(如下圖：) 

 

然后我們現(xiàn)在遍歷一遍Bit區(qū)域，將該位是一的位的編號(hào)輸出（2，3，4，5，7），這樣就達(dá)到了排序的目的。下面的代碼給出了一個(gè)BitMap的用法：排序。 

C代碼：

//定義每個(gè)Byte中有8個(gè)Bit位  
     #include ＜memory.h＞  
     #define BYTESIZE 8  
     void SetBit(char *p, int posi)  
     {  
         for(int i=0; i ＜ (posi/BYTESIZE); i++)  
         {  
             p++;  
         }  
        
         *p = *p|(0x01＜＜(posi%BYTESIZE));//將該Bit位賦值1  
         return;  
     }  
        
     void BitMapSortDemo()  
     {  
         //為了簡(jiǎn)單起見，我們不考慮負(fù)數(shù)  
         int num[] = {3,5,2,10,6,12,8,14,9};  
        
         //BufferLen這個(gè)值是根據(jù)待排序的數(shù)據(jù)中最大值確定的  
 //待排序中的最大值是14，因此只需要2個(gè)Bytes(16個(gè)Bit)  
 //就可以了。  
         const int BufferLen = 2;  
         char *pBuffer = new char[BufferLen];  
        
         //要將所有的Bit位置為0，否則結(jié)果不可預(yù)知。  
         memset(pBuffer,0,BufferLen);  
         for(int i=0;i＜9;i++)  
         {  
             //首先將相應(yīng)Bit位上置為1  
             SetBit(pBuffer,num[i]);  
         }  
        
         //輸出排序結(jié)果  
         for(int i=0;i＜BufferLen;i++)//每次處理一個(gè)字節(jié)(Byte)  
         {  
             for(int j=0;j＜BYTESIZE;j++)//處理該字節(jié)中的每個(gè)Bit位  
             {  
                 //判斷該位上是否是1，進(jìn)行輸出，這里的判斷比較笨。  
 //首先得到該第j位的掩碼（0x01＜＜j），將內(nèi)存區(qū)中的  
 //位和此掩碼作與操作。最后判斷掩碼是否和處理后的  
 //結(jié)果相同  
                 if((*pBuffer&(0x01＜＜j)) == (0x01＜＜j))  
                 {  
                     printf("%d ",i*BYTESIZE + j);  
                 }  
             }  
             pBuffer++;  
         }  
     }  
        
     int _tmain(int argc, _TCHAR* argv[])  
     {  
         BitMapSortDemo();  
         return 0;  
     }

【適用范圍】 

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

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

使用bit數(shù)組來表示某些元素是否存在，比如8位電話號(hào)碼 

【擴(kuò)展】 

Bloom filter可以看做是對(duì)bit-map的擴(kuò)展 

【問題實(shí)例】 

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

8位最多99 999 999，大概需要99m個(gè)bit，大概10幾m字節(jié)的內(nèi)存即可。 （可以理解為從0-99 999 999的數(shù)字，每個(gè)數(shù)字對(duì)應(yīng)一個(gè)Bit位，所以只需要99M個(gè)Bit==1.2MBytes，這樣，就用了小小的1.2M左右的內(nèi)存表示了所有的8位數(shù)的 電話） 

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次及以上，在遍歷這些數(shù)的時(shí)候，如果對(duì)應(yīng)位置的值是 0，則將其置為1；如果是1，將其置為2；如果是2，則保持不變?；蛘呶覀儾挥?bit來進(jìn)行表示，我們用兩個(gè)bit-map即可模擬實(shí)現(xiàn)這個(gè)2bit- map，都是一樣的道理。 

【什么是堆】
概念：堆是一種特殊的二叉樹，具備以下兩種性質(zhì)
1）每個(gè)節(jié)點(diǎn)的值都大于（或者都小于，稱為最小堆）其子節(jié)點(diǎn)的值
2）樹是完全平衡的，并且最后一層的樹葉都在最左邊
這樣就定義了一個(gè)最大堆。如下圖用一個(gè)數(shù)組來表示堆：

那么下面介紹二叉堆：二叉堆是一種完全二叉樹，其任意子樹的左右節(jié)點(diǎn)（如果有的話）的鍵值一定比根節(jié)點(diǎn)大，上圖其實(shí)就是一個(gè)二叉堆。

你一定發(fā)覺了，最小的一個(gè)元素就是數(shù)組第一個(gè)元素，那么二叉堆這種有序隊(duì)列如何入隊(duì)呢？看圖：

假設(shè)要在這個(gè)二叉堆里入隊(duì)一個(gè)單元，鍵值為2，那只需在數(shù)組末尾加入這個(gè)元素，然后盡可能把這個(gè)元素往上挪，直到挪不動(dòng)，經(jīng)過了這種復(fù)雜度為Ο(logn)的操作，二叉堆還是二叉堆。

那如何出隊(duì)呢？也不難，看圖：

出隊(duì)一定是出數(shù)組的第一個(gè)元素，這么來第一個(gè)元素以前的位置就成了空位，我們需要把這個(gè)空位挪至葉子節(jié)點(diǎn)，然后把數(shù)組最后一個(gè)元素插入這個(gè)空位，把這個(gè)“空位”盡量往上挪。這種操作的復(fù)雜度也是Ο(logn)。

【適用范圍】
海量數(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ù)據(jù)處理專題（六）

【什么是雙層桶】  
事實(shí)上，與其說雙層桶劃分是一種數(shù)據(jù)結(jié)構(gòu)，不如說它是一種算法設(shè)計(jì)思想。面對(duì)一堆大量的數(shù)據(jù)我們無法處理的時(shí)候，我們可以將其分成一個(gè)個(gè)小的單元，然后根據(jù)一定的策略來處理這些小單元，從而達(dá)到目的。

【適用范圍】 
第k大，中位數(shù)，不重復(fù)或重復(fù)的數(shù)字

【基本原理及要點(diǎn)】 
因?yàn)樵胤秶艽?，不能利用直接尋址表，所以通過多次劃分，逐步確定范圍，然后最后在一個(gè)可以接受的范圍內(nèi)進(jìn)行?？梢酝ㄟ^多次縮小，雙層只是一個(gè)例子，分治才是其根本（只是“只分不治”）。

【擴(kuò)展】 
當(dāng)有時(shí)候需要用一個(gè)小范圍的數(shù)據(jù)來構(gòu)造一個(gè)大數(shù)據(jù)，也是可以利用這種思想，相比之下不同的，只是其中的逆過程。

【問題實(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就可以直接解決了。也就是說只要有足夠的磁盤空間，就可以很方便的解決。 當(dāng)然這個(gè)題也可以用我們前面講過的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ì)了。

3).現(xiàn)在有一個(gè)0-30000的隨機(jī)數(shù)生成器。請(qǐng)根據(jù)這個(gè)隨機(jī)數(shù)生成器，設(shè)計(jì)一個(gè)抽獎(jiǎng)范圍是0-350000彩票中獎(jiǎng)號(hào)碼列表，其中要包含20000個(gè)中獎(jiǎng)號(hào)碼。

這個(gè)題剛好和上面兩個(gè)思想相反，一個(gè)0到3萬的隨機(jī)數(shù)生成器要生成一個(gè)0到35萬的隨機(jī)數(shù)。那么我們完全可以將0-35萬的區(qū)間分成35/3=12 個(gè)區(qū) 間，然后每個(gè)區(qū)間的長(zhǎng)度都小于等于3萬，這樣我們就可以用題目給的隨機(jī)數(shù)生成器來生成了，然后再加上該區(qū)間的基數(shù)。那么要每個(gè)區(qū)間生成多少個(gè)隨機(jī)數(shù)呢？計(jì) 算公式就是：區(qū)間長(zhǎng)度*隨機(jī)數(shù)密度，在本題目中就是30000*（20000/350000）。最后要注意一點(diǎn)，該題目是有隱含條件的：彩票，這意味著你 生成的隨機(jī)數(shù)里面不能有重復(fù)，這也是我為什么用雙層桶劃分思想的另外一個(gè)原因。

海量數(shù)據(jù)處理專題（七）——數(shù)據(jù)庫索引及優(yōu)化

索引是對(duì)數(shù)據(jù)庫表中一列或多列的值進(jìn)行排序的一種結(jié)構(gòu)，使用索引可快速訪問數(shù)據(jù)庫表中的特定信息。

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

什么是索引

　　數(shù)據(jù)庫索引好比是一本書前面的目錄，能加快數(shù)據(jù)庫的查詢速度。
　　例如這樣一個(gè)查詢：select * from table1 where id=44。如果沒有索引，必須遍歷整個(gè)表，直到ID等于44的這一行被找到為止；有了索引之后(必須是在ID這一列上建立的索引)，直接在索引里面找 44（也就是在ID這一列找），就可以得知這一行的位置，也就是找到了這一行?？梢?，索引是用來定位的。
　　索引分為聚簇索引和非聚簇索引兩種，聚簇索引 是按照數(shù)據(jù)存放的物理位置為順序的，而非聚簇索引就不一樣了；聚簇索引能提高多行檢索的速度，而非聚簇索引對(duì)于單行的檢索很快。

概述

　　建立索引的目的是加快對(duì)表中記錄的查找或排序。
　　為表設(shè)置索引要付出代價(jià)的：一是增加了數(shù)據(jù)庫的存儲(chǔ)空間，二是在插入和修改數(shù)據(jù)時(shí)要花費(fèi)較多的時(shí)間(因?yàn)樗饕惨S之變動(dòng))。

B樹索引-Sql Server索引方式

為什么要?jiǎng)?chuàng)建索引

　　創(chuàng)建索引可以大大提高系統(tǒng)的性能。
　　　　第一，通過創(chuàng)建唯一性索引，可以保證數(shù)據(jù)庫表中每一行數(shù)據(jù)的唯一性。
　　　　第二，可以大大加快數(shù)據(jù)的檢索速度，這也是創(chuàng)建索引的最主要的原因。
　　　　第三，可以加速表和表之間的連接，特別是在實(shí)現(xiàn)數(shù)據(jù)的參考完整性方面特別有意義。
　　　　第四，在使用分組和排序子句進(jìn)行數(shù)據(jù)檢索時(shí)，同樣可以顯著減少查詢中分組和排序的時(shí)間。
　　　　第五，通過使用索引，可以在查詢的過程中，使用優(yōu)化隱藏器，提高系統(tǒng)的性能。
　　也許會(huì)有人要問：增加索引有如此多的優(yōu)點(diǎn)，為什么不對(duì)表中的每一個(gè)列創(chuàng)建一個(gè)索引呢？因?yàn)?，增加索引也有許多不利的方面。
　　　　第一，創(chuàng)建索引和維護(hù)索引要耗費(fèi)時(shí)間，這種時(shí)間隨著數(shù)據(jù)量的增加而增加。
　　　　第二，索引需要占物理空間，除了數(shù)據(jù)表占數(shù)據(jù)空間之外，每一個(gè)索引還要占一定的物理空間，如果要建立聚簇索引，那么需要的空間就會(huì)更大。
　　　　第三，當(dāng)對(duì)表中的數(shù)據(jù)進(jìn)行增加、刪除和修改的時(shí)候，索引也要?jiǎng)討B(tài)的維護(hù)，這樣就降低了數(shù)據(jù)的維護(hù)速度。

在哪建索引

　　索引是建立在數(shù)據(jù)庫表中的某些列的上面。在創(chuàng)建索引的時(shí)候，應(yīng)該考慮在哪些列上可以創(chuàng)建索引，在哪些列上不能創(chuàng)建索引。一般來說，應(yīng)該在這些列上創(chuàng)建索引：
　　在經(jīng)常需要搜索的列上，可以加快搜索的速度；
　　在作為主鍵的列上，強(qiáng)制該列的唯一性和組織表中數(shù)據(jù)的排列結(jié)構(gòu)；
　　在經(jīng)常用在連接的列上，這些列主要是一些外鍵，可以加快連接的速度；在經(jīng)常需要根據(jù)范圍進(jìn)行搜索的列上創(chuàng)建索引，因?yàn)樗饕呀?jīng)排序，其指定的范圍是連續(xù)的；
　　在經(jīng)常需要排序的列上創(chuàng)建索引，因?yàn)樗饕呀?jīng)排序，這樣查詢可以利用索引的排序，加快排序查詢時(shí)間；
　　在經(jīng)常使用在WHERE子句中的列上面創(chuàng)建索引，加快條件的判斷速度。
　　同樣，對(duì)于有些列不應(yīng)該創(chuàng)建索引。一般來說，不應(yīng)該創(chuàng)建索引的的這些列具有下列特點(diǎn)：
　　第一，對(duì)于那些在查詢中很少使用或者參考的列不應(yīng)該創(chuàng)建索引。這是因?yàn)?，既然這些列很少使用到，因此有索引或者無索引，并不能提高查詢速度。相反，由于增加了索引，反而降低了系統(tǒng)的維護(hù)速度和增大了空間需求。
　　第二，對(duì)于那些只有很少數(shù)據(jù)值的列也不應(yīng)該增加索引。這是因?yàn)?，由于這些列的取值很少，例如人事表的性別列，在查詢的結(jié)果中，結(jié)果集的數(shù)據(jù)行占了表中數(shù)據(jù)行的很大比例，即需要在表中搜索的數(shù)據(jù)行的比例很大。增加索引，并不能明顯加快檢索速度。
　　第三，對(duì)于那些定義為text, image和bit數(shù)據(jù)類型的列不應(yīng)該增加索引。這是因?yàn)?，這些列的數(shù)據(jù)量要么相當(dāng)大，要么取值很少,不利于使用索引。
　　第四，當(dāng)修改性能遠(yuǎn)遠(yuǎn)大于檢索性能時(shí)，不應(yīng)該創(chuàng)建索引。這是因?yàn)?，修改性能和檢索性能是互相矛盾的。當(dāng)增加索引時(shí)，會(huì)提高檢索性能，但是會(huì)降低修改性能。當(dāng)減少索引時(shí)，會(huì)提高修改性能，降低檢索性能。因此，當(dāng)修改操作遠(yuǎn)遠(yuǎn)多于檢索操作時(shí)，不應(yīng)該創(chuàng)建索引。

數(shù)據(jù)庫優(yōu)化

　　此外，除了數(shù)據(jù)庫索引之外，在LAMP結(jié)果如此流行的今天，數(shù)據(jù)庫（尤其是MySQL）性能優(yōu)化也是海量數(shù)據(jù)處理的一個(gè)熱點(diǎn)。下面就結(jié)合自己的經(jīng)驗(yàn)，聊一聊MySQL數(shù)據(jù)庫優(yōu)化的幾個(gè)方面。
　　首先，在數(shù)據(jù)庫設(shè)計(jì)的時(shí)候，要能夠充分的利用索引帶來的性能提升，至于如何建立索引，建立什么樣的索引，在哪些字段上建立索引，上面已經(jīng)講的很清楚 了，這里不在贅述。另外就是設(shè)計(jì)數(shù)據(jù)庫的原則就是盡可能少的進(jìn)行數(shù)據(jù)庫寫操作（插入，更新，刪除等），查詢?cè)胶?jiǎn)單越好。如下：

數(shù)據(jù)庫設(shè)計(jì)

　　其次，配置緩存是必不可少的，配置緩存可以有效的降低數(shù)據(jù)庫查詢讀取次數(shù)，從而緩解數(shù)據(jù)庫服務(wù)器壓力，達(dá)到優(yōu)化的目的，一定程度上來講，這算是一個(gè) “圍魏救趙”的辦法?？膳渲玫木彺姘ㄋ饕彺?key_buffer)，排序緩存(sort_buffer)，查詢緩存(query_buffer)， 表描述符緩存(table_cache)，如下圖：

配置緩存

　　第三，切表，切表也是一種比較流行的數(shù)據(jù)庫優(yōu)化法。分表包括兩種方式：橫向分表和縱向分表，其中，橫向分表比較有使用意義，故名思議，橫向切表 就是指把記錄分到不同的表中，而每條記錄仍舊是完整的（縱向切表后每條記錄是不完整的），例如原始表中有100條記錄，我要切成2個(gè)表，那么最簡(jiǎn)單也是最 常用的方法就是ID取摸切表法，本例中，就把ID為1,3,5,7。。。的記錄存在一個(gè)表中，ID為2,4,6,8,。。。的記錄存在另一張表中。雖然橫 向切表可以減少查詢強(qiáng)度，但是它也破壞了原始表的完整性，如果該表的統(tǒng)計(jì)操作比較多，那么就不適合橫向切表。橫向切表有個(gè)非常典型的用法，就是用戶數(shù)據(jù)： 每個(gè)用戶的用戶數(shù)據(jù)一般都比較龐大，但是每個(gè)用戶數(shù)據(jù)之間的關(guān)系不大，因此這里很適合橫向切表。最后，要記住一句話就是：分表會(huì)造成查詢的負(fù)擔(dān)，因此在數(shù) 據(jù)庫設(shè)計(jì)之初，要想好是否真的適合切表的優(yōu)化：

分表

第四，日志分析，在數(shù)據(jù)庫運(yùn)行了較長(zhǎng)一段時(shí)間以后，會(huì)積累大量的LOG日志，其實(shí)這里面的蘊(yùn)涵的有用的信息量還是很大的。通過分析日志，可以找到系統(tǒng)性能的瓶頸，從而進(jìn)一步尋找優(yōu)化方案。

性能分析

以上講的都是單機(jī)MySQL的性能優(yōu)化的一些經(jīng)驗(yàn)，但是隨著信息大爆炸，單機(jī)的數(shù)據(jù)庫服務(wù)器已經(jīng)不能滿足我們的需求，于是，多多節(jié)點(diǎn)，分布式數(shù)據(jù)庫網(wǎng)絡(luò)出現(xiàn)了，其一般的結(jié)構(gòu)如下：

分布式數(shù)據(jù)庫結(jié)構(gòu)

這種分布式集群的技術(shù)關(guān)鍵就是“同步復(fù)制”。。。

海量數(shù)據(jù)處理專題（八）——倒排索引(搜索引擎之基石)

引言：

在信息大爆炸的今天，有了搜索引擎的幫助，使得我們能夠快速，便捷的找到所求。提到搜索引擎，就不得不說VSM模型，說到VSM，就不得不聊倒排索引?？梢院敛豢鋸埖闹v，倒排索引是搜索引擎的基石。

VSM檢索模型

VSM全稱是Vector Space Model(向量空間模型)，是IR(Information Retrieval信息檢索)模型中的一種，由于其簡(jiǎn)單，直觀，高效，所以被廣泛的應(yīng)用到搜索引擎的架構(gòu)中。98年的Google就是憑借這樣的一個(gè)模 型，開始了它的瘋狂擴(kuò)張之路。廢話不多說，讓我們來看看到底VSM是一個(gè)什么東東。

在開始之前，我默認(rèn)大家對(duì)線性代數(shù)里面的向量(Vector)有一定了解的。向量是既有大小又有方向的量，通常用有向線段表示，向量有：加、減、倍數(shù)、內(nèi)積、距離、模、夾角的運(yùn)算。

文檔(Document)：一個(gè)完整的信息單元，對(duì)應(yīng)的搜索引擎系統(tǒng)里，就是指一個(gè)個(gè)的網(wǎng)頁。

標(biāo)引項(xiàng)(Term)：文檔的基本構(gòu)成單位，例如在英文中可以看做是一個(gè)單詞，在中文中可以看作一個(gè)詞語。

查詢(Query)：一個(gè)用戶的輸入，一般由多個(gè)Term構(gòu)成。

那么用一句話概況搜索引擎所做的事情就是：對(duì)于用戶輸入的Query，找到最相似的Document返回給用戶。而這正是IR模型所解決的問題：

信息檢索模型是指如何對(duì)查詢和文檔進(jìn)行表示，然后對(duì)它們進(jìn)行相似度計(jì)算的框架和方法。

舉個(gè)簡(jiǎn)單的例子：

現(xiàn)在有兩篇文章(Document)分別是 “春風(fēng)來了，春天的腳步近了” 和 “春風(fēng)不度玉門關(guān)”。然后輸入的Query是“春風(fēng)”，從直觀上感覺，前者和輸入的查詢更相關(guān)一些，因?yàn)樗?個(gè)春，但這只是我們的直觀感覺，如何量 化呢，要知道計(jì)算機(jī)是門嚴(yán)謹(jǐn)?shù)膶W(xué)科^_^。這個(gè)時(shí)候，我們前面講的Term和VSM模型就派上用場(chǎng)了。

首先我們要確定向量的維數(shù)，這時(shí)候就需要一個(gè)字典庫，字典庫的大小，即是向量的維數(shù)。在該例中，字典為{春風(fēng),來了,春天, 的,腳步,近了,不度,玉門關(guān)} ，文檔向量，查詢向量如下圖：

VSM模型示例

PS:為了簡(jiǎn)單起見，這里分詞的粒度很大。

將Query和Document都量化為向量以后，那么就可以計(jì)算用戶的查詢和哪個(gè)文檔相似性更大了。簡(jiǎn)單的計(jì)算結(jié)果是D1和D2同Query的內(nèi) 積都是1，囧。當(dāng)然了，如果分詞粒度再細(xì)一些，查詢的結(jié)果就是另外一個(gè)樣子了，因此分詞的粒度也是會(huì)對(duì)查詢結(jié)果（主要是召回率和準(zhǔn)確率）造成影響的。

上述的例子是用一個(gè)很簡(jiǎn)單的例子來說明VSM模型的，計(jì)算文檔相似度的時(shí)候也是采用最原始的內(nèi)積的方法，并且只考慮了詞頻(TF)影響因子，而沒有考慮反詞頻(IDF)，而現(xiàn)在比較常用的是cos夾角法，影響因子也非常多，據(jù)傳Google的影響因子有100+之多。
大名鼎鼎的Lucene項(xiàng)目就是采用VSM模型構(gòu)建的，VSM的核心公式如下（由cos夾角法演變，此處省去推導(dǎo)過程）

VSM模型公式

從上面的例子不難看出，如果向量的維度(對(duì)漢語來將，這個(gè)值一般在30w-45w)變大，而且文檔數(shù)量(通常都是海量的)變多，那么計(jì)算一次相關(guān)性，開銷是非常大的，如何解決這個(gè)問題呢？不要忘記了我們這節(jié)的主題就是 倒排索引，主角終于粉墨登場(chǎng)了?。。?/p>

倒排索引

倒排索引非常類似我們前面提到的Hash結(jié)構(gòu)。以下內(nèi)容來自維基百科：

倒排索引（英語：Inverted index），也常被稱為反向索引、置入檔案或反向檔案，是一種索引方法，被用來存儲(chǔ)在全文搜索下某個(gè)單詞在一個(gè)文檔或者一組文檔中的存儲(chǔ)位置的映射。它是文檔檢索系統(tǒng)中最常用的數(shù)據(jù)結(jié)構(gòu)。

有兩種不同的反向索引形式：

• 一條記錄的水平反向索引（或者反向檔案索引）包含每個(gè)引用單詞的文檔的列表。
• 一個(gè)單詞的水平反向索引（或者完全反向索引）又包含每個(gè)單詞在一個(gè)文檔中的位置。

后者的形式提供了更多的兼容性（比如短語搜索），但是需要更多的時(shí)間和空間來創(chuàng)建。

由上面的定義可以知道，一個(gè)倒排索引包含一個(gè)字典的索引和所有詞的列表。其中字典索引中包含了所有的Term(通俗理解為文檔中的詞)，索引后面跟 的列表則保存該詞的信息(出現(xiàn)的文檔號(hào)，甚至包含在每個(gè)文檔中的位置信息)。下面我們還采用上面的方法舉一個(gè)簡(jiǎn)單的例子來說明倒排索引。

例如現(xiàn)在我們要對(duì)三篇文檔建立索引(實(shí)際應(yīng)用中，文檔的數(shù)量是海量的)：

文檔1(D1)：中國移動(dòng)互聯(lián)網(wǎng)發(fā)展迅速

文檔2(D2)：移動(dòng)互聯(lián)網(wǎng)未來的潛力巨大

文檔3(D3)：中華民族是個(gè)勤勞的民族

那么文檔中的詞典集合為：{中國，移動(dòng)，互聯(lián)網(wǎng)，發(fā)展，迅速，未來，的，潛力，巨大，中華，民族，是，個(gè)，勤勞}

建好的索引如下圖：

倒排索引

在上面的索引中，存儲(chǔ)了兩個(gè)信息，文檔號(hào)和出現(xiàn)的次數(shù)。建立好索引以后，我們就可以開始查詢了。例如現(xiàn)在有一個(gè)Query是”中國移動(dòng)”。首先分詞 得到Term集合{中國，移動(dòng)}，查倒排索引，分別計(jì)算query和d1,d2,d3的距離。有沒有發(fā)現(xiàn)，倒排表建立好以后，就不需要在檢索整個(gè)文檔庫， 而是直接從字典集合中找到“中國”和“移動(dòng)”，然后遍歷后面的列表直接計(jì)算。

對(duì)倒排索引結(jié)構(gòu)我們已經(jīng)有了初步的了解，但在實(shí)際應(yīng)用中還有些需要解決的問題(主要是由海量數(shù)據(jù)引起的)。筆者列舉一些問題，并給出相應(yīng)的解決方案，拋磚以引玉，希望大家可以展開討論：

1.左側(cè)的索引表如何建立?怎么做才能最高效？

可能有人不假思索回答：左側(cè)的索引當(dāng)然要采取hash結(jié)構(gòu)啊，這樣可以快速的定位到字典項(xiàng)。但是這樣問題又來了，hash函數(shù)如何選取呢？而且 hash是有碰撞的，但是倒排表似乎又是不允許碰撞的存在的。事實(shí)上，雖然倒排表和hash異常的相思，但是兩者還是有很大區(qū)別的，其實(shí)在這里我們可以采 用前面提到的Bitmap的思想，每個(gè)Term(單詞)對(duì)應(yīng)一個(gè)位置(當(dāng)然了，這里不是一個(gè)比特位)，而且是一一對(duì)應(yīng)的。如何能夠做到呢，一般在文字處理 中，有很多的編碼，漢字中的GBK編碼基本上就可以包含所有用到的漢字，每個(gè)漢字的GBK編碼是確定的，因此一個(gè)Term的”ID”也就確定了，從而可以 做到快速定位。注：得到一個(gè)漢字的GBK號(hào)是非?？斓倪^程，可以理解為O(1)的時(shí)間復(fù)雜度。

2.如何快速的添加刪除更新索引？

有經(jīng)驗(yàn)的碼農(nóng)都知道，一般在系統(tǒng)的“做加法”的代價(jià)比“做減法”的代價(jià)要低很多，在搜索引擎中中也不例外。因此，在倒排表中，遇到要?jiǎng)h除一個(gè)文檔，其實(shí)不是真正的刪除，而是將其標(biāo)記刪除。這樣一個(gè)減法操作的代價(jià)就比較小了。

3.那么多的海量文檔，如果存儲(chǔ)呢？有么有什么備份策略呢？

當(dāng)然了，一臺(tái)機(jī)器是存儲(chǔ)不下的，分布式存儲(chǔ)是采取的。一般的備份保存3份就足夠了。