海量數(shù)據(jù)問題的處理方法：
1.hash map
就是把任意長度的輸入通過散列算法編程固定長度的輸出。這種轉(zhuǎn)換時一種壓縮映射
哈希表，用來快速查找刪除，通常要求總的數(shù)據(jù)量可以放入內(nèi)存，散列值空間通常要小于輸入空間，哪些問題可以用到hash表呢。
2.bit map用一個bit位來表示某個元素對應的value，而key是該元素。由于采用了bit為單位來存儲數(shù)據(jù)，因此在存儲空間方面可以大大節(jié)省。
3.bloom filter
4.heap堆是一種特殊的二叉樹，每個節(jié)點的值都大于其子節(jié)點的值，樹是完全平衡的，而且最后一層的樹葉都在最左邊，海量數(shù)據(jù)前n大，并且n比較小，堆可以放入內(nèi)存、
5.雙層桶，算法設(shè)計思想，無法處理的時候分成一個個小的單元，然后根據(jù)一定的策略來處理這些小單元，從而達到目的。第k大，中位數(shù)，不重復或重復的數(shù)字。因為元素范圍很大，不能利用直接尋址表。所以通過多次劃分逐步確定范圍，然后最后在一個可以接受的范圍內(nèi)進行，可以通過多次縮小。雙層只是一個例子，分治才是其根本。
6.數(shù)據(jù)庫索引好比是一本書前面的目錄，能加快數(shù)據(jù)庫的查詢速度，select * from table1 where id = 44如果沒有索引必須遍歷整個表，知道id等于44這一行被找到為止，有了索引以后必須是在id這一列上建立的所以，直接在索引里找44，也就是在id這一列找，就可以得知這一行的為止，也就是找到了這一行，由此可見索引是用來定位的。它還可以建立表和表之間的連接索引有這么多優(yōu)點，那是不是可以給所有類建立一個索引呢。索引的缺點有創(chuàng)建維護索引的時候肯定要消耗時間的，比如插入或刪除的時候，索引還要占據(jù)物理空間。
7.倒排索引是一種縮影方法，被用來存儲在全文搜索下某個單詞在一個文檔或者一組文檔中的存儲位置的映射。單詞指向包含的文檔，查詢包含的單詞
8.外排序外排序的歸并方法，置換選擇敗者樹，最優(yōu)歸并樹
9.B+樹，其構(gòu)建過程中引入了有序數(shù)組，從而有效降低了樹的高度，一次性取出一個連續(xù)的數(shù)組，這個操作在磁盤上比取出與數(shù)組相同數(shù)量的離散數(shù)據(jù)要便宜的多，所以磁盤上基本都是B+樹的結(jié)構(gòu)。比較次數(shù)比較少，存儲系統(tǒng)一次性要讀大塊的數(shù)據(jù)，比一次性讀小塊數(shù)據(jù)要快，這里面可以做很多事情，可以查找一個區(qū)間?？梢圆檎乙粋€數(shù)，增加一個節(jié)點很容易，復雜度可控，hash表的話性能就要下降。
10.Trie tree又稱字典樹，字典查找樹或者前綴樹，是一種用于快速檢索的多叉樹結(jié)構(gòu)，如英文字母的字典樹是一個26叉樹，數(shù)字的字典樹是一個10叉樹。適用范圍是數(shù)據(jù)量大，重復多，但是數(shù)據(jù)種類小可以放入內(nèi)存的時候。利用字符串的公共前綴來節(jié)省空間。
11.分布式mapreduce，適用范圍、：數(shù)據(jù)量大，數(shù)據(jù)種類小可以放入內(nèi)存、
海量數(shù)據(jù)案例1.
上千萬，或者億數(shù)據(jù)，里面有重復，統(tǒng)計其中出現(xiàn)次數(shù)最多的前N個數(shù)據(jù)，分兩種情況，可一次讀入內(nèi)存，不可一次讀入。
能否一次性讀入內(nèi)存是去除重復數(shù)據(jù)量，建立一個字典，hash map來進行一個統(tǒng)計。當你在更新每條數(shù)據(jù)的時候，可以用堆來維護。這樣會導致你維護的次數(shù)增多，如果你是無法放入內(nèi)存的，可以考慮能不能加以改進。出現(xiàn)次數(shù)最多的前100個。你歸并了以后不能保證找到的是真正最多的一百個。外排序會消耗大量的IO。效率不高?？梢钥紤]近似統(tǒng)計，把實際中出現(xiàn)最多的放入內(nèi)存。
設(shè)計一個可控制規(guī)模的社交網(wǎng)絡系統(tǒng)，可以查找兩個用戶之間的關(guān)系。
在數(shù)據(jù)量不大的情況下，所有數(shù)據(jù)可以存放在同一臺機器上，那查找兩個用戶的關(guān)系是單純的搜索。
當數(shù)據(jù)量大的情況下，可以用相似的思路，用hash，用戶的前幾位數(shù)字決定存儲在哪個機器上，獲得用戶的好友列表，ID機器名，再去訪問機器ID的節(jié)點。訪問另一臺機器的成本可能比較高。所以相關(guān)的數(shù)據(jù)要一次讀取完畢。節(jié)點有沒有被訪問過，防止重復的訪問，可以建立hashmap，如果用戶三層關(guān)系才可以聯(lián)系上，可以判斷兩個用戶是陌生的。
一個服務器有一個訪問，設(shè)計數(shù)據(jù)結(jié)構(gòu)可以判斷上一秒，上一分和上一小時的訪問量。
對每一個請求分配當前的一個時間戳，對時間戳進行排序，那就是有序序列。用二分查找通過快速的定位。一分鐘之內(nèi)訪問到哪里。找到了對應的request,如何知道request已經(jīng)進行了多少次請求，request可以計數(shù)，第幾個。可以知道一共發(fā)生了多少次。復雜度。二分搜索某個特定時間request是log n
電商網(wǎng)站，單個機器MVC，在初期一臺機器能承受的時候，CS和BS兩種模型，browser的協(xié)議更加標準一些。MVC是一個分層的框架。簡單的認為client提一個請求到web server上面，用一個控制器去請求數(shù)據(jù)庫和文件資源再返還給用戶。典型的網(wǎng)站結(jié)構(gòu)，開源的技術(shù)。技術(shù)的選型
login: session和cookie
web server: apache/php/nginx
mvc: templates, spring
db: mysql
登陸的時候有session表。Cookie是在瀏覽器端的設(shè)置，通過cookie傳遞給server看看session是不是存在，可以認為cookie是明碼，session是設(shè)立在服務器端的。
Nginx在異步和大規(guī)模并發(fā)的時候有很好的性能。
Mvc模板類
電商網(wǎng)站2.0版本。SOA
服務指向結(jié)構(gòu)。
Cache APP server，DB server，fileserver.
遇到性能問題，第一反應就是加cache
SOA的一些特點，
Scaling
規(guī)模，graceful degradatron平穩(wěn)地降級。
如果一個模塊比方說評論或者廣告宕機了，不能影響到整個網(wǎng)站的訪問。要保證基本的核心能保證穩(wěn)定的。
Reuse復用性。當我們搭建一些小的服務可以搭積木可以變成更強大的服務。
Ownership有責任。從設(shè)計到代碼的完成，到監(jiān)控和alert，
Simplification通過接口的方式。REST
電商網(wǎng)站3.0版本，多了一些組件，前面加了router反向代理。不同的請求放到app server上去。
海量數(shù)據(jù)案例2
聊天系統(tǒng)
facebook message wechat
工作流
Q2get new message
Pull和push，pull每隔三秒
Online status上次在線的時間。
Heart beat
每隔一分鐘，自動去update
conversation list
數(shù)據(jù)抽樣，長度為N的鏈表，不知道n有多大，遍歷一次平均概率取出k個元素。
蓄水池抽樣，保存k個元素，k+1開始
一次掃描每個元素，top k的算法。
Ab兩個文件各存放50億個url,每個占64字節(jié)，內(nèi)存限制4G，找到ab文件共同的URL，存儲到1000個小文件里，每個小文件
Bloom filter
有十個文件，每個文件1G，每一行是用戶的query,每隔query都可能重復，按照query的頻度排序
