（一）——開篇

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

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

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

Bloom Filter

Hash

Bit-Map

堆(Heap)

雙層桶劃分

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

倒排索引（Inverted Index）

外排序

Trie樹

MapReduce

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

（二）——Bloom Filter

【什么是Bloom Filter】

Bloom Filter是一種空間效率很高的隨機數(shù)據(jù)結(jié)構(gòu)，它利用位數(shù)組很簡潔地表示一個集合肝断，并能判斷一個元素是否屬于這個集合杈曲。Bloom Filter的這種高效是有一定代價的：在判斷一個元素是否屬于某個集合時，有可能會把不屬于這個集合的元素誤認為屬于這個集合（false positive）胸懈。因此鱼蝉，Bloom Filter不適合那些“零錯誤”的應(yīng)用場合。而在能容忍低錯誤率的應(yīng)用場合下箫荡，Bloom Filter通過極少的錯誤換取了存儲空間的極大節(jié)省。 這里有一篇關(guān)于Bloom Filter的詳細介紹渔隶，不太懂的博友可以看看羔挡。

【適用范圍】

可以用來實現(xiàn)數(shù)據(jù)字典洁奈，進行數(shù)據(jù)的判重，或者集合求交集

【基本原理及要點】

對于原理來說很簡單绞灼，位數(shù)組+k個獨立hash函數(shù)利术。將hash函數(shù)對應(yīng)的值的位數(shù)組置1，查找時如果發(fā)現(xiàn)所有hash函數(shù)對應(yīng)位都是1說明存在低矮，很明顯這 個過程并不保證查找的結(jié)果是100%正確的印叁。同時也不支持刪除一個已經(jīng)插入的關(guān)鍵字，因為該關(guān)鍵字對應(yīng)的位會牽動到其他的關(guān)鍵字军掂。所以一個簡單的改進就是 counting Bloom filter轮蜕，用一個counter數(shù)組代替位數(shù)組，就可以支持刪除了蝗锥。

還有一個比較重要的問題跃洛，如 何根據(jù)輸入元素個數(shù)n，確定位數(shù)組m的大小及hash函數(shù)個數(shù)终议。當hash函數(shù)個數(shù)k=(ln2)*(m/n)時錯誤率最小汇竭。在錯誤率不大于E的情況 下，m至少要等于n*lg(1/E)才能表示任意n個元素的集合穴张。但m還應(yīng)該更大些细燎，因為還要保證bit數(shù)組里至少一半為0，則m應(yīng) 該>=nlg(1/E)*lge 大概就是nlg(1/E)1.44倍(lg表示以2為底的對數(shù))皂甘。

舉個例子我們假設(shè)錯誤率為0.01玻驻，則此時m應(yīng)大概是n的13倍。這樣k大概是8個叮贩。

注意這里m與n的單位不同击狮，m是bit為單位，而n則是以元素個數(shù)為單位(準確的說是不同元素的個數(shù))益老。通常單個元素的長度都是有很多bit的彪蓬。所以使用bloom filter內(nèi)存上通常都是節(jié)省的。

【擴展】

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

【問題實例】

給你A,B兩個文件态坦，各存放50億條URL盐数，每條URL占用64字節(jié)，內(nèi)存限制是4G伞梯，讓你找出A,B文件共同的URL玫氢。如果是三個乃至n個文件呢帚屉？

根據(jù)這個問題我們來計算下內(nèi)存的占用，4G=2^32大概是40億*8大概是340億bit漾峡，n=50億攻旦，如果按出錯率0.01算需要的大概是650億個bit。 現(xiàn)在可用的是340億生逸，相差并不多牢屋，這樣可能會使出錯率上升些。另外如果這些urlip是一一對應(yīng)的槽袄，就可以轉(zhuǎn)換成ip烙无，則大大簡單了。

（三）——Hash

【什么是Hash】

