資料庫索引演算法

① 資料庫索引原理

資料庫索引原理如下：

使用索引可快速訪問資料庫表中的特定信息。如果想按特定職員的姓來查找人員碼搏銷，則與在表中搜索所有的行相比，索引有助於更快地獲取信息。

索引的實現通常使用B樹及其變種B+樹。在數據之外，資料庫系統還維護著滿足特定查找演算法的數據結構，這些數據結構以某種方式引用（指向）數據，這樣就可以在這些數據結構上實現高級查找演算法。

(1)資料庫索引演算法擴展閱讀：

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

1、查詢很少：

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

2、少數據值：

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

3、定義類型：

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

② 資料庫索引的底層實現是什麼數據結構

索引類型：
根據資料庫的功能，可以在資料庫設計器中創建索引：唯一索引、主鍵索引和聚集索引。
盡管唯一索引有助於定位信息，但為獲得最佳性能結果，建議改用主鍵或唯一約束。

唯一索引：

UNIQUE

例如：create
unique
index
stusno
on
student（sno）；
表明此索引的每一個索引值只對應唯一的數據記錄，對於單列惟一性索引，這保證單列不包含重復的值。對於多列惟一性索引，保證多個值的組合不重復。
主鍵索引：

primary
key
資料庫表經常有一列或列組合，其值唯一標識表中的每一行。該列稱為表的主鍵。

在資料庫關系圖中為表定義主鍵將自動創森握建主鍵索引，主鍵索引是唯一索引的特定類型。該索引要求主鍵中的每個值都唯一。當在查詢中使用主鍵索引時，它還允許對數據的快速訪問。
聚集索引（也叫聚簇索引）：cluster

在聚集索引中，表中行的物理順序與鍵值的邏輯（索引）順序相同。一個表只能包含一個聚集索引。

如果某索引不是聚集索引，則表中行的物理順序與鍵值的邏輯順序不匹配。與非聚集索引相比，聚集索引通常提供更快的數據訪問速度。
索引的實現方式
1
B+樹

我們經常聽到B+樹就是這個概念，用這個樹的目的和紅黑樹差不多，也是為了盡量保持樹的平衡，當然紅黑樹是二叉樹，但B+樹就不是二叉樹了，節點下面可以有多個子節點，資料庫開發商會設置子節點數的一個最大值，這個值不會太小，所以B+樹一般來說比較矮胖，而紅黑樹就比較瘦高了。
關於B+樹的插入，刪除，會涉及到一些演算法以保持樹的平衡，這里就不詳述了。ORACLE的默認索引就是這種結構的。
如果經常需要同時對兩個欄位進行AND查詢,那麼使用兩個單獨索引不如建立一個復合索引，因為兩個單獨索引通常資料庫只能使用其中一個，而使用復合索引因為索引本身就對應到兩個欄位上的，效率會有很大提高。
2
散列索引
第二種索引叫做散列索引，就是通過散列函數來定位的一種索引，不過很少有單獨使用散列索引的，反而是散列文件組織用的比較多。
散列文件組織就是根據一個鍵通過散列計算把對應的記錄都放到同一個槽中，這樣的話相同的鍵值對應的記錄就一定是放在同一個文件里了，也就減少了文件讀取的次數，提高了效率。
散列索引呢就是根據對應鍵的散列碼來找到最終的索引項的技術，其實和B樹就差不多液仿了，也鬧春纖就是一種索引之上的二級輔助索引，我理解散列索引都是二級或更高級的稀疏索引，否則桶就太多了，效率也不會很高。
3
點陣圖索引
點陣圖索引是一種針對多個欄位的簡單查詢設計一種特殊的索引，適用范圍比較小，只適用於欄位值固定並且值的種類很少的情況，比如性別，只能有男和女，或者級別，狀態等等，並且只有在同時對多個這樣的欄位查詢時才能體現出點陣圖的優勢。
點陣圖的基本思想就是對每一個條件都用0或者1來表示，如有5條記錄，性別分別是男，女，男，男，女，那麼如果使用點陣圖索引就會建立兩個點陣圖，對應男的10110和對應女的01001,這樣做有什麼好處呢，就是如果同時對多個這種類型的欄位進行and或or查詢時，可以使用按位與和按位或來直接得到結果了。
可以參考文章：http://www.cnblogs.com/barrywxx/p/4351901.html

③ 資料庫索引的實現原理

