索引是對數據庫表中一列或多列的值進行排序的一種結構，使用索引可快速訪問數據庫表中的特定信息。

數據庫索引

什么是索引

數據庫索引好比是一本書前面的目錄，能加快數據庫的查詢速度。

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

索引分為聚簇索引和非聚簇索引兩種，聚簇索引 是按照數據存放的物理位置為順序的，而非聚簇索引就不一樣了；聚簇索引能提高多行檢索的速度，而非聚簇索引對于單行的檢索很快。

概述

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

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

B樹索引-Sql Server索引方式

為什么要創建索引

創建索引可以大大提高系統的性能。

第一，通過創建唯一性索引，可以保證數據庫表中每一行數據的唯一性。
第二，可以大大加快數據的檢索速度，這也是創建索引的最主要的原因。
第三，可以加速表和表之間的連接，特別是在實現數據的參考完整性方面特別有意義。
第四，在使用分組和排序子句進行數據檢索時，同樣可以顯著減少查詢中分組和排序的時間。
第五，通過使用索引，可以在查詢的過程中，使用優化隱藏器，提高系統的性能。

也許會有人要問：增加索引有如此多的優點，為什么不對表中的每一個列創建一個索引呢？因為，增加索引也有許多不利的方面。

第一，創建索引和維護索引要耗費時間，這種時間隨著數據量的增加而增加。
第二，索引需要占物理空間，除了數據表占數據空間之外，每一個索引還要占一定的物理空間，如果要建立聚簇索引，那么需要的空間就會更大。
第三，當對表中的數據進行增加、刪除和修改的時候，索引也要動態的維護，這樣就降低了數據的維護速度。

在哪建索引

索引是建立在數據庫表中的某些列的上面。在創建索引的時候，應該考慮在哪些列上可以創建索引，在哪些列上不能創建索引。一般來說，應該在這些列上創建索引：

在經常需要搜索的列上，可以加快搜索的速度；
在作為主鍵的列上，強制該列的唯一性和組織表中數據的排列結構；
在經常用在連接的列上，這些列主要是一些外鍵，可以加快連接的速度；在經常需要根據范圍進行搜索的列上創建索引，因為索引已經排序，其指定的范圍是連續的；
在經常需要排序的列上創建索引，因為索引已經排序，這樣查詢可以利用索引的排序，加快排序查詢時間；
在經常使用在WHERE子句中的列上面創建索引，加快條件的判斷速度。

同樣，對于有些列不應該創建索引。一般來說，不應該創建索引的的這些列具有下列特點：

第一，對于那些在查詢中很少使用或者參考的列不應該創建索引。這是因為，既然這些列很少使用到，因此有索引或者無索引，并不能提高查詢速度。相反，由于增加了索引，反而降低了系統的維護速度和增大了空間需求。

第二，對于那些只有很少數據值的列也不應該增加索引。這是因為，由于這些列的取值很少，例如人事表的性別列，在查詢的結果中，結果集的數據行占了表中數據行的很大比例，即需要在表中搜索的數據行的比例很大。增加索引，并不能明顯加快檢索速度。

第三，對于那些定義為text, image和bit數據類型的列不應該增加索引。這是因為，這些列的數據量要么相當大，要么取值很少,不利于使用索引。

第四，當修改性能遠遠大于檢索性能時，不應該創建索引。這是因為，修改性能和檢索性能是互相矛盾的。當增加索引時，會提高檢索性能，但是會降低修改性能。當減少索引時，會提高修改性能，降低檢索性能。因此，當修改操作遠遠多于檢索操作時，不應該創建索引。

數據庫優化

此外，除了數據庫索引之外，在LAMP結果如此流行的今天，數據庫（尤其是MySQL）性能優化也是海量數據處理的一個熱點。下面就結合自己的經驗，聊一聊MySQL數據庫優化的幾個方面。

首先，在數據庫設計的時候，要能夠充分的利用索引帶來的性能提升，至于如何建立索引，建立什么樣的索引，在哪些字段上建立索引，上面已經講的很清楚了，這里不在贅述。另外就是設計數據庫的原則就是盡可能少的進行數據庫寫操作（插入，更新，刪除等），查詢越簡單越好。如下：

數據庫設計

其次，配置緩存是必不可少的，配置緩存可以有效的降低數據庫查詢讀取次數，從而緩解數據庫服務器壓力，達到優化的目的，一定程度上來講，這算是一個“圍魏救趙”的辦法。可配置的緩存包括索引緩存(key_buffer)，排序緩存(sort_buffer)，查詢緩存(query_buffer)，表描述符緩存(table_cache)，如下圖：

配置緩存

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

分表