Hash掰伸，一般翻譯做“散列”皱炉，也有直接音譯為“哈希”的狮鸭，就是把任意長度的輸入（又叫做預(yù)映射合搅， pre-image），通過散列算法歧蕉，變換成固定長度的輸出灾部，該輸出就是散列值。這種轉(zhuǎn)換是一種壓縮映射惯退，也就是赌髓，散列值的空間通常遠小于輸入的空間，不同的輸入可能會散列成相同的輸出催跪，而不可能從散列值來唯一的確定輸入值锁蠕。簡單的說就是一種將任意長度的消息壓縮到某一固定長度的消息摘要的函數(shù)。

HASH主要用于信息安全領(lǐng)域中加密算法懊蒸，它把一些不同長度的信息轉(zhuǎn)化成雜亂的128位的編碼,這些編碼值叫做HASH值. 也可以說荣倾，hash就是找到一種數(shù)據(jù)內(nèi)容和數(shù)據(jù)存放地址之間的映射關(guān)系。

數(shù)組的特點是：尋址容易骑丸，插入和刪除困難舌仍；而鏈表的特點是：尋址困難，插入和刪除容易通危。那么我們能不能綜合兩者的特性铸豁，做出一種尋址容易，插入刪除也容易的數(shù)據(jù)結(jié)構(gòu)菊碟？答案是肯定的节芥，這就是我們要提起的哈希表，哈希表有多種不同的實現(xiàn)方法逆害，我接下來解釋的是最常用的一種方法——拉鏈法藏古，我們可以理解為“鏈表的數(shù)組”增炭，如圖：

左邊很明顯是個數(shù)組，數(shù)組的每個成員包括一個指針拧晕，指向一個鏈表的頭，當然這個鏈表可能為空梅垄，也可能元素很多厂捞。我們根據(jù)元素的一些特征把元素分配到不同的鏈表中去，也是根據(jù)這些特征队丝，找到正確的鏈表靡馁，再從鏈表中找出這個元素。

元素特征轉(zhuǎn)變?yōu)閿?shù)組下標的方法就是散列法机久。散列法當然不止一種臭墨，下面列出三種比較常用的。

1膘盖，除法散列法

最直觀的一種胧弛，上圖使用的就是這種散列法，公式：

index = value % 16

學(xué)過匯編的都知道侠畔，求模數(shù)其實是通過一個除法運算得到的结缚，所以叫“除法散列法”。

2软棺，平方散列法

求index是非常頻繁的操作红竭，而乘法的運算要比除法來得省時（對現(xiàn)在的CPU來說，估計我們感覺不出來）喘落，所以我們考慮把除法換成乘法和一個位移操作茵宪。公式：

index = (value * value) >> 28

如果數(shù)值分配比較均勻的話這種方法能得到不錯的結(jié)果，但我上面畫的那個圖的各個元素的值算出來的index都是0——非常失敗瘦棋。也許你還有個問題稀火，value如果很大，value * value不會溢出嗎兽狭？答案是會的憾股，但我們這個乘法不關(guān)心溢出，因為我們根本不是為了獲取相乘結(jié)果箕慧，而是為了獲取index服球。

3，斐波那契（Fibonacci）散列法

平方散列法的缺點是顯而易見的颠焦，所以我們能不能找出一個理想的乘數(shù)斩熊，而不是拿value本身當作乘數(shù)呢？答案是肯定的伐庭。

1粉渠，對于16位整數(shù)而言分冈，這個乘數(shù)是40503

2，對于32位整數(shù)而言霸株，這個乘數(shù)是2654435769

3雕沉，對于64位整數(shù)而言，這個乘數(shù)是11400714819323198485

這幾個“理想乘數(shù)”是如何得出來的呢去件？這跟一個法則有關(guān)坡椒，叫黃金分割法則，而描述黃金分割法則的最經(jīng)典表達式無疑就是著名的斐波那契數(shù)列尤溜，如果你還有興趣倔叼，就到網(wǎng)上查找一下“斐波那契數(shù)列”等關(guān)鍵字，我數(shù)學(xué)水平有限宫莱，不知道怎么描述清楚為什么丈攒，另外斐波那契數(shù)列的值居然和太陽系八大行星的軌道半徑的比例出奇吻合，很神奇授霸，對么巡验？