資料庫索引的實現原理
一、概述資料庫索引，是資料庫管理系統中一個排序的數據結構，以協助快速查詢、更新資料庫表中數據。索引的實現通常使用B樹及其變種B+樹。在數據之外，資料庫系統還維護著滿足特定查找演算法的數據結構，這些數據結構以某種方式引用(指向)數據，這樣就可以在這些數據結構上實現高級查找演算法。這種數據結構，就是索引。其實說穿了，索引問題就是一個查找問題。二、索引的原理當我們的業務產生了大量的數據時，查找數據的效率問題也就隨之而來，所以我們可以通過為表設置索引，而為表設置索引要付出代價的：一是增加了資料庫的存儲空間，二是在插入和修改數據時要花費較多的時間(因為索引也要隨之變動)。
上圖展示了一種可能的索引方式。左邊是數據表，一共有兩列七條記錄，最左邊的是數據記錄的物理地址(注意邏輯上相鄰的記錄在磁碟上也並不是一定物理相鄰的)。為了加快Col2的查找，可以維護一個右邊所示的二叉查找樹，每個節點分別包含索引鍵值和一個指向對應數據記錄物理地址的指針，這樣就可以運用二叉查找在O(log2n)的復雜度內獲取到相應數據。索引是建立在資料庫表中的某些列的上面。在創建索引的時候，應該考慮在哪些列上可以創建索引，在哪些列上不能創建索引。一般來說，應該在這些列上創建索引：在經常需要搜索的列上，可以加快搜索的速度;在作為主鍵的列上，強制該列的唯一性和組織表中數據的排列結構;在經常用在連接的列上，這些列主要是一些外鍵，可以加快連接的速度;在經常需要根據范圍進行搜索的列上創建索引，因為索引已經排序，其指定的范圍是連續的;在經常需要排序的列上創建索引，因為索引已經排序，這樣查詢可以利用索引的排序，加快排序查詢時間;在經常使用在WHERE子句中的列上面創建索引，加快條件的判斷速度。創建索引可以大大提高系統的性能第一，通過創建唯一性索引，可以保證資料庫表中每一行數據的唯一性。第二，可以大大加快數據的檢索速度，這也是創建索引的最主要的原因。第三，可以加速表和表之間的連接，特別是在實現數據的參考完整性方面特別有意義。第四，在使用分組和排序子句進行數據檢索時，同樣可以顯著減少查詢中分組和排序的時間。第五，通過使用索引，可以在查詢的過程中，使用優化隱藏器，提高系統的性能。也許會有人要問：增加索引有如此多的優點，為什麼不對表中的每一個列創建一個索引呢?因為，增加索引也有許多不利的方面。創建索引的弊端第一，創建索引和維護索引要耗費時間，這種時間隨著數據量的增加而增加。第二，索引需要佔物理空間，除了數據表占數據空間之外，每一個索引還要佔一定的物理空間，如果要建立聚簇索引，那麼需要的空間就會更大。第三，當對表中的數據進行增加、刪除和修改的時候，索引也要動態的維護，這樣就降低了數據的維護速度。同樣，對於有些列不應該創建索引。一般來說，不應該創建索引的的這些列具有下列特點：第一，對於那些在查詢中很少使用或者參考的列不應該創建索引。這是因為，既然這些列很少使用到，因此有索引或者無索引，並不能提高查詢速度。相反，由於增加了索引，反而降低了系統的維護速度和增大了空間需求。第二，對於那些只有很少數據值的列也不應該增加索引。這是因為，由於這些列的取值很少，例如人事表的性別列，在查詢的結果中，結果集的數據行佔了表中數據行的很大比例，即需要在表中搜索的數據行的比例很大。增加索引，並不能明顯加快檢索速度。第三，對於那些定義為text, image和bit數據類型的列不應該增加索引。這是因為，這些列的數據量要麼相當大，要麼取值很少。第四，當修改性能遠遠大於檢索性能時，不應該創建索引。這是因為，修改性能和檢索性能是互相矛盾的。當增加索引時，會提高檢索性能，但是會降低修改性能。當減少索引時，會提高修改性能，降低檢索性能。因此，當修改性能遠遠大於檢索性能時，不應該創建索引。三、索引的類型根據資料庫的功能，可以在資料庫設計器中創建三種索引：唯一索引、主鍵索引和聚集索引。唯一索引唯一索引是不允許其中任何兩行具有相同索引值的索引。當現有數據中存在重復的鍵值時，大多數資料庫不允許將新創建的唯一索引與表一起保存。資料庫還可能防止添加將在表中創建重復鍵值的新數據。例如，如果在employee表中職員的姓(lname)上創建了唯一索引，則任何兩個員工都不能同姓。主鍵索引資料庫表經常有一列或列組合，其值唯一標識表中的每一行。該列稱為表的主鍵。在資料庫關系圖中為表定義主鍵將自動創建主鍵索引，主鍵索引是唯一索引的特定類型。該索引要求主鍵中的每個值都唯一。當在查詢中使用主鍵索引時，它還允許對數據的快速訪問。聚集索引在聚集索引中，表中行的物理順序與鍵值的邏輯(索引)順序相同。一個表只能包含一個聚集索引。如果某索引不是聚集索引，則表中行的物理順序與鍵值的邏輯順序不匹配。與非聚集索引相比，聚集索引通常提供更快的數據訪問速度。四、局部性原理與磁碟預讀由於存儲介質的特性，磁碟本身存取就比主存慢很多，再加上機械運動耗費，磁碟的存取速度往往是主存的幾百分分之一，因此為了提高效率，要盡量減少磁碟I/O。為了達到這個目的，磁碟往往不是嚴格按需讀取，而是每次都會預讀，即使只需要一個位元組，磁碟也會從這個位置開始，順序向後讀取一定長度的數據放入內存。這樣做的理論依據是計算機科學中著名的局部性原理：當一個數據被用到時，其附近的數據也通常會馬上被使用。程序運行期間所需要的數據通常比較集中。由於磁碟順序讀取的效率很高(不需要尋道時間，只需很少的旋轉時間)，因此對於具有局部性的程序來說，預讀可以提高I/O效率。預讀的長度一般為頁(page)的整倍數。頁是計算機管理存儲器的邏輯塊，硬體及操作系統往往將主存和磁碟存儲區分割為連續的大小相等的塊，每個存儲塊稱為一頁(在許多操作系統中，頁得大小通常為4k)，主存和磁碟以頁為單位交換數據。當程序要讀取的數據不在主存中時，會觸發一個缺頁異常，此時系統會向磁碟發出讀盤信號，磁碟會找到數據的起始位置並向後連續讀取一頁或幾頁載入內存中，然後異常返回，程序繼續運行。五、B樹和B+樹數據結構1、B樹B樹中每個節點包含了鍵值和鍵值對於的數據對象存放地址指針，所以成功搜索一個對象可以不用到達樹的葉節點。成功搜索包括節點內搜索和沿某一路徑的搜索，成功搜索時間取決於關鍵碼所在的層次以及節點內關鍵碼的數量。在B樹中查找給定關鍵字的方法是：首先把根結點取來，在根結點所包含的關鍵字K1,…,kj查找給定的關鍵字(可用順序查找或二分查找法)，若找到等於給定值的關鍵字，則查找成功;否則，一定可以確定要查的關鍵字在某個Ki或Ki+1之間，於是取Pi所指的下一層索引節點塊繼續查找，直到找到，或指針Pi為空時查找失敗。2、B+樹B+樹非葉節點中存放的關鍵碼並不指示數據對象的地址指針，非也節點只是索引部分。所有的葉節點在同一層上，包含了全部關鍵碼和相應數據對象的存放地址指針，且葉節點按關鍵碼從小到大順序鏈接。如果實際數據對象按加入的順序存儲而不是按關鍵碼次數存儲的話，葉節點的索引必須是稠密索引，若實際數據存儲按關鍵碼次序存放的話，葉節點索引時稀疏索引。B+樹有2個頭指針，一個是樹的根節點，一個是最小關鍵碼的葉節點。所以 B+樹有兩種搜索方法：一種是按葉節點自己拉起的鏈表順序搜索。一種是從根節點開始搜索，和B樹類似，不過如果非葉節點的關鍵碼等於給定值，搜索並不停止，而是繼續沿右指針，一直查到葉節點上的關鍵碼。所以無論搜索是否成功，都將走完樹的所有層。B+ 樹中，數據對象的插入和刪除僅在葉節點上進行。這兩種處理索引的數據結構的不同之處：1、B樹中同一鍵值不會出現多次，並且它有可能出現在葉結點，也有可能出現在非葉結點中。而B+樹的鍵一定會出現在葉結點中，並且有可能在非葉結點中也有可能重復出現，以維持B+樹的平衡。2、因為B樹鍵位置不定，且在整個樹結構中只出現一次，雖然可以節省存儲空間，但使得在插入、刪除操作復雜度明顯增加。B+樹相比來說是一種較好的折中。3、B樹的查詢效率與鍵在樹中的位置有關，最大時間復雜度與B+樹相同(在葉結點的時候)，最小時間復雜度為1(在根結點的時候)。而B+樹的時候復雜度對某建成的樹是固定的。六、B/+Tree索引的性能分析到這里終於可以分析B-/+Tree索引的性能了。上文說過一般使用磁碟I/O次數評價索引結構的優劣。先從B-Tree分析，根據B-Tree的定義，可知檢索一次最多需要訪問h個節點。資料庫系統的設計者巧妙利用了磁碟預讀原理，將一個節點的大小設為等於一個頁，這樣每個節點只需要一次I/O就可以完全載入。為了達到這個目的，在實際實現B-Tree還需要使用如下技巧：每次新建節點時，直接申請一個頁的空間，這樣就保證一個節點物理上也存儲在一個頁里，加之計算機存儲分配都是按頁對齊的，就實現了一個node只需一次I/O。B-Tree中一次檢索最多需要h-1次I/O(根節點常駐內存)，漸進復雜度為O(h)=O(logdN)。一般實際應用中，出度d是非常大的數字，通常超過100，因此h非常小(通常不超過3)。而紅黑樹這種結構，h明顯要深的多。由於邏輯上很近的節點(父子)物理上可能很遠，無法利用局部性，所以紅黑樹的I/O漸進復雜度也為O(h)，效率明顯比B-Tree差很多。綜上所述，用B-Tree作為索引結構效率是非常高的。

