01?概述

? ? 大數(shù)據(jù)必然涉及海量數(shù)據(jù)，所謂海量數(shù)據(jù)嚎卫，就是數(shù)據(jù)量太大，要么在短時間內(nèi)無法計算出結(jié)果宏榕，要么因為數(shù)據(jù)太大無法一次性裝入內(nèi)存拓诸。

????針對時間，我們可以使用巧妙的算法搭配合適的數(shù)據(jù)結(jié)構(gòu)麻昼，如bitmap/堆/trie樹等進行優(yōu)化奠支。

????針對空間，就一個辦法抚芦，大而化小胚宦，分而治之，常采用hash映射等方法燕垃。

02?hash映射

????這里的hash映射是指通過一種哈希算法，將海量數(shù)據(jù)均勻分布在對應的內(nèi)存或更小的文件中井联，這是一種分而治之的實現(xiàn)思想卜壕。

????使用Hash映射有個最重要的特點是: Hash值相同的兩個串不一定一樣，但是兩個一樣的字符串hash值一定相等（如果不相等會存在嚴重安全問題烙常，比如兩個人的賬號信息經(jīng)過哈希后映射到同一個值）轴捎。

? ? 如下所示：

????在使用hash映射的時候，選擇合適高效的Hash函數(shù)是關(guān)鍵蚕脏，選擇的不好不僅浪費空間侦副，而且效率不高，存在沖突的可能性較大驼鞭。當出現(xiàn)沖突的時候秦驯，還需要借助各種沖突檢測方法去解決。

03?bitmap

????用1個(或幾個)bit位來標記某個元素對應的value（如果是1bitmap挣棕，就只能是元素是否存在;如果是x-bitmap,還可以是元素出現(xiàn)的次數(shù)等信息）译隘。使用bit位來存儲信息，在需要的存儲空間方面可以大大節(jié)省洛心。

????應用場景有：

????1固耘、排序（如果是1-bitmap，就只能對無重復的數(shù)排序）

????2词身、判斷某個元素是否存在

? ? 例如厅目，某文件中有若干8位數(shù)字的電話號碼，要求統(tǒng)計一共有多少個不同的電話號碼？

????分析：8位最多99 999 999, 如果1Byte（8bit）表示1個號碼是否存在损敷，需要99999999Byte=99999999/1024KB=99999999/1024/1024MB≈95MB空間葫笼，但是如果采用1bit表示1個號碼是否存在，則只需要 95/8=12MB 的空間嗤锉。這時渔欢，數(shù)字k(0~99 999 999)與bit位的對應關(guān)系是：

04?Trie樹

????Trie，又叫前綴樹瘟忱，字典樹等等奥额。它有很多變種，如后綴樹访诱，Radix Tree（基樹垫挨，Linux內(nèi)核采用這種數(shù)據(jù)結(jié)構(gòu)用以實現(xiàn)快速查找）。

????與二叉查找樹不同触菜，鍵不是直接保存在節(jié)點中九榔，而是由節(jié)點在樹中的位置決定。一個節(jié)點的所有子孫都有相同的前綴涡相，也就是這個節(jié)點對應的字符串哲泊，而根節(jié)點對應空字符串。

????例如催蝗，要想實現(xiàn)某個單詞的快速查找切威，可以采用如下Trie樹將每個單詞存儲起來：

????這樣存儲的好處就在于，要想查找的時候可以根據(jù)單詞排除大量非關(guān)聯(lián)分支丙号，提高查詢速度先朦。

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

????索引使用的數(shù)據(jù)結(jié)構(gòu)多是B樹或B+樹。

??? B樹和B+樹廣泛應用于文件存儲系統(tǒng)和數(shù)據(jù)庫系統(tǒng)中犬缨，mysql使用的是B+樹喳魏，oracle使用的是B樹，Mysql也支持多種索引類型怀薛，如b-tree 索引刺彩，哈希索引，全文索引等乾戏。