對我們常見的32位整數(shù)而言，公式：

i ndex = (value * 2654435769) >> 28

如果用這種斐波那契散列法的話绝葡，那我上面的圖就變成這樣了：

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

【適用范圍】

快速查找藏畅，刪除的基本數(shù)據(jù)結(jié)構(gòu)敷硅，通常需要總數(shù)據(jù)量可以放入內(nèi)存。

【基本原理及要點】

hash函數(shù)選擇愉阎，針對字符串绞蹦，整數(shù)，排列榜旦，具體相應(yīng)的hash方法幽七。

碰撞處理，一種是open hashing溅呢，也稱為拉鏈法澡屡；另一種就是closed hashing，也稱開地址法咐旧，opened addressing驶鹉。

【擴展】

d-left hashing中的d是多個的意思，我們先簡化這個問題铣墨，看一看2-left hashing室埋。2-left hashing指的是將一個哈希表分成長度相等的兩半，分別叫做T1和T2，給T1和T2分別配備一個哈希函數(shù)姚淆，h1和h2孕蝉。在存儲一個新的key時，同 時用兩個哈希函數(shù)進行計算腌逢，得出兩個地址h1[key]和h2[key]降淮。這時需要檢查T1中的h1[key]位置和T2中的h2[key]位置，哪一個 位置已經(jīng)存儲的（有碰撞的）key比較多搏讶，然后將新key存儲在負載少的位置骤肛。如果兩邊一樣多，比如兩個位置都為空或者都存儲了一個key窍蓝，就把新key 存儲在左邊的T1子表中，2-left也由此而來繁成。在查找一個key時吓笙，必須進行兩次hash，同時查找兩個位置巾腕。

【問題實例】

1).海量日志數(shù)據(jù)面睛，提取出某日訪問百度次數(shù)最多的那個IP。

IP的數(shù)目還是有限的尊搬，最多2^32個叁鉴，所以可以考慮使用hash將ip直接存入內(nèi)存，然后進行統(tǒng)計佛寿。

（四）——Bit-map

【什么是Bit-map】

所謂的Bit-map就是用一個bit位來標記某個元素對應(yīng)的Value幌墓， 而Key即是該元素。由于采用了Bit為單位來存儲數(shù)據(jù)冀泻，因此在存儲空間方面常侣，可以大大節(jié)省。

如果說了這么多還沒明白什么是Bit-map弹渔，那么我們來看一個具體的例子胳施，假設(shè)我們要對0-7內(nèi)的5個元素(4,7,2,5,3)排序（這里假設(shè)這些元素沒有重復(fù)）。那么我們就可以采用Bit-map的方法來達到排序的目的肢专。要表示8個數(shù)舞肆，我們就只需要8個Bit（1Bytes），首先我們開辟1Byte的空間博杖，將這些空間的所有Bit位都置為0(如下圖：)

然后遍歷這5個元素椿胯，首先第一個元素是4，那么就把4對應(yīng)的位置為1（可以這樣操作 p+(i/8)|(0x01<<(i%8)) 當然了這里的操作涉及到Big-ending和Little-ending的情況欧募，這里默認為Big-ending）,因為是從零開始的压状，所以要把第五位置為一（如下圖）：

然后再處理第二個元素7，將第八位置為1,，接著再處理第三個元素种冬，一直到最后處理完所有的元素镣丑，將相應(yīng)的位置為1，這時候的內(nèi)存的Bit位的狀態(tài)如下：

然后我們現(xiàn)在遍歷一遍Bit區(qū)域娱两，將該位是一的位的編號輸出（2莺匠，3，4十兢，5趣竣，7），這樣就達到了排序的目的旱物。下面的代碼給出了一個BitMap的用法：排序遥缕。