第四，日志分析，在數據庫運行了較長一段時間以后，會積累大量的LOG日志，其實這里面的蘊涵的有用的信息量還是很大的。通過分析日志，可以找到系統性能的瓶頸，從而進一步尋找優化方案。

性能分析

以上講的都是單機MySQL的性能優化的一些經驗，但是隨著信息大爆炸，單機的數據庫服務器已經不能滿足我們的需求，于是，多多節點，分布式數據庫網絡出現了，其一般的結構如下：

分布式數據庫結構

這種分布式集群的技術關鍵就是“同步復制”。。。《未完待續。。。》

做人要厚道，轉載請注明出處：http://diducoder.com/mass-data-topic-7-index-and-

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

【適用范圍】
第k大，中位數，不重復或重復的數字

【基本原理及要點】
因為元素范圍很大，不能利用直接尋址表，所以通過多次劃分，逐步確定范圍，然后最后在一個可以接受的范圍內進行。可以通過多次縮小，雙層只是一個例子，分治才是其根本（只是“只分不治”）。

【擴展】
當有時候需要用一個小范圍的數據來構造一個大數據，也是可以利用這種思想，相比之下不同的，只是其中的逆過程。

【問題實例】
1).2.5億個整數中找出不重復的整數的個數，內存空間不足以容納這2.5億個整數。

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

2).5億個int找它們的中位數。

這個例子比上面那個更明顯。首先我們將int劃分為2^16個區域，然后讀取數據統計落到各個區域里的數的個數，之后我們根據統計結果就可以判斷中位數落到那個區域，同時知道這個區域中的第幾大數剛好是中位數。然后第二次掃描我們只統計落在這個區域中的那些數就可以了。

實際上，如果不是int是int64，我們可以經過3次這樣的劃分即可降低到可以接受的程度。即可以先將int64分成2^24個區域，然后確定區域的第幾 大數，在將該區域分成2^20個子區域，然后確定是子區域的第幾大數，然后子區域里的數的個數只有2^20，就可以直接利用direct addr table進行統計了。

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

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

做人好厚道，轉載請注明出處：http://diducoder.com/mass-data-topic-6-multi-dividing.html

【什么是Bit-map】

所謂的Bit-map就是用一個bit位來標記某個元素對應的Value， 而Key即是該元素。由于采用了Bit為單位來存儲數據，因此在存儲空間方面，可以大大節省。

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

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

然后再處理第二個元素7，將第八位置為1,，接著再處理第三個元素，一直到最后處理完所有的元素，將相應的位置為1，這時候的內存的Bit位的狀態如下：

然后我們現在遍歷一遍Bit區域，將該位是一的位的編號輸出（2，3，4，5，7），這樣就達到了排序的目的。下面的代碼給出了一個BitMap的用法：排序。

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

【適用范圍】

可進行數據的快速查找，判重，刪除，一般來說數據范圍是int的10倍以下

【基本原理及要點】

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

【擴展】

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

【問題實例】

1)已知某個文件內包含一些電話號碼，每個號碼為8位數字，統計不同號碼的個數。

8位最多99 999 999，大概需要99m個bit，大概10幾m字節的內存即可。 （可以理解為從0-99 999 999的數字，每個數字對應一個Bit位，所以只需要99M個Bit==12.4MBytes，這樣，就用了小小的12.4M左右的內存表示了所有的8位數的電話）

2)2.5億個整數中找出不重復的整數的個數，內存空間不足以容納這2.5億個整數。

將bit-map擴展一下，用2bit表示一個數即可，0表示未出現，1表示出現一次，2表示出現2次及以上，在遍歷這些數的時候，如果對應位置的值是0，則將其置為1；如果是1，將其置為2；如果是2，則保持不變。或者我們不用2bit來進行表示，我們用兩個bit-map即可模擬實現這個2bit-map，都是一樣的道理。

做人好厚道，轉載請注明出處：http://diducoder.com/mass-data-4-bitmap.html

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

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

你一定發覺了，最小的一個元素就是數組第一個元素，那么二叉堆這種有序隊列如何入隊呢？看圖：

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

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

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

【適用范圍】
海量數據前n大，并且n比較小，堆可以放入內存

【基本原理及要點】
最大堆求前n小，最小堆求前n大。方法，比如求前n小，我們比較當前元素與最大堆里的最大元素，如果它小于最大元素，則應該替換那個最大元 素。這樣最后得到的n個元素就是最小的n個。適合大數據量，求前n小，n的大小比較小的情況，這樣可以掃描一遍即可得到所有的前n元素，效率很高。

【擴展】
雙堆，一個最大堆與一個最小堆結合，可以用來維護中位數。

