13518219792
1.Bloom filter
柳河ssl適用于網站、小程序/APP、API接口等需要進行數據傳輸應用場景，ssl證書未來市場廣闊！成為成都創新互聯的ssl證書銷售渠道，可以享受市場價格4-6折優惠！如果有意向歡迎電話聯系或者加微信：028-86922220（備注：SSL證書合作）期待與您的合作！
適用范圍：可以用來實現數據字典，進行數據的判重，或者集合求交集
基本原理及要點：
對于原理來說很簡單，位數組+k個獨立hash函數。將hash函數對應的值的位數組置1，查找時如果發現所有hash函數對應位都是1說明存在，很明顯這個過程并不保證查找的結果是100%正確的。同時也不支持刪除一個已經插入的關鍵字，因為該關鍵字對應的位會牽動到其他的關鍵字。所以一個簡單的改進就是 counting Bloom filter，用一個counter數組代替位數組，就可以支持刪除了。
還有一個比較重要的問題，如何根據輸入元素個數n，確定位數組m的大小及hash函數個數。當hash函數個數k=(ln2)*(m/n)時錯誤率最小。在錯誤率不大于E的情況下，m至少要等于n*lg(1/E)才能表示任意n個元素的集合。但m還應該更大些，因為還要保證bit數組里至少一半為 0，則m 應該=nlg(1/E)*lge 大概就是nlg(1/E)1.44倍(lg表示以2為底的對數)。
舉個例子我們假設錯誤率為0.01，則此時m應大概是n的13倍。這樣k大概是8個。
注意這里m與n的單位不同，m是bit為單位，而n則是以元素個數為單位(準確的說是不同元素的個數)。通常單個元素的長度都是有很多bit的。所以使用bloom filter內存上通常都是節省的。
擴展：
Bloom filter將集合中的元素映射到位數組中，用k（k為哈希函數個數）個映射位是否全1表示元素在不在這個集合中。Counting bloom filter（CBF）將位數組中的每一位擴展為一個counter，從而支持了元素的刪除操作。Spectral Bloom Filter（SBF）將其與集合元素的出現次數關聯。SBF采用counter中的最小值來近似表示元素的出現頻率。
問題實例：給你A,B兩個文件，各存放50億條URL，每條URL占用64字節，內存限制是4G，讓你找出A,B文件共同的URL。如果是三個乃至n個文件呢？
根據這個問題我們來計算下內存的占用，4G=2^32大概是40億*8大概是340億，n=50億，如果按出錯率0.01算需要的大概是650億個 bit。現在可用的是340億，相差并不多，這樣可能會使出錯率上升些。另外如果這些urlip是一一對應的，就可以轉換成ip，則大大簡單了。
2.Hashing
適用范圍：快速查找，刪除的基本數據結構，通常需要總數據量可以放入內存
基本原理及要點：
hash函數選擇，針對字符串，整數，排列，具體相應的hash方法。
碰撞處理，一種是open hashing，也稱為拉鏈法；另一種就是closed hashing，也稱開地址法，opened addressing。 ()
擴展：
d-left hashing中的d是多個的意思，我們先簡化這個問題，看一看2-left hashing。2-left hashing指的是將一個哈希表分成長度相等的兩半，分別叫做T1和T2，給T1和T2分別配備一個哈希函數，h1和h2。在存儲一個新的key時，同時用兩個哈希函數進行計算，得出兩個地址h1[key]和h2[key]。這時需要檢查T1中的h1[key]位置和T2中的h2[key]位置，哪一個位置已經存儲的（有碰撞的）key比較多，然后將新key存儲在負載少的位置。如果兩邊一樣多，比如兩個位置都為空或者都存儲了一個key，就把新key 存儲在左邊的T1子表中，2-left也由此而來。在查找一個key時，必須進行兩次hash，同時查找兩個位置。
問題實例：
1).海量日志數據，提取出某日訪問百度次數最多的那個IP。
IP的數目還是有限的，最多2^32個，所以可以考慮使用hash將ip直接存入內存，然后進行統計。
3.bit-map
適用范圍：可進行數據的快速查找，判重，刪除，一般來說數據范圍是int的10倍以下
基本原理及要點：使用bit數組來表示某些元素是否存在，比如8位電話號碼
擴展：bloom filter可以看做是對bit-map的擴展
問題實例：
1)已知某個文件內包含一些電話號碼，每個號碼為8位數字，統計不同號碼的個數。
8位最多99 999 999，大概需要99m個bit，大概10幾m字節的內存即可。
2)2.5億個整數中找出不重復的整數的個數，內存空間不足以容納這2.5億個整數。
將bit-map擴展一下，用2bit表示一個數即可，0表示未出現，1表示出現一次，2表示出現2次及以上。或者我們不用2bit來進行表示，我們用兩個bit-map即可模擬實現這個2bit-map。
4.堆
適用范圍：海量數據前n大，并且n比較小，堆可以放入內存
基本原理及要點：最大堆求前n小，最小堆求前n大。方法，比如求前n小，我們比較當前元素與最大堆里的最大元素，如果它小于最大元素，則應該替換那個最大元素。這樣最后得到的n個元素就是最小的n個。適合大數據量，求前n小，n的大小比較小的情況，這樣可以掃描一遍即可得到所有的前n元素，效率很高。
擴展：雙堆，一個最大堆與一個最小堆結合，可以用來維護中位數。
問題實例：
1)100w個數中找最大的前100個數。
用一個100個元素大小的最小堆即可。
5.雙層桶劃分 ----其實本質上就是【分而治之】的思想，重在“分”的技巧上！
適用范圍：第k大，中位數，不重復或重復的數字
基本原理及要點：因為元素范圍很大，不能利用直接尋址表，所以通過多次劃分，逐步確定范圍，然后最后在一個可以接受的范圍內進行。可以通過多次縮小，雙層只是一個例子。
擴展：
問題實例：
1).2.5億個整數中找出不重復的整數的個數，內存空間不足以容納這2.5億個整數。
有點像鴿巢原理，整數個數為2^32,也就是，我們可以將這2^32個數，劃分為2^8個區域(比如用單個文件代表一個區域)，然后將數據分離到不同的區域，然后不同的區域在利用bitmap就可以直接解決了。也就是說只要有足夠的磁盤空間，就可以很方便的解決。
2).5億個int找它們的中位數。
這個例子比上面那個更明顯。首先我們將int劃分為2^16個區域，然后讀取數據統計落到各個區域里的數的個數，之后我們根據統計結果就可以判斷中位數落到那個區域，同時知道這個區域中的第幾大數剛好是中位數。然后第二次掃描我們只統計落在這個區域中的那些數就可以了。
實際上，如果不是int是int64，我們可以經過3次這樣的劃分即可降低到可以接受的程度。即可以先將int64分成2^24個區域，然后確定區域的第幾大數，在將該區域分成2^20個子區域，然后確定是子區域的第幾大數，然后子區域里的數的個數只有2^20，就可以直接利用direct addr table進行統計了。
6.數據庫索引
適用范圍：大數據量的增刪改查
基本原理及要點：利用數據的設計實現方法，對海量數據的增刪改查進行處理。
擴展：
問題實例：
7.倒排索引(Inverted index)
適用范圍：搜索引擎，關鍵字查詢
基本原理及要點：為何叫倒排索引？一種索引方法，被用來存儲在全文搜索下某個單詞在一個文檔或者一組文檔中的存儲位置的映射。
以英文為例，下面是要被索引的文本：
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" 將對應集合的交集。
正向索引開發出來用來存儲每個文檔的單詞的列表。正向索引的查詢往往滿足每個文檔有序頻繁的全文查詢和每個單詞在校驗文檔中的驗證這樣的查詢。在正向索引中，文檔占據了中心的位置，每個文檔指向了一個它所包含的索引項的序列。也就是說文檔指向了它包含的那些單詞，而反向索引則是單詞指向了包含它的文檔，很容易看到這個反向的關系。
擴展：
問題實例：文檔檢索系統，查詢那些文件包含了某單詞，比如常見的學術論文的關鍵字搜索。
8.外排序
適用范圍：大數據的排序，去重
基本原理及要點：外排序的歸并方法，置換選擇 敗者樹原理，最優歸并樹
擴展：
問題實例：
1).有一個1G大小的一個文件，里面每一行是一個詞，詞的大小不超過16個字節，內存限制大小是1M。返回頻數最高的100個詞。
這個數據具有很明顯的特點，詞的大小為16個字節，但是內存只有1m做hash有些不夠，所以可以用來排序。內存可以當輸入緩沖區使用。
9.trie樹
適用范圍：數據量大，重復多，但是數據種類小可以放入內存
基本原理及要點：實現方式，節點孩子的表示方式
擴展：壓縮實現。
問題實例：
1).有10個文件，每個文件1G， 每個文件的每一行都存放的是用戶的query，每個文件的query都可能重復。要你按照query的頻度排序 。
2).1000萬字符串，其中有些是相同的(重復),需要把重復的全部去掉，保留沒有重復的字符串。請問怎么設計和實現？
3).尋找熱門查詢：查詢串的重復度比較高，雖然總數是1千萬，但如果除去重復后，不超過3百萬個，每個不超過255字節。
10.分布式處理 mapreduce
適用范圍：數據量大，但是數據種類小可以放入內存
基本原理及要點：將數據交給不同的機器去處理，數據劃分，結果歸約。
擴展：
問題實例：
1).The canonical example application of MapReduce is a process to count the appearances of
each different word in a set of documents:
void map(String name, String document):
// name: document name
// document: document contents
for each word w in document:
EmitIntermediate(w, 1);
void reduce(String word, Iterator partialCounts):
// key: a word
// values: a list of aggregated partial counts
int result = 0;
for each v in partialCounts:
result += ParseInt(v);
Emit(result);
Here, each document is split in words, and each word is counted initially with a "1" value by
the Map function, using the word as the result key. The framework puts together all the pairs
with the same key and feeds them to the same call to Reduce, thus this function just needs to
sum all of its input values to find the total appearances of that word.
2).海量數據分布在100臺電腦中，想個辦法高效統計出這批數據的TOP10。
3).一共有N個機器，每個機器上有N個數。每個機器最多存O(N)個數并對它們操作。如何找到N^2個數的中數(median)？
經典問題分析
上千萬or億數據（有重復），統計其中出現次數最多的前N個數據,分兩種情況：可一次讀入內存，不可一次讀入。
可用思路：trie樹+堆，數據庫索引，劃分子集分別統計，hash，分布式計算，近似統計，外排序
所謂的是否能一次讀入內存，實際上應該指去除重復后的數據量。如果去重后數據可以放入內存，我們可以為數據建立字典，比如通過 map，hashmap，trie，然后直接進行統計即可。當然在更新每條數據的出現次數的時候，我們可以利用一個堆來維護出現次數最多的前N個數據，當然這樣導致維護次數增加，不如完全統計后在求前N大效率高。
如果數據無法放入內存。一方面我們可以考慮上面的字典方法能否被改進以適應這種情形，可以做的改變就是將字典存放到硬盤上，而不是內存，這可以參考數據庫的存儲方法。
當然還有更好的方法，就是可以采用分布式計算，基本上就是map-reduce過程，首先可以根據數據值或者把數據hash(md5)后的值，將數據按照范圍劃分到不同的機子，最好可以讓數據劃分后可以一次讀入內存，這樣不同的機子負責處理各種的數值范圍，實際上就是map。得到結果后，各個機子只需拿出各自的出現次數最多的前N個數據，然后匯總，選出所有的數據中出現次數最多的前N個數據，這實際上就是reduce過程。
實際上可能想直接將數據均分到不同的機子上進行處理，這樣是無法得到正確的解的。因為一個數據可能被均分到不同的機子上，而另一個則可能完全聚集到一個機子上，同時還可能存在具有相同數目的數據。比如我們要找出現次數最多的前100個，我們將1000萬的數據分布到10臺機器上，找到每臺出現次數最多的前 100個，歸并之后這樣不能保證找到真正的第100個，因為比如出現次數最多的第100個可能有1萬個，但是它被分到了10臺機子，這樣在每臺上只有1千個，假設這些機子排名在1000個之前的那些都是單獨分布在一臺機子上的，比如有1001個，這樣本來具有1萬個的這個就會被淘汰，即使我們讓每臺機子選出出現次數最多的1000個再歸并，仍然會出錯，因為可能存在大量個數為1001個的發生聚集。因此不能將數據隨便均分到不同機子上，而是要根據hash 后的值將它們映射到不同的機子上處理，讓不同的機器處理一個數值范圍。
而外排序的方法會消耗大量的IO，效率不會很高。而上面的分布式方法，也可以用于單機版本，也就是將總的數據根據值的范圍，劃分成多個不同的子文件，然后逐個處理。處理完畢之后再對這些單詞的及其出現頻率進行一個歸并。實際上就可以利用一個外排序的歸并過程。
另外還可以考慮近似計算，也就是我們可以通過結合自然語言屬性，只將那些真正實際中出現最多的那些詞作為一個字典，使得這個規模可以放入內存。
數據庫屬于 IO 密集型的應用程序，其主要職責就是數據的管理及存儲工作。而我們知道，從內存中讀取一個數據庫的時間是微秒級別，而從一塊普通硬盤上讀取一個IO是在毫秒級別，二者相差3個數量級。所以，要優化數據庫，首先第一步需要優化的就是 IO，盡可能將磁盤IO轉化為內存IO。本文先從 MySQL 數據庫IO相關參數(緩存參數)的角度來看看可以通過哪些參數進行IO優化：
?query_cache_size/query_cache_type (global)
Query cache 作用于整個 MySQL Instance，主要用來緩存 MySQL 中的 ResultSet，也就是一條SQL語句執行的結果集，所以僅僅只能針對select語句。當我們打開了 Query Cache 功能，MySQL在接受到一條select語句的請求后，如果該語句滿足Query Cache的要求(未顯式說明不允許使用Query Cache，或者已經顯式申明需要使用Query Cache)，MySQL 會直接根據預先設定好的HASH算法將接受到的select語句以字符串方式進行hash，然后到Query Cache 中直接查找是否已經緩存。也就是說，如果已經在緩存中，該select請求就會直接將數據返回，從而省略了后面所有的步驟(如 SQL語句的解析，優化器優化以及向存儲引擎請求數據等)，極大的提高性能。
當然，Query Cache 也有一個致命的缺陷，那就是當某個表的數據有任何任何變化，都會導致所有引用了該表的select語句在Query Cache 中的緩存數據失效。所以，當我們的數據變化非常頻繁的情況下，使用Query Cache 可能會得不償失。
Query Cache的使用需要多個參數配合，其中最為關鍵的是 query_cache_size 和 query_cache_type ，前者設置用于緩存 ResultSet 的內存大小，后者設置在何場景下使用 Query Cache。在以往的經驗來看，如果不是用來緩存基本不變的數據的MySQL數據庫，query_cache_size 一般 256MB 是一個比較合適的大小。當然，這可以通過計算Query Cache的命中率(Qcache_hits/(Qcache_hits+Qcache_inserts)*100))來進行調整。query_cache_type可以設置為0(OFF)，1(ON)或者2(DEMOND)，分別表示完全不使用query cache，除顯式要求不使用query cache(使用sql_no_cache)之外的所有的select都使用query cache，只有顯示要求才使用query cache(使用sql_cache)。
?binlog_cache_size (global)
Binlog Cache 用于在打開了二進制日志(binlog)記錄功能的環境，是 MySQL 用來提高binlog的記錄效率而設計的一個用于短時間內臨時緩存binlog數據的內存區域。
一般來說，如果我們的數據庫中沒有什么大事務，寫入也不是特別頻繁，2MB～4MB是一個合適的選擇。但是如果我們的數據庫大事務較多，寫入量比較大，可與適當調高binlog_cache_size。同時，我們可以通過binlog_cache_use 以及 binlog_cache_disk_use來分析設置的binlog_cache_size是否足夠，是否有大量的binlog_cache由于內存大小不夠而使用臨時文件(binlog_cache_disk_use)來緩存了。
?key_buffer_size (global)
Key Buffer 可能是大家最為熟悉的一個 MySQL 緩存參數了，尤其是在 MySQL 沒有更換默認存儲引擎的時候，很多朋友可能會發現，默認的 MySQL 配置文件中設置最大的一個內存參數就是這個參數了。key_buffer_size 參數用來設置用于緩存 MyISAM存儲引擎中索引文件的內存區域大小。如果我們有足夠的內存，這個緩存區域最好是能夠存放下我們所有的 MyISAM 引擎表的所有索引，以盡可能提高性能。
此外，當我們在使用MyISAM 存儲的時候有一個及其重要的點需要注意，由于 MyISAM 引擎的特性限制了他僅僅只會緩存索引塊到內存中，而不會緩存表數據庫塊。所以，我們的 SQL 一定要盡可能讓過濾條件都在索引中，以便讓緩存幫助我們提高查詢效率。
?bulk_insert_buffer_size (thread)
和key_buffer_size一樣，這個參數同樣也僅作用于使用 MyISAM存儲引擎，用來緩存批量插入數據的時候臨時緩存寫入數據。當我們使用如下幾種數據寫入語句的時候，會使用這個內存區域來緩存批量結構的數據以幫助批量寫入數據文件：
insert … select …
insert … values (…) ,(…),(…)…
load data infile… into… (非空表)
?innodb_buffer_pool_size(global)
當我們使用InnoDB存儲引擎的時候，innodb_buffer_pool_size 參數可能是影響我們性能的最為關鍵的一個參數了，他用來設置用于緩存 InnoDB 索引及數據塊的內存區域大小，類似于 MyISAM 存儲引擎的 key_buffer_size 參數，當然，可能更像是 Oracle 的 db_cache_size。簡單來說，當我們操作一個 InnoDB 表的時候，返回的所有數據或者去數據過程中用到的任何一個索引塊，都會在這個內存區域中走一遭。
和key_buffer_size 對于 MyISAM 引擎一樣，innodb_buffer_pool_size 設置了 InnoDB 存儲引擎需求最大的一塊內存區域的大小，直接關系到 InnoDB存儲引擎的性能，所以如果我們有足夠的內存，盡可將該參數設置到足夠打，將盡可能多的 InnoDB 的索引及數據都放入到該緩存區域中，直至全部。
我們可以通過 (Innodb_buffer_pool_read_requests – Innodb_buffer_pool_reads) / Innodb_buffer_pool_read_requests * 100% 計算緩存命中率，并根據命中率來調整 innodb_buffer_pool_size 參數大小進行優化。
?innodb_additional_mem_pool_size(global)
這個參數我們平時調整的可能不是太多，很多人都使用了默認值，可能很多人都不是太熟悉這個參數的作用。innodb_additional_mem_pool_size 設置了InnoDB存儲引擎用來存放數據字典信息以及一些內部數據結構的內存空間大小，所以當我們一個MySQL Instance中的數據庫對象非常多的時候，是需要適當調整該參數的大小以確保所有數據都能存放在內存中提高訪問效率的。
這個參數大小是否足夠還是比較容易知道的，因為當過小的時候，MySQL 會記錄 Warning 信息到數據庫的 error log 中，這時候你就知道該調整這個參數大小了。
?innodb_log_buffer_size (global)
這是 InnoDB 存儲引擎的事務日志所使用的緩沖區。類似于 Binlog Buffer，InnoDB 在寫事務日志的時候，為了提高性能，也是先將信息寫入 Innofb Log Buffer 中，當滿足 innodb_flush_log_trx_commit 參數所設置的相應條件(或者日志緩沖區寫滿)之后，才會將日志寫到文件(或者同步到磁盤)中。可以通過 innodb_log_buffer_size 參數設置其可以使用的最大內存空間。
注：innodb_flush_log_trx_commit 參數對 InnoDB Log 的寫入性能有非常關鍵的影響。該參數可以設置為0，1，2，解釋如下：
0：log buffer中的數據將以每秒一次的頻率寫入到log file中，且同時會進行文件系統到磁盤的同步操作，但是每個事務的commit并不會觸發任何log buffer 到log file的刷新或者文件系統到磁盤的刷新操作;
1：在每次事務提交的時候將log buffer 中的數據都會寫入到log file，同時也會觸發文件系統到磁盤的同步;
2：事務提交會觸發log buffer 到log file的刷新，但并不會觸發磁盤文件系統到磁盤的同步。此外，每秒會有一次文件系統到磁盤同步操作。
此外，MySQL文檔中還提到，這幾種設置中的每秒同步一次的機制，可能并不會完全確保非常準確的每秒就一定會發生同步，還取決于進程調度的問題。實際上，InnoDB 能否真正滿足此參數所設置值代表的意義正常 Recovery 還是受到了不同 OS 下文件系統以及磁盤本身的限制，可能有些時候在并沒有真正完成磁盤同步的情況下也會告訴 mysqld 已經完成了磁盤同步。
?innodb_max_dirty_pages_pct (global)
這個參數和上面的各個參數不同，他不是用來設置用于緩存某種數據的內存大小的一個參數，而是用來控制在 InnoDB Buffer Pool 中可以不用寫入數據文件中的Dirty Page 的比例(已經被修但還沒有從內存中寫入到數據文件的臟數據)。這個比例值越大，從內存到磁盤的寫入操作就會相對減少，所以能夠一定程度下減少寫入操作的磁盤IO。
但是，如果這個比例值過大，當數據庫 Crash 之后重啟的時間可能就會很長，因為會有大量的事務數據需要從日志文件恢復出來寫入數據文件中。同時，過大的比例值同時可能也會造成在達到比例設定上限后的 flush 操作“過猛”而導致性能波動很大。
上面這幾個參數是 MySQL 中為了減少磁盤物理IO而設計的主要參數，對 MySQL 的性能起到了至關重要的作用。
PHP 能做任何事。PHP 主要是用于服務端的腳本程序，因此您可以用 PHP 來完成任何其它的 CGI 程序能夠完成的工作，例如收集表單數據，生成動態網頁，或者發送/接收 Cookies。但 PHP 的功能遠不局限于此。
PHP 腳本主要用于以下三個領域。
服務端腳本。這是 PHP 最傳統，也是最主要的目標領域。開展這項工作您需要具備以下三點：PHP 解析器（CGI 或者服務器模塊）、WEB 服務器和 WEB 瀏覽器。您需要在運行 WEB 服務器時，安裝并配置 PHP，然后，可以用 WEB 瀏覽器來訪問 PHP 程序的輸出，即瀏覽服務端的 PHP 頁面。請查閱“安裝”一章以獲取更多信息。
命令行腳本。您可以編寫一段 PHP 腳本，并且不需要任何服務器或者瀏覽器來運行它。通過這種方式，您僅僅只需要 PHP 解析器來執行。這種用法對于依賴 cron（Unix 或者 Linux 環境）或者 Task Scheduler（Windows 環境）的日常運行的腳本來說是理想的選擇。這些腳本也可以用來處理簡單的文本。請參閱“PHP 的命令行模式”以獲取更多信息。
編寫客戶端的 GUI 應用程序。對于基于窗口式的應用程序來說，PHP 或許不是一種最好的語言，但是如果您非常精通 PHP，并且希望在您的客戶端應用程序中使用 PHP 的一些高級特性，您可以利用 PHP-GTK 來編寫這些程序。用這種方法，您還可以編寫跨平臺的應用程序。PHP-GTK 是 PHP 的一個擴展，在通常發布的 PHP 包中并不包含它。如果您對 PHP-GTK 感興趣，請訪問其網站以獲取更多信息。
本地配置好服務器，主要目的是開發、設計、調試PHP，最終還是要讓更多人看到，那就需要廣域網的空間、數據庫才能讓大家訪問得到。那就要申請空間、數據庫，也可以自己擁有服務器，把本地的數據庫上傳，把你的作品上傳。
1，html?+?css?知識，用來改模板。
2，Javascript?知識，?有一些頁面事件，特效
3，php?+?mysql?知識，用于修改程序邏輯和數據處理
4，操作系統知識：網站架構與調優
多去官網，參考手冊，二次開發入門、常量與變量、數據字典