④ MySQL索引

MySQL的Innodb存儲引擎的索引分為聚集索引和非聚集索引兩大類

特點：B+樹葉子節點存儲行數據

一個表中，必須有一個聚集索引，只能有一個聚集索引，Innodb通常把一個表的主鍵索引作為聚集索引，如果沒有主鍵InnoDB會選擇一個唯一索引代替。如果沒有這樣的索引，InnoDB會隱式的定義一個主鍵來作為聚集索引，這個欄位為6個位元組，類型為長整形。
利用主鍵索引查找行數據是最快的，建議使用自增主鍵原因是利於索引樹的構建（主鍵自增寫入時新游跡插入的數據不會影響到原有頁，插入效率高；但是如果主鍵是無序的或者隨機的，那每次的插入可能會導致原有頁頻繁的分裂，影響插入效率）

特點：B+樹葉子空磨凳節點存儲主鍵ID

一個表中可以有多個非聚集索引，每個非聚集索引即是一棵B+樹
通過非聚集索引查找數據時，需要先在非聚集索引上找到主鍵ID，再從聚集索引獲取行數據，這個過程就稱之為回表

B樹索引中的B樹實際上是B+樹，至於為什麼使用B+樹而不使用B樹或者紅黑樹的原因在另外的文章中有提及。