【問題實例】
1)100w個數中找最大的前100個數。
用一個100個元素大小的最小堆即可。

做人要厚道：轉載請注明出處：http://diducoder.com/mass-data-topic-5-heap.html

【什么是Hash】

Hash，一般翻譯做“散列”，也有直接音譯為“哈希”的，就是把任意長度的輸入（又叫做預映射， pre-image），通過散列算法，變換成固定長度的輸出，該輸出就是散列值。這種轉換是一種壓縮映射，也就是，散列值的空間通常遠小于輸入的空間，不同的輸入可能會散列成相同的輸出，而不可能從散列值來唯一的確定輸入值。簡單的說就是一種將任意長度的消息壓縮到某一固定長度的消息摘要的函數。

HASH主要用于信息安全領域中加密算法，它把一些不同長度的信息轉化成雜亂的128位的編碼,這些編碼值叫做HASH值. 也可以說，hash就是找到一種數據內容和數據存放地址之間的映射關系。

數組的特點是：尋址容易，插入和刪除困難；而鏈表的特點是：尋址困難，插入和刪除容易。那么我們能不能綜合兩者的特性，做出一種尋址容易，插入刪除也容易的數據結構？答案是肯定的，這就是我們要提起的哈希表，哈希表有多種不同的實現方法，我接下來解釋的是最常用的一種方法——拉鏈法，我們可以理解為“鏈表的數組”，如圖：

左邊很明顯是個數組，數組的每個成員包括一個指針，指向一個鏈表的頭，當然這個鏈表可能為空，也可能元素很多。我們根據元素的一些特征把元素分配到不同的鏈表中去，也是根據這些特征，找到正確的鏈表，再從鏈表中找出這個元素。

元素特征轉變為數組下標的方法就是散列法。散列法當然不止一種，下面列出三種比較常用的。

1，除法散列法
最直觀的一種，上圖使用的就是這種散列法，公式：
index = value % 16
學過匯編的都知道，求模數其實是通過一個除法運算得到的，所以叫“除法散列法”。

2，平方散列法
求index是非常頻繁的操作，而乘法的運算要比除法來得省時（對現在的CPU來說，估計我們感覺不出來），所以我們考慮把除法換成乘法和一個位移操作。公式：
index = (value * value) >> 28
如果數值分配比較均勻的話這種方法能得到不錯的結果，但我上面畫的那個圖的各個元素的值算出來的index都是0——非常失敗。也許你還有個問題，value如果很大，value * value不會溢出嗎？答案是會的，但我們這個乘法不關心溢出，因為我們根本不是為了獲取相乘結果，而是為了獲取index。

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

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

1，對于16位整數而言，這個乘數是40503
2，對于32位整數而言，這個乘數是2654435769
3，對于64位整數而言，這個乘數是11400714819323198485

這幾個“理想乘數”是如何得出來的呢？這跟一個法則有關，叫黃金分割法則，而描述黃金分割法則的最經典表達式無疑就是著名的斐波那契數列，如果你還有興趣，就到網上查找一下“斐波那契數列”等關鍵字，我數學水平有限，不知道怎么描述清楚為什么，另外斐波那契數列的值居然和太陽系八大行星的軌道半徑的比例出奇吻合，很神奇，對么？

對我們常見的32位整數而言，公式：
i ndex = (value * 2654435769) >> 28

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

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

【適用范圍】

快速查找，刪除的基本數據結構，通常需要總數據量可以放入內存。

【基本原理及要點】
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直接存入內存，然后進行統計。

做人要厚道，轉載請注明出處： http://diducoder.com/mass-data-topic-3-hash.html

【什么是Bloom Filter】

Bloom Filter是一種空間效率很高的隨機數據結構，它利用位數組很簡潔地表示一個集合，并能判斷一個元素是否屬于這個集合。Bloom Filter的這種高效是有一定代價的：在判斷一個元素是否屬于某個集合時，有可能會把不屬于這個集合的元素誤認為屬于這個集合（false positive）。因此，Bloom Filter不適合那些“零錯誤”的應用場合。而在能容忍低錯誤率的應用場合下，采用Bloom Filter的數據結構，可以通過極少的錯誤換取了存儲空間的極大節省。 這里有一篇關于Bloom Filter的詳細介紹，不太懂的博友可以看看。

【適用范圍】

可以用來實現數據字典，進行數據的判重，或者集合求交集

【基本原理及要點】

bloom filter位數組（集合）的初始狀態

bloom-filter-插入元素

bloom-filter-判斷元素是否屬于集合

如上圖，由于y1的三個hash index有一個不為1，因此不屬于該集合，而y2所有的hash index的位置上都為1，因此屬于該集合。

【擴展】

【問題實例】