????一般來說迂苛，索引本身也很大，不可能全部存儲在內(nèi)存中鼓择，因此索引往往以索引文件的形式存儲的磁盤上三幻。索引查找過程中就要產(chǎn)生磁盤I/O消耗，相對于內(nèi)存存取呐能，I/O存取的消耗要高幾個數(shù)量級念搬，所以評價一個數(shù)據(jù)結(jié)構(gòu)作為索引的優(yōu)劣最重要的指標就是在查找過程中磁盤I/O操作次數(shù)的漸進復雜度抑堡。換句話說，索引的結(jié)構(gòu)組織要盡量減少查找過程中磁盤I/O的存取次數(shù)朗徊。

06?倒排索引

????也叫反向索引首妖。是文檔檢索系統(tǒng)中最常用的數(shù)據(jù)結(jié)構(gòu)。

????倒排索引的索引表中的每一項都包含一個屬性值和具有該屬性值的各記錄的地址爷恳。因為不是由記錄來確定屬性值有缆，而是由屬性來確定記錄，因而成為倒排索引（inverted index）温亲。

????倒排列表記錄了某個單詞位于哪些文檔中棚壁。在給定的文檔語料中，一般會有多個文檔包含某單詞栈虚，每個文檔有唯一的編號（DocID）袖外，單詞在這個文檔中出現(xiàn)的次數(shù)（TF）及單詞在文檔中哪些位置出現(xiàn)等信息，與一個文檔相關(guān)的信息被稱做倒排索引項（Posting）魂务，包含這個單詞的一系列倒排索引項形成了列表結(jié)構(gòu)曼验，這就是某個單詞對應的倒排列表。

07?外排序

????外排序即對磁盤文件的排序粘姜。如果待處理的數(shù)據(jù)不能一次裝入內(nèi)存鬓照，先讀入部分數(shù)據(jù)排序后輸出到臨時文件，采用「排序-歸并」的策略孤紧。在歸并階段將這些臨時文件組合為一個大的有序文件颖杏，也即排序結(jié)果。

????例如坛芽，要對900 MB的數(shù)據(jù)進行排序，但機器上只有100 MB的可用內(nèi)存時翼抠，外歸并排序按如下方法操作：

??? 1咙轩、讀入100 MB的數(shù)據(jù)至內(nèi)存中，用某種常規(guī)方式（如快速排序阴颖、堆排序活喊、歸并排序等方法）在內(nèi)存中完成排序；

??? 2量愧、將排序完成的數(shù)據(jù)寫入磁盤钾菊；

??? 3、重復步驟1和2直到所有的數(shù)據(jù)都存入了不同的100 MB的塊（臨時文件）中偎肃，最終會產(chǎn)生9個臨時文件煞烫。

??? 4、讀入每個臨時文件的前10 MB（100 MB / (9塊 + 1)）的數(shù)據(jù)放入內(nèi)存中的輸入緩沖區(qū)累颂，最后的10 MB作為輸出緩沖區(qū)滞详；

????5凛俱、執(zhí)行九路歸并算法，將結(jié)果輸出到輸出緩沖區(qū)料饥。一旦輸出緩沖區(qū)滿蒲犬，將緩沖區(qū)中的數(shù)據(jù)寫出至目標文件，清空緩沖區(qū)岸啡。一旦9個輸入緩沖區(qū)中的一個變空原叮，就從這個緩沖區(qū)關(guān)聯(lián)的文件，讀入下一個10M數(shù)據(jù)巡蘸，除非這個文件已讀完奋隶。這是“外歸并排序”能在主存外完成排序的關(guān)鍵步驟 ：因為“歸并算法”(merge algorithm)對每一個大塊只是順序地做一輪訪問(進行歸并)，每個大塊不用完全載入主存赡若。

08?simhash算法

? ? 假設存在這樣的應用場景：快速比較兩種論文的相似程度达布，該如何設計算法？

??? simhash算法分為5個步驟：

????1逾冬、分詞：對待考察文檔進行分詞黍聂，把得到的分詞稱為特征，然后為每一個特征設置N等級別的權(quán)重身腻。如給定一段語句：“云計算通俗講義的作者程序員姜戈”产还，分詞后為：“云計算 通俗 講義 的 作者 程序員 姜戈”，然后為每個特征向量賦予權(quán)值：云計算(5)通俗(2)講義(2)的(1)作者(4)程序員(5)姜戈(5)嘀趟，權(quán)重代表了這個特征在整條語句中的重要程度脐区。