特點：

特點：類似JDK中的HashMap，但無法支持范圍查詢

特點：使用的演算法仍然是B樹索引，不同的就是索引列的值必須唯一

對於普通索引來說，查找到滿足條件的第一個記錄後，需要查找下一個記錄，直到碰到第一個不滿足條件的記錄。
對於唯一索引來說，由於索引定義了唯一性，查找到第一個滿足條件的記錄後，就會停止繼續檢索，提升索引性能

另外插入行時會構建該唯一索引，假如索引值重復將插入失敗，適合業務上做唯一性檢驗

通過建立倒排索引，可以極大的提升檢索效率,解決判斷欄位是否包含的問題，但是業務上一般都不採用這種索引，斗旅而是使用ES處理全文搜索需求

僅對某個特定欄位建立的索引，如(biz_id)

對多個欄位建立的索引，如(biz_id,type)

⑤ 什麼是資料庫表的索引

索引是對資料庫表中一列或埋譽友多列的值進行排序的一種結構，使用索引可快速訪問資料庫表中的特彎槐定信息。
索引是對虛芹資料庫表中一個或多個列（例如，employee 表的姓名 (name) 列）的值進行排序的結構。如果想按特定職員的姓來查找他或她，則與在表中搜索所有的行相比，索引有助於更快地獲取信息。
例如這樣一個查詢：select * from table1 where id=10000。如果沒有索引，必須遍歷整個表，直到ID等於10000的這一行被找到為止；有了索引之後(必須是在ID這一列上建立的索引)，即可在索引中查找。由於索引是經過某種演算法優化過的，因而查找次數要少的多。可見，索引是用來定位的。
參考資料：http://ke..com/view/2079871.htm

⑥ 資料庫索引是什麼，有什麼用，怎麼用

下面是關於資料庫索引的相關知識：

1. 簡單來說，資料庫索引就是資料庫的數據結構！進一步說則是該數據結構中存儲了一張表中猜耐鏈某一列的所有值，也就是說索引是基於數據表中畝枝的某一列創建的。總而言之：一個索引是由表中某一列上的數據組成，並且這些數據存儲在某個數據結構中。

4.例如這樣一個查詢：select * from table1 where id=10000。如果沒有索引，必須遍歷整個表，直到ID等於10000的這一行被找到為止；有了索引之後(必須是在ID這一列上建立的索引)，即可在索引中查找。由於索引是經過某種演算法優化過的，因而查找次數要少的多。可見，索引是用來定位的。

5.從數據搜索實現的角度來看，索引也是另外一類文件/記錄，它包含著可以指示出相關數據記錄的各種記錄。其中，每一索引都有一個相對應的搜索碼，字元段的任意一個子集都能夠形成一個搜索碼。這樣，索引就相當於所有數據目錄項的一個集合，它能為既定的搜索碼值的所有數據目錄項提供定位所需的各種有效支持