【適用范圍】

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

【基本原理及要點】

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

【擴展】

Bloom filter可以看做是對bit-map的擴展

【問題實例】

1)已知某個文件內(nèi)包含一些電話號碼宝穗，每個號碼為8位數(shù)字户秤，統(tǒng)計不同號碼的個數(shù)。

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

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

將bit-map擴展一下糖荒，用2bit表示一個數(shù)即可，0表示未出現(xiàn)蜘矢，1表示出現(xiàn)一次综看，2表示出現(xiàn)2次及以上，在遍歷這些數(shù)的時候舞吭，如果對應(yīng)位置的值是0，則將其置為1羡鸥；如果是1，將其置為2惧浴；如果是2存和，則保持不變≈月茫或者我們不用2bit來進行表示捐腿，我們用兩個bit-map即可模擬實現(xiàn)這個2bit-map，都是一樣的道理柿顶。

（五）——堆

【什么是堆】

概念：堆是一種特殊的二叉樹茄袖，具備以下兩種性質(zhì)

1）每個節(jié)點的值都大于（或者都小于，稱為最小堆）其子節(jié)點的值

2）樹是完全平衡的嘁锯，并且最后一層的樹葉都在最左邊

這樣就定義了一個最大堆绞佩。如下圖用一個數(shù)組來表示堆：

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

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

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

那如何出隊呢雄家？也不難，看圖：

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

【適用范圍】

海量數(shù)據(jù)前n大峦筒，并且n比較小物喷，堆可以放入內(nèi)存

【基本原理及要點】

最大堆求前n小，最小堆求前n大尉辑。方法隧魄，比如求前n小，我們比較當前元素與最大堆里的最大元素狮含，如果它小于最大元素辉川，則應(yīng)該替換那個最大元 素乓旗。這樣最后得到的n個元素就是最小的n個汇跨。適合大數(shù)據(jù)量穷遂，求前n小，n的大小比較小的情況中剩，這樣可以掃描一遍即可得到所有的前n元素掠剑，效率很高。

【擴展】

雙堆眠寿，一個最大堆與一個最小堆結(jié)合澜公，可以用來維護中位數(shù)。

【問題實例】

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

用一個100個元素大小的最小堆即可间学。

（六）雙層桶

【什么是雙層桶】

事實上低葫，與其說雙層桶劃分是一種數(shù)據(jù)結(jié)構(gòu)嘿悬，不如說它是一種算法設(shè)計思想窒盐。面對一堆大量的數(shù)據(jù)我們無法處理的時候，我們可以將其分成一個個小的單元源内，然后根據(jù)一定的策略來處理這些小單元呻此，從而達到目的掌唾。

【適用范圍】

第k大糯彬，中位數(shù)，不重復(fù)或重復(fù)的數(shù)字

【基本原理及要點】

因為元素范圍很大，不能利用直接尋址表泉手，所以通過多次劃分斩萌，逐步確定范圍，然后最后在一個可以接受的范圍內(nèi)進行姆吭』啵可以通過多次縮小答倡，雙層只是一個例子获茬，分治才是其根本（只是“只分不治”）。

【擴展】

當有時候需要用一個小范圍的數(shù)據(jù)來構(gòu)造一個大數(shù)據(jù)，也是可以利用這種思想实蓬，相比之下不同的，只是其中的逆過程酌伊。

【問題實例】

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

有 點像鴿巢原理奏候，整數(shù)個數(shù)為2^32,也就是循集，我們可以將這2^32個數(shù)，劃分為2^8個區(qū)域(比如用單個文件代表一個區(qū)域)鼻由，然后將數(shù)據(jù)分離到不同的區(qū) 域，然后不同的區(qū)域在利用bitmap就可以直接解決了厚棵。也就是說只要有足夠的磁盤空間蕉世，就可以很方便的解決彬犯。 當然這個題也可以用我們前面講過的BitMap方法解決，正所謂條條大道通羅馬~~~

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

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

