Index使用的資料結構(B+ tree)
B+ tree是一種資料結構這個資料結構被Index拿來使用，關於B+ tree網路上有很多資源可再自行尋找，所以我們來談談為什麼DataBase會使用B+ tree
在Wiki講述B+ tree有其中一段
B+ tree是能夠保持資料穩定有序，其插入與修改擁有較穩定的對數時間複雜度。B+ tree元素由下而上插入，通過最大化在每個內部節點內的子節點的數目減少樹的高度，平衡操作不經常發生，而且效率增加了。這種價值得以確立通常需要每個節點在次級儲存中占據完整的磁碟塊或近似的大小。
簡白來說B+ tree有一個特性是他會把資料存在子頁中並且透過連結把每個子頁串聯起來，提高他的穩定度.
B+ tree資料結構如下圖，這個資料結在在範圍查詢時較B tree來的更穩定
Index真正在使用B+ tree儲存類似於下圖
此圖來自(Pro SQL Server Internals, 2nd edition)
Index優缺點
建立太多Index，小心降低新增、更新效率，Index可以加快查詢速度，是Index以空間換取時間。
基本上它使用的資源如下:
- 每個
Index都會建立一顆b+ tree - 每次新增、更新資料時都會改變
b+ tree
所以當你Index越多時，你需要維護的Index越多(代表需要更多資源來維護)
Clustered Index(叢集索引)
每個資料表只能有一個Clustered index，資料表會依照Clustered index方式存放排列資料，Clustered Index跟資料一起放置在Left子頁層
Cluster index好比書籍頁碼目錄。每本書只能有一個目錄
建立Clustered Index欄位有幾個重點
- 常用於查詢欄位
- 可識別度高(唯一性較高)
NonClustered Index(非叢集索引)
每個資料表能有許多NonClustered Index，像每本書可以有很多種附錄
- 例如依照字母排序
- 依照附錄A
- 附錄B
NonClustered Index按照Key Column排序，
NonClustered Index(index page)上所有分葉節點存放指標，如果資料表已存在Clustered Index(KeyID)，那麼該指標將會指Clustered Index，如不存在將指向資料真實存放位置(RID)
this is a very important point to remember. Nonclustered indexes do not store information about physical row location when a table has a clustered index. They store the value of the clustered index key instead.
上面簡單來說如果NonClustered Index沒有包含所有要查詢欄位
- 有
Clustered Index，會執行Key Lookup - 沒有
Clustered Index，會執行RID Lookup
這裡的
RID是指向真實資料位子RowID
RID Lookup
資料表沒有Clustered Index且使用Index所有查詢欄位不包含在Converting Index中就會透過RID Lookup查找確切Page上的Row(藉由Row-Id)
RID Key的大小8 byte
lookup會消耗Disk I/O，所以消耗成本相對會比較大.
沒有
Clustered Index的資料表我們稱為Heap資料表
Key Lookup
NonClustered Index中會存放此Row在Clustered Index相對位置，假如單單靠搜尋Non-Clustered Index沒有辦法滿足所有查詢需要資料就會去Key Lookup(by Clustered key)回找Clustered Index取出相對應的資料.
範例演示
我們先準備10000筆樣本資料
CREATE TABLE T(
Id INT identity(1,1),
UserId INT,
UserGroup INT
)
INSERT INTO T (UserId,UserGroup)
SELECT TOP 10000 1.0 + floor(10000 * RAND(convert(varbinary, newid()))),
(1.0 + floor(10000 * RAND(convert(varbinary, newid())))/1000)+1
FROM sys.all_columns t1 CROSS JOIN sys.all_columns t2
建立完資料後我們利用下面條件來查找資料.
SELECT *
FROM dbo.T
WHERE id = 10000
因為沒有建立Index，導致我明明只需要撈取一筆資料,但資料庫卻全表掃描
建立一個 NonClustered Index
我們在表中建立了一個NonClustered Index，並利用相同查詢語法查詢資料
CREATE NONCLUSTERED INDEX IX_T_Id on dbo.T(
id
)
建立完NonClustered Index後從原本的全表掃描變成RID Lookup和Index Seek，因為NonClustered Index的B+ Tree沒有包含所有需要撈取的資料.所以透過RID回去Heap資料表查找出所需要的欄位
RID Lookup在執行計畫中呈現如下圖，
再建立一個 Clustered Index
我們在T資料表中建立一個Clustered Index，並且執行相同查詢
CREATE CLUSTERED INDEX CIX_T_UserId on dbo.T(
UserId
)
能看到執行計畫的不同了，已經透過Key Lookup回去查找資料，原因是目前資料表已經有Clustered Index但此查詢使用條件使用NonClustered Index所以導致需要Lookup回去Clustered Index的B+ Tree查找資料
如果本文對您幫助很大，可街口支付斗內鼓勵石頭^^
