SQL Server 索引內幕 (by rolence)
網路上許多說明索引的文章，但看來看去總覺得索引這東西像是罩著一層神秘的面紗，難以一窺究竟，這天剛好在網路上看一篇微軟考證照用書。有提到索引的細節。
因此本著分享的精神，將書中重點用口語的方式寫下這篇文章。希望各位跟我一樣，能透過此文了解到一些索引的細節。
SQL Server 透過平衡樹來建立索引(又叫B-樹), 由下圖可知，B樹是由一個根節點，N個中間級節點加N個葉子級節點組成。(不好意思，圖是簡體的)
從下圖的索引來找”SQL Server”, 紅色的部份就代表了使用索引所跨的頁(在SQL Server 的T-SQL中可以下SET STATISTICS IO ON來看搜尋所跨的頁數)
索引能加快搜尋是眾所皆知的，比較容易忽略的是，從上圖來說，透過B樹不管搜尋到那一個字母，要跨的頁數都是一樣的。(上圖不管搜哪一個字母都要搜尋三頁)，也就是說，搜尋A開頭的字串，不會比搜尋Z開頭的字串來得慢很多。
不管資料table或者是索引的table ，在SQL SERVER裏面都是以頁(Page)為一個單位的。你可以把頁，想像成就像硬碟裏的"磁區"(但它跟硬碟裏的磁區並沒有絕對的關係)。而一個頁的大小，網路上通常寫8K，而我寫這篇文章時所參考微軟的認證用書，果然寫的比較詳細。書上說，一個頁實際上可以存的大小是8060 byte。
以下透過實際的例子來說明索引的建立方式：
假設在一個char(60)的欄位上建立索引，這代表：索引頁一行(Row)的大小就是60 byte。
如果一個Table有100行資料，則索引行共需要100 x 60 = 6k byte的大小。這個大小可以塞到同一個頁當中(因為一頁有8K的空間)。這一頁裏面，會有根級、葉級的索引行。
當這個Table 有135行資料時，則索引共需要 135 x 60 = 8100 byte的大小。這時候一頁 (8060 byte)就塞不進去這麼多索引了。此時會需要三個頁，為什麼？第一頁放135後的前半部索引，第二頁放135行中的後半部索引，而第三頁只有二行索引，分別指向第一頁及第二頁。(此時沒有中間級的索引頁)
根頁134行，可以指向134個葉子頁，因此共可以索引134 x 134 = 17956 個資料行。由此可知，如果資料行數大於17956，則會有中間層出現。
當中間層出現時，則可以存放134 x 134 x 134 = 2406104 行索引。
現在你理解三件事：
1. 搜尋2406104個資料列，你只要搜尋三個頁，最差狀況下，也只有掃描了134x3=402行索引行，這就是索引快的原因！
2. 索引行的大小很關鍵：在上例中，如果我的欄位小了10倍，只有6byte ，則一頁可以放8060/6 = 1343行。二層的索引就可以存放1343x 1343 = 1803649,約180萬個索引行，跟上面範例中17956比，差了100倍。
3.從上面的算法，你也可以從實際存放的資料筆數+索引欄位大小，反推出你會需要幾層的分頁，而每層分頁存放多少筆索引鍵，進而算出索引表的Total大小。
叢集索引
通常每個Table都有一個叢集索引鍵，稱做主建。叢集索引鍵使Table中的資料列按叢集索引鍵的順序排列。而一個Table只能有一個排列順序，因此一個Table只能有一個叢集索引。
叢集索引不須要 葉級的索引頁，葉級的索引頁就是資料的分頁。找到葉級的索引就等於找到實際的資料頁中了。
容易搞錯的是。網路上很多人說叢集索引讓資料的物理順序也按邏輯順序排序，這是錯的。資料頁不一定是放在連續的磁軌中。
值得一提的是，當使用TSQL 的CREATE INDEX 命令中，有一個選項叫 ONLINE ，預設值是OFF，這個選項是SQL SERVER 2005 企業版才有的新功能，可以把這個選項設為ON。
開啟這個功能，可以讓SQL SERVER 在創建叢集索引(也就是Insert)的同時還可以SELECT 或UPDATE資料，且不會把整個資料表鎖死。
非叢集索引
一個資料表最多可以設定249個非叢集索引(書上沒有說為什麼是249這個數)。特別的是，非叢集索引的葉級索引，裏面的值有二個可能。
一、資料表有主鍵時，索引指向主鍵的索引。
二、如果資料表中沒有設主鍵，則指到資料頁的物理位置。
平衡索引所需的維護工作
索引的維護工作通常發生在Insert的時候。因為table建了索引。當Insert一筆資料時，同時也得將資料插到正確的索引頁中，而且索引頁中的資料還要進行重新排序才行。
所以，如果一個table有一個索引，insert 至少導至索引頁的一次寫入動作。30個索引，就會多了30個寫入動作。
另一個情況是，如果葉級的某個索引頁沒有空間了，sql server 就會執行page split(頁面分割)的動作。該動作會將原先索引頁中的一半索引行copy到新的索引頁中。
好了，有一個新的葉索引頁，這時候要新增中間頁的索引行了，如果此時又造成中間頁空間不足，這時候中間頁又要來一次page split動作了。
總而言之，一個資料表中的索引，並不是越多越好。
填滿因素
上文提及索引折分，談到這，不免要談一下「填滿因素」了。MSDN這樣寫的：
「建立或重建索引時，填滿因數值會決定要在每個分葉層級分頁上填滿資料的空間百分比，進而保留某個百分比的可用空間以備未來成長使用」
「在基礎資料表中加入資料時，將有空間可備索引擴充之用。空白空間會保留在每個頁面的索引資料列之間而非頁面的結尾」
不好理解是吧。我來解釋一下讀者就容易理解了：
如果索引行每一行都是緊臨填滿的情況下(如下圖所示)。那麼，如果有一個資料新增了，新的B索引要建在A及F之間，但A跟F之間沒有空白行，因此就需要大規模的搬移動作，把F之之後的所有索引行往下搬移。大家如果有學過資料結構，就會知道，陣列插入元素慢的原因也在於此。
但是換一個作法，如果索引行之間有了留白的空間，如下圖，那麼插入一筆資料時就可以避免到搬移的動作，進而加快插入的時間。
因此，適當的保留空間可以增加索引的插入效能。但卻也會增加索引的索引頁數(以空間換時間)。因為一個索引頁不再可以放滿所有的索引行了。
從上圖可以知道，很多人誤認為填滿因素的空白空間都在索引頁的最後面，這是不正確的。