實 際上，如果不是int是int64睡腿，我們可以經(jīng)過3次這樣的劃分即可降低到可以接受的程度船万。即可以先將int64分成2^24個區(qū)域狮荔，然后確定區(qū)域的第幾 大數(shù)爵憎，在將該區(qū)域分成2^20個子區(qū)域沥寥，然后確定是子區(qū)域的第幾大數(shù)，然后子區(qū)域里的數(shù)的個數(shù)只有2^20，就可以直接利用direct addr table進行統(tǒng)計了萝勤。

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

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

（七）——數(shù)據(jù)庫索引及優(yōu)化

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

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

什么是索引

數(shù)據(jù)庫索引好比是一本書前面的目錄，能加快數(shù)據(jù)庫的查詢速度李丰。

例如這樣一個查詢：select * from table1 where id=44苦锨。如果沒有索引，必須遍歷整個表趴泌，直到ID等于44的這一行被找到為止舟舒；有了索引之后(必須是在ID這一列上建立的索引)，直接在索引里面找44（也就是在ID這一列找）嗜憔，就可以得知這一行的位置秃励，也就是找到了這一行〖罚可見夺鲜，索引是用來定位的。

索引分為聚簇索引和非聚簇索引兩種呐舔，聚簇索引 是按照數(shù)據(jù)存放的物理位置為順序的币励，而非聚簇索引就不一樣了；聚簇索引能提高多行檢索的速度珊拼，而非聚簇索引對于單行的檢索很快食呻。

概述

建立索引的目的是加快對表中記錄的查找或排序。

為表設(shè)置索引要付出代價的：一是增加了數(shù)據(jù)庫的存儲空間澎现，二是在插入和修改數(shù)據(jù)時要花費較多的時間(因為索引也要隨之變動)搁进。

B樹索引-Sql Server索引方式

為什么要創(chuàng)建索引

創(chuàng)建索引可以大大提高系統(tǒng)的性能。

第一昔头，通過創(chuàng)建唯一性索引饼问，可以保證數(shù)據(jù)庫表中每一行數(shù)據(jù)的唯一性。

第二揭斧，可以大大加快數(shù)據(jù)的檢索速度莱革，這也是創(chuàng)建索引的最主要的原因峻堰。

第三，可以加速表和表之間的連接盅视，特別是在實現(xiàn)數(shù)據(jù)的參考完整性方面特別有意義捐名。

第四，在使用分組和排序子句進行數(shù)據(jù)檢索時闹击，同樣可以顯著減少查詢中分組和排序的時間镶蹋。

第五，通過使用索引赏半，可以在查詢的過程中贺归，使用優(yōu)化隱藏器，提高系統(tǒng)的性能断箫。

也許會有人要問：增加索引有如此多的優(yōu)點拂酣，為什么不對表中的每一個列創(chuàng)建一個索引呢？因為仲义，增加索引也有許多不利的方面婶熬。

第一，創(chuàng)建索引和維護索引要耗費時間埃撵，這種時間隨著數(shù)據(jù)量的增加而增加赵颅。

第二，索引需要占物理空間暂刘，除了數(shù)據(jù)表占數(shù)據(jù)空間之外性含，每一個索引還要占一定的物理空間，如果要建立聚簇索引鸳惯，那么需要的空間就會更大商蕴。

第三，當對表中的數(shù)據(jù)進行增加芝发、刪除和修改的時候绪商，索引也要動態(tài)的維護，這樣就降低了數(shù)據(jù)的維護速度辅鲸。

在哪建索引

索引是建立在數(shù)據(jù)庫表中的某些列的上面格郁。在創(chuàng)建索引的時候，應(yīng)該考慮在哪些列上可以創(chuàng)建索引独悴，在哪些列上不能創(chuàng)建索引例书。一般來說，應(yīng)該在這些列上創(chuàng)建索引：