??? 2、hash：通過hash算法計算各個特征向量的hash值她按，hash值為二進制數(shù)組成的n位簽名凉泄。

????3、加權(quán)：W=hash*weight象缀，W(云計算)=101011*5=5-55-555跪削，W(作者)=100101*4=4-4-44-44。

????4陵刹、合并：將上述每個特征的加權(quán)結(jié)果累加默伍，變成一個序列串。如“5+4衰琐，-5+-4也糊，5-4,-5+4，5-4羡宙，5+4”狸剃，得到“9,-9,1,-1,1”。

??? 5狗热、降維：對于n位簽名的累加結(jié)果捕捂，如果大于0則置1瑟枫，否則置0，從而得到該語句的simhash值指攒，最后我們便可以根據(jù)不同語句simhash的海明距離來判斷它們的相似度慷妙。例如把上面計算出來的“9,-9,1,-1,1,9”降維，得到“101011”允悦，從而形成它們的simhash簽名膝擂。

09?跳躍鏈表

????跳躍鏈表對有序的鏈表附加輔助結(jié)構(gòu)，在鏈表中的查找可以快速的跳過部分結(jié)點（因此得名）隙弛。跳躍鏈表是一種隨機化數(shù)據(jù)結(jié)構(gòu)架馋，基于并聯(lián)的鏈表，其效率與RBTree相當全闷。具有簡單叉寂、高效、動態(tài)的特點总珠。查找屏鳍、增加、刪除的期望時間都是O(logN)局服。

????跳躍列表是按層建造的钓瞭。底層是一個普通的有序鏈表。每個更高層都充當下面列表的“快速跑道”淫奔，這里在層i中的元素按某個固定的概率p出現(xiàn)在層i+1中山涡。平均起來，每個元素都在1/(1-p)個列表中出現(xiàn)唆迁。

????如果需要查找元素5鸭丛，只需要遍歷1->1->3-三個節(jié)點即可，如果需要查找元素13唐责，則只需要遍歷1->7->10->13四個節(jié)點即可系吩。

????跳躍鏈表在并行計算中非常有用，數(shù)據(jù)插入可以在跳表的不同部分并行進行妒蔚，而不用全局的數(shù)據(jù)結(jié)構(gòu)重新平衡。

10?MD5算法

? ? MD5信息摘要算法（英語：MD5 Message-Digest Algorithm）月弛，一種被廣泛使用的密碼散列函數(shù)肴盏，可以產(chǎn)生出一個128位（16字節(jié)）的散列值（hash value），用于確保信息傳輸完整一致帽衙。

11?MapReduce

????MapReduce是Google提出的一個軟件架構(gòu)菜皂，用于大規(guī)模數(shù)據(jù)集（大于1TB）的并行運算。

????舉例：我們需要查找近10年內(nèi)數(shù)據(jù)庫相關(guān)論文厉萝，出現(xiàn)最多的幾個單詞恍飘，以便了解該方向發(fā)展態(tài)勢榨崩。

????如果逐個查找那么費時費力，我們可以把論文集分成N份章母，分別放到N臺機器上母蛛，一臺機器跑一個作業(yè)，這樣就可以并發(fā)執(zhí)行任務乳怎。這個方法雖然速度快彩郊，但是有部署成本，我們需要把論文集分成不重復的N份蚪缀，然后將查找程序拷貝到N臺機器秫逝，而且還需要最后把N個運行結(jié)果整合起來。這種方法比較復雜询枚，人工操作比較麻煩违帆，MapReduce就是幫助我們解決這樣拆分合并的問題，解放程序員的雙手金蜀。

??? Map函數(shù)和Reduce函數(shù)是交給用戶實現(xiàn)的刷后，這兩個函數(shù)定義了任務本身。

??? Map函數(shù)：接受一個鍵值對廉油，產(chǎn)生一組中間鍵值對惠险，Map操作是可以并發(fā)執(zhí)行的。Reduce函數(shù)：接受一個鍵抒线，以及相關(guān)的一組值班巩，將這組值進行合并產(chǎn)生一組規(guī)模更小的值（通常只有一個或零個值）。

? ? MapReduce框架會將map函數(shù)產(chǎn)生的中間鍵值對里鍵相同的值傳遞給一個reduce函數(shù)嘶炭。