http://m.oschina.net/blog/10314
一、引言
對資料庫索引的關注從未淡出我的們的讨論，那麼資料庫索引是什麼樣的？聚集索引與非聚集索引有什麼不同？希望本文對各位同仁有一定的幫助。有不少存疑的地方，誠心希望各位不吝賜教指正，共同進步。[最近首頁之争沸沸揚揚，也不知道這個放在這合适麼，苦勞？功勞？……]
二、 B-Tree
我們常見的資料庫系統，其索引使用的資料結構多是 B-Tree 或者 B+Tree 。例如， MsSql 使用的是 B+Tree ， Oracle 及 Sysbase 使用的是 B-Tree 。是以在最開始，簡單地介紹一下 B-Tree 。
B-Tree 不同于 Binary Tree （二叉樹，最多有兩個子樹），一棵 M 階的 B-Tree 滿足以下條件：
1 ）每個結點至多有 M 個孩子；
2 ）除根結點和葉結點外，其它每個結點至少有 M/2 個孩子；
3 ）根結點至少有兩個孩子（除非該樹僅包含一個結點）；
4 ）所有葉結點在同一層，葉結點不包含任何關鍵字資訊；
5 ）有 K 個關鍵字的非葉結點恰好包含 K+1 個孩子；
另外，對于一個結點，其内部的關鍵字是從小到大排序的。以下是 B-Tree （ M=4 ）的樣例：
對于每個結點，主要包含一個關鍵字數組 Key[] ，一個指針數組（指向兒子） Son[] 。在 B-Tree 内，查找的流程是：使用順序查找（數組長度較短時）或折半查找方法查找 Key[] 數組，若找到關鍵字 K ，則傳回該結點的位址及 K在 Key[] 中的位置；否則，可确定 K 在某個 Key 和 Key[i+1] 之間，則從 Son 所指的子結點繼續查找，直到在某結點中查找成功；或直至找到葉結點且葉結點中的查找仍不成功時，查找過程失敗。
接着，我們使用以下圖檔示範如何生成 B-Tree （ M=4 ，依次插入 1~6 ）：
從圖可見，當我們插入關鍵字 4 時，由于原結點已經滿了，故進行分裂，基本按一半的原則進行分裂，然後取出中間的關鍵字 2 ，更新（這裡是成為根結點）。其它的依類推，就是這樣一個大概的過程。
三、資料庫索引
1 ．什麼是索引
在資料庫中，索引的含義與日常意義上的“索引”一詞并無多大差別（想想小時候查字典），它是用于提高資料庫表資料通路速度的資料庫對象。
A ）索引可以避免全表掃描。多數查詢可以僅掃描少量索引頁及資料頁，而不是周遊所有資料頁。
B ） 對于非聚集索引，有些查詢甚至可以不通路資料頁。
C ） 聚集索引可以避免資料插入操作集中于表的最後一個資料頁。
D ） 一些情況下，索引還可用于避免排序操作。
當然，衆所周知，雖然索引可以提高查詢速度，但是它們也會導緻資料庫系統更新資料的性能下降，因為大部分資料更新需要同時更新索引。
2. 索引的存儲
一條索引記錄中包含的基本資訊包括：鍵值（即你定義索引時指定的所有字段的值） + 邏輯指針 （指向資料頁或者另一索引頁）。
當你為一張空表建立索引時，資料庫系統将為你配置設定一個索引頁，該索引頁在你插入資料前一直是空的。此頁此時既是根結點，也是葉結點。每當你往表中插入一行資料，資料庫系統即向此根結點中插入一行索引記錄。當根結點滿時，資料庫系統大抵按以下步驟進行分裂：
A ）建立兩個兒子結點
B ）将原根結點中的資料近似地拆成兩半，分别寫入新的兩個兒子結點
C ）根結點中加上指向兩個兒子結點的指針
通常狀況下，由于索引記錄僅包含索引字段值（以及 4-9 位元組的指針），索引實體比真實的資料行要小許多，索引頁相較資料頁來說要密集許多。一個索引頁可以存儲數量更多的索引記錄，這意味着在索引中查找時在 I/O 上占很大的優勢，了解這一點有助于從本質上了解使用索引的優勢。
3 ．索引的類型
A ） 聚集索引，表資料按照索引的順序來存儲的。對于聚集索引，葉子結點即存儲了真實的資料行，不再有另外單獨的資料頁。
B ） 非聚集索引，表資料存儲順序與索引順序無關。對于非聚集索引，葉結點包含索引字段值及指向資料頁資料行的邏輯指針，該層緊鄰資料頁，其行數量與資料表行資料量一緻。
在一張表上隻能建立一個聚集索引，因為真實資料的實體順序隻可能是一種。如果一張表沒有聚集索引，那麼它被稱為 “ 堆集 ” （ Heap ）。這樣的表中的資料行沒有特定的順序，所有的新行将被添加的表的末尾位置。
4 ．聚集索引
在聚集索引中，葉結點也即資料結點，所有資料行的存儲順序與索引的存儲順序一緻。
1 ）聚集索引與查詢操作
如上圖，我們在名字字段上建立聚集索引，當需要在根據 此字段 查找特定的記錄時，資料庫系統會根據 特定的系統表 查找的此索引的根，然後根據指針查找下一個，直到找到。例如我們要查詢“ Green ”，由于 它介于[Bennet,Karsen] ，據此我們找到了索引頁 1007 ，在該頁中 “Green” 介于 [Greane , Hunter] 間 ，據此我們找到葉結點 1133 （也即資料結點），并最終在此頁中找以了目标資料行。
此次查詢的 IO 包括 3 個索引頁的查詢（其中最後一次實際上是在資料頁中查詢）。這裡的查找可能是從磁盤讀取 (Physical Read) 或是從緩存中讀取 (Logical Read) ，如果此表通路頻率較高，那麼索引樹中較高層的索引很可能在緩存中被找到。是以真正的 IO 可能小于上面的情況。
2 ）聚集索引與插入操作
最簡單的情況下，插入操作根據索引找到對應的資料頁，然後通過挪動已有的記錄為新資料騰出空間，最後插入資料。
如果資料頁已滿，則需要拆分資料頁（頁拆分是一種耗費資源的操作，一般資料庫系統中會有相應的機制要盡量減少頁拆分的次數，通常是通過為每頁預留白間來實作）：
A ） 在該使用的資料段（ extent ）上配置設定新的資料頁，如果資料段已滿，則需要配置設定新段。
B ） 調整索引指針，這需要将相應的索引頁讀入記憶體并加鎖。
C ） 大約有一半的資料行被歸入新的資料頁中。
D ） 如果表還有非聚集索引，則需要更新這些索引指向新的資料頁。
特殊情況：
A ） 如果新插入的一條記錄包含很大的資料，可能會配置設定兩個新資料頁，其中之一用來存儲新記錄，另一存儲從原頁中拆分出來的資料。
B ） 通常資料庫系統中會将重複的資料記錄存儲于相同的頁中。
C ） 類似于自增列為聚集索引的，資料庫系統可能并不拆分資料頁，頁隻是簡單的新添資料頁。
3 ）聚集索引與删除操作
删除行将導緻其下方的資料行向上移動以填充删除記錄造成的空白。
如果删除的行是該資料頁中的最後一行，那麼該資料頁将被回收，相應的索引頁中的記錄将被删除。如果回收的資料頁位于跟該表的其它資料頁相同的段上，那麼它可能在随後的時間内被利用。如果該資料頁是該段的唯一一個資料頁，則該段也被回收。
對于資料的删除操作，可能導緻索引頁中僅有一條記錄，這時，該記錄可能會被移至鄰近的索引頁中，原索引頁将被回收，即所謂的“索引合并”。
5 ．非聚集索引
非聚集索引與聚集索引相比：
A ） 葉子結點并非資料結點
B ） 葉子結點為每一真正的資料行存儲一個 “ 鍵 - 指針 ” 對
C ） 葉子結點中還存儲了一個指針偏移量，根據頁指針及指針偏移量可以定位到具體的資料行。
D ） 類似的，在除葉結點外的其它索引結點，存儲的也是類似的内容，隻不過它是指向下一級的索引頁的。
聚集索引是一種稀疏索引，資料頁上一級的索引頁存儲的是頁指針，而不是行指針。而對于非聚集索引，則是密集索引，在資料頁的上一級索引頁它為每一個資料行存儲一條索引記錄。
對于根與中間級的索引記錄，它的結構包括：
A ） 索引字段值
B ） RowId （即對應資料頁的頁指針 + 指針偏移量）。在高層的索引頁中包含 RowId 是為了當索引允許重複值時，當更改資料時精确定位資料行。
C ） 下一級索引頁的指針
對于葉子層的索引對象，它的結構包括：
B ） RowId
1 ）非聚集索引與查詢操作
針對上圖，如果我們同樣查找“ Green ”，那麼一次查詢操作将包含以下 IO ： 3 個索引頁的讀取 +1 個資料頁的讀取。 同樣，由于緩存的關系，真實的 IO 實際可能要小于上面列出的。
2 ）非聚集索引與插入操作
如果一張表包含一個非聚集索引但沒有聚集索引，則新的資料将被插入到最末一個資料頁中，然後非聚集索引将被更新。如果也包含聚集索引，該聚集索引将被用于查找新行将要處于什麼位置，随後，聚集索引、以及非聚集索引将被更新。
3 ）非聚集索引與删除操作
如果在 删除指令的 Where 子句中包含的列上，建有非聚集索引，那麼該非聚集索引将被用于查找資料行的位置，資料删除之後，位于索引葉子上的對應記錄也将被删除。如果該表上有其它非聚集索引，則它們葉子結點上的相應資料也要删除。
如果删除的資料是該數所頁中的唯一一條，則該頁也被回收，同時需要更新各個索引樹上的指針。
由于沒有自動的合并功能，如果應用程式中有頻繁的随機删除操作，最後可能導緻表包含多個資料頁，但每個頁中隻有少量資料。
6 ．索引覆寫
索引覆寫是這樣一種索引政策：當某一查詢中包含的所需字段皆包含于一個索引中，此時索引将大大提高查詢性能。
包含多個字段的索引，稱為複合索引。索引最多可以包含 31 個字段，索引記錄最大長度為 600B 。如果你在若幹個字段上建立了一個複合的非聚集索引，且你的查詢中所需S elect 字段及 Where,Order By,Group By,Having 子句中所涉及的字段都包含在索引中，則隻搜尋索引頁即可滿足查詢，而不需要通路資料頁。由于非聚集索引的葉結點包含所有資料行中的索引列值，使用這些結點即可傳回真正的資料，這種情況稱之為 “ 索引覆寫 ” 。
在索引覆寫的情況下，包含兩種索引掃描：
A） 比對索引掃描
B） 非比對索引掃描
1 ）比對索引掃描
此類索引掃描可以讓我們省去通路資料頁的步驟，當查詢僅傳回一行資料時，性能提高是有限的，但在範圍查詢的情況下，性能提高将随結果集數量的增長而增長。
針對此類掃描，索引必須包含查詢中涉及的的所有字段，另外，還需要滿足： Where 子句中包含索引中的 “ 引導列 ” （ Leading Column ），例如一個複合索引包含 A,B,C,D 四列，則 A 為 “ 引導列 ” 。如果 Where 子句中所包含列是 BCD 或者 BD 等情況，則隻能使用非比對索引掃描。
2 ）非配置索引掃描
正如上述，如果 Where 子句中不包含索引的導引列，那麼将使用非配置索引掃描。這最終導緻掃描索引樹上的所有葉子結點，當然，它的性能通常仍強于掃描所有的資料頁。
[參考 ]
[1] http://manuals.sybase.com/onlinebooks/group-asarc/asg1200e/aseperf/@Generic__BookTextView/3358
[2] http://publib.boulder.ibm.com/infocenter/idshelp/v10/index.jsp?topic=/com.ibm.adref.doc/adref235.htm