在經(jīng)常需要搜索的列上刻炒，可以加快搜索的速度决采；

在作為主鍵的列上，強制該列的唯一性和組織表中數(shù)據(jù)的排列結(jié)構(gòu)坟奥；

在經(jīng)常用在連接的列上树瞭，這些列主要是一些外鍵拇厢，可以加快連接的速度；在經(jīng)常需要根據(jù)范圍進行搜索的列上創(chuàng)建索引晒喷，因為索引已經(jīng)排序孝偎，其指定的范圍是連續(xù)的；

在經(jīng)常需要排序的列上創(chuàng)建索引凉敲，因為索引已經(jīng)排序衣盾，這樣查詢可以利用索引的排序，加快排序查詢時間爷抓；

在經(jīng)常使用在WHERE子句中的列上面創(chuàng)建索引势决，加快條件的判斷速度。

同樣废赞，對于有些列不應(yīng)該創(chuàng)建索引。一般來說叮姑，不應(yīng)該創(chuàng)建索引的的這些列具有下列特點：

第一唉地，對于那些在查詢中很少使用或者參考的列不應(yīng)該創(chuàng)建索引。這是因為传透，既然這些列很少使用到耘沼，因此有索引或者無索引，并不能提高查詢速度朱盐。相反群嗤，由于增加了索引，反而降低了系統(tǒng)的維護速度和增大了空間需求兵琳。

第二狂秘，對于那些只有很少數(shù)據(jù)值的列也不應(yīng)該增加索引。這是因為躯肌，由于這些列的取值很少者春，例如人事表的性別列，在查詢的結(jié)果中清女，結(jié)果集的數(shù)據(jù)行占了表中數(shù)據(jù)行的很大比例钱烟，即需要在表中搜索的數(shù)據(jù)行的比例很大。增加索引嫡丙，并不能明顯加快檢索速度拴袭。

第三，對于那些定義為text, image和bit數(shù)據(jù)類型的列不應(yīng)該增加索引曙博。這是因為拥刻，這些列的數(shù)據(jù)量要么相當大，要么取值很少,不利于使用索引父泳。

第四泰佳，當修改性能遠遠大于檢索性能時盼砍，不應(yīng)該創(chuàng)建索引。這是因為逝她，修改性能和檢索性能是互相矛盾的浇坐。當增加索引時，會提高檢索性能黔宛，但是會降低修改性能近刘。當減少索引時，會提高修改性能臀晃，降低檢索性能觉渴。因此，當修改操作遠遠多于檢索操作時徽惋，不應(yīng)該創(chuàng)建索引案淋。

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

此外，除了數(shù)據(jù)庫索引之外险绘，在LAMP結(jié)果如此流行的今天踢京，數(shù)據(jù)庫（尤其是MySQL）性能優(yōu)化也是海量數(shù)據(jù)處理的一個熱點。下面就結(jié)合自己的經(jīng)驗宦棺，聊一聊MySQL數(shù)據(jù)庫優(yōu)化的幾個方面瓣距。

首先，在數(shù)據(jù)庫設(shè)計的時候代咸，要能夠充分的利用索引帶來的性能提升蹈丸，至于如何建立索引，建立什么樣的索引呐芥，在哪些字段上建立索引逻杖，上面已經(jīng)講的很清楚了，這里不在贅述思瘟。另外就是設(shè)計數(shù)據(jù)庫的原則就是盡可能少的進行數(shù)據(jù)庫寫操作（插入弧腥，更新，刪除等）潮太，查詢越簡單越好管搪。如下：

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

其次，配置緩存是必不可少的铡买，配置緩存可以有效的降低數(shù)據(jù)庫查詢讀取次數(shù)更鲁，從而緩解數(shù)據(jù)庫服務(wù)器壓力，達到優(yōu)化的目的奇钞，一定程度上來講澡为，這算是一個“圍魏救趙”的辦法【鞍＃可配置的緩存包括索引緩存(key_buffer)媒至，排序緩存(sort_buffer)顶别，查詢緩存(query_buffer)，表描述符緩存(table_cache)拒啰，如下圖：

配置緩存

第三驯绎，切表，切表也是一種比較流行的數(shù)據(jù)庫優(yōu)化法谋旦。分表包括兩種方式：橫向分表和縱向分表剩失，其中，橫向分表比較有使用意義册着，故名思議拴孤，橫向切表就是指把記錄分到不同的表中，而每條記錄仍舊是完整的（縱向切表后每條記錄是不完整的）甲捏，例如原始表中有100條記錄演熟，我要切成2個表，那么最簡單也是最常用的方法就是ID取摸切表法司顿，本例中芒粹，就把ID為1,3,5,7。免猾。是辕。的記錄存在一個表中囤热，ID為2,4,6,8,猎提。。旁蔼。的記錄存在另一張表中锨苏。雖然橫向切表可以減少查詢強度，但是它也破壞了原始表的完整性棺聊，如果該表的統(tǒng)計操作比較多伞租，那么就不適合橫向切表。橫向切表有個非常典型的用法限佩，就是用戶數(shù)據(jù)：每個用戶的用戶數(shù)據(jù)一般都比較龐大葵诈，但是每個用戶數(shù)據(jù)之間的關(guān)系不大，因此這里很適合橫向切表祟同。最后作喘，要記住一句話就是：分表會造成查詢的負擔，因此在數(shù)據(jù)庫設(shè)計之初晕城，要想好是否真的適合切表的優(yōu)化：

分表

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

性能分析

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

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

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

（八）——倒排索引(搜索引擎之基石)

引言：

在信息大爆炸的今天，有了搜索引擎的幫助掩幢，使得我們能夠快速逊拍，便捷的找到所求。提到搜索引擎际邻，就不得不說VSM模型芯丧，說到VSM，就不得不聊倒排索引世曾∮Ш悖可以毫不夸張的講，倒排索引是搜索引擎的基石轮听。

VSM檢索模型

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

在開始之前，我默認大家對線性代數(shù)里面的向量(Vector)有一定了解的掀序。向量是既有大小又有方向的量帆焕，通常用有向線段表示，向量有：加、減叶雹、倍數(shù)财饥、內(nèi)積、距離折晦、模钥星、夾角的運算。

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

標引項(Term)：文檔的基本構(gòu)成單位风喇，例如在英文中可以看做是一個單詞宁改，在中文中可以看作一個詞語。

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

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

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

舉個簡單的例子：

現(xiàn)在有兩篇文章(Document)分別是 “春風(fēng)來了倦始，春天的腳步近了” 和 “春風(fēng)不度玉門關(guān)”斗遏。然后輸入的Query是“春風(fēng)”，從直觀上感覺鞋邑，前者和輸入的查詢更相關(guān)一些诵次，因為它包含有2個春，但這只是我們的直觀感覺炫狱，如何量化呢藻懒，要知道計算機是門嚴謹?shù)膶W(xué)科^_^剔猿。這個時候视译，我們前面講的Term和VSM模型就派上用場了。

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

VSM模型示例

PS:為了簡單起見呀舔，這里分詞的粒度很大。

將Query和Document都量化為向量以后扩灯，那么就可以計算用戶的查詢和哪個文檔相似性更大了媚赖。簡單的計算結(jié)果是D1和D2同Query的內(nèi)積都是1霜瘪，囧。當然了惧磺，如果分詞粒度再細一些颖对，查詢的結(jié)果就是另外一個樣子了，因此分詞的粒度也是會對查詢結(jié)果（主要是召回率和準確率）造成影響的磨隘。

上述的例子是用一個很簡單的例子來說明VSM模型的缤底，計算文檔相似度的時候也是采用最原始的內(nèi)積的方法，并且只考慮了詞頻(TF)影響因子番捂，而沒有考慮反詞頻(IDF)个唧，而現(xiàn)在比較常用的是cos夾角法，影響因子也非常多设预，據(jù)傳Google的影響因子有100+之多坑鱼。

大名鼎鼎的Lucene項目就是采用VSM模型構(gòu)建的，VSM的核心公式如下（由cos夾角法演變絮缅，此處省去推導(dǎo)過程）

VSM模型公式

從上面的例子不難看出鲁沥，如果向量的維度(對漢語來將，這個值一般在30w-45w)變大耕魄，而且文檔數(shù)量(通常都是海量的)變多画恰，那么計算一次相關(guān)性，開銷是非常大的吸奴，如何解決這個問題呢允扇？不要忘記了我們這節(jié)的主題就是 倒排索引，主角終于粉墨登場了Ｔ虬隆？既蟆！

倒排索引

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

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

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

一條記錄的水平反向索引（或者反向檔案索引）包含每個引用單詞的文檔的列表粥脚。

一個單詞的水平反向索引（或者完全反向索引）又包含每個單詞在一個文檔中的位置。

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

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

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

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

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

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

那么文檔中的詞典集合為：{中國，移動土砂，互聯(lián)網(wǎng)州既，發(fā)展，迅速萝映，未來吴叶，的，潛力序臂，巨大蚌卤，中華，民族奥秆，是逊彭，個，勤勞}

建好的索引如下圖：

倒排索引

在上面的索引中构订，存儲了兩個信息侮叮，文檔號和出現(xiàn)的次數(shù)。建立好索引以后悼瘾，我們就可以開始查詢了囊榜。例如現(xiàn)在有一個Query是”中國移動”。首先分詞得到Term集合{中國亥宿，移動}卸勺，查倒排索引，分別計算query和d1,d2,d3的距離烫扼。有沒有發(fā)現(xiàn)曙求，倒排表建立好以后，就不需要在檢索整個文檔庫材蛛，而是直接從字典集合中找到“中國”和“移動”圆到，然后遍歷后面的列表直接計算怎抛。

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

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

可能有人不假思索回答：左側(cè)的索引當然要采取hash結(jié)構(gòu)啊掷邦，這樣可以快速的定位到字典項白胀。但是這樣問題又來了，hash函數(shù)如何選取呢抚岗？而且hash是有碰撞的或杠，但是倒排表似乎又是不允許碰撞的存在的。事實上宣蔚，雖然倒排表和hash異常的相思向抢，但是兩者還是有很大區(qū)別的，其實在這里我們可以采用前面提到的Bitmap的思想胚委，每個Term(單詞)對應(yīng)一個位置(當然了挟鸠，這里不是一個比特位)，而且是一一對應(yīng)的亩冬。如何能夠做到呢艘希，一般在文字處理中，有很多的編碼硅急，漢字中的GBK編碼基本上就可以包含所有用到的漢字覆享，每個漢字的GBK編碼是確定的，因此一個Term的”ID”也就確定了营袜，從而可以做到快速定位淹真。注：得到一個漢字的GBK號是非常快的過程连茧，可以理解為O(1)的時間復(fù)雜度核蘸。

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

有經(jīng)驗的碼農(nóng)都知道啸驯，一般在系統(tǒng)的“做加法”的代價比“做減法”的代價要低很多客扎，在搜索引擎中中也不例外。因此罚斗，在倒排表中徙鱼，遇到要刪除一個文檔，其實不是真正的刪除针姿，而是將其標記刪除袱吆。這樣一個減法操作的代價就比較小了。

3.那么多的海量文檔距淫，如果存儲呢绞绒？有么有什么備份策略呢？

當然了榕暇，一臺機器是存儲不下的蓬衡，分布式存儲是采取的喻杈。一般的備份保存3份就足夠了。

好了狰晚，倒排索引終于完工了筒饰，不足的地方請指正。謝謝

來源