資料庫索引深入淺出(一)

Posted on | Edited on | In , | Comments: | Views:
Symbols count in article: 4.1k | Reading time ≈ 7 mins.

前文

Index第一個欄位至關重要它會影響資料統計值結果，Index一般建立在查詢條件的欄位

每個Index都擁有自己的B+ tree.

Index使用的資料結構(B+ tree)

B+ tree是一種資料結構這個資料結構被Index拿來使用，關於B+ tree網路上有很多資源可再自行尋找，所以我們來談談為什麼DataBase會使用B+ tree

在Wiki講述B+ tree有其中一段

B+ tree是能夠保持資料穩定有序，其插入與修改擁有較穩定的對數時間複雜度。B+ tree元素由下而上插入，通過最大化在每個內部節點內的子節點的數目減少樹的高度，平衡操作不經常發生，而且效率增加了。這種價值得以確立通常需要每個節點在次級儲存中占據完整的磁碟塊或近似的大小。

簡白來說B+ tree有一個特性是他會把資料存在子頁(Leaf Page)中透過一個參考把每個子頁串聯起來，提高穩定度.

B+ tree資料結構如下圖，這個資料結在在範圍查詢時較B tree來的更穩定

Index真正在使用B+ tree儲存類似於下圖

此圖來自(Pro SQL Server Internals, 2nd edition)

Index優缺點

Index可以加快查詢速度，因為Index是以空間換取時間。

基本上它使用的資源如下:

  1. 每個Index都會建立一顆b+ tree
  2. 每次新增、更新資料時都會異動到有使用的b+ tree

所以當你Index越多時，你需要維護的Index越多(代表需要更多資源來維護)

建立太多Index，小心降低(新增、更新)效率

因為SQLServer會對於這次新增、更新使用Index做異動

下面有一個T98資料表擁有兩個Index

  • CIX_T98 Clustered Index
  • IX_T98 Convering Index
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
IF EXISTS(
    SELECT 1
    FROM sys.tables
    WHERE name = 'T98'
)
BEGIN
    CREATE TABLE T98(
        ID int,
        COL1 VARCHAR(50),
        COL2 VARCHAR(50)
    )
END

insert into T98 VALUES (1,'Hello','Hello1')

CREATE CLUSTERED  INDEX CIX_T98 ON T98(
    ID 
)

CREATE INDEX IX_T98 ON T98(
    ID 
) INCLUDE (COL1)

當我們要執行更新COL1欄位時(打開執行計畫)

1
2
UPDATE T98
SET COL1 = 'Test1'

可以發現此次更新,我們會對於這兩個Index異動

  • CIX_T98 Clustered Index
  • IX_T98 Convering Index

1
2
UPDATE T98
SET COL1 = 'Test1'

但當我只更新COL2時,只會異動CIX_T98 Index

1
2
UPDATE T98
SET COL2 = 'Test1'

這是為什麼?

因為IX_T98 Index B+ Tree沒有包含COL2欄位相關資訊,所以不需要更新

Clustered Index(叢集索引)

每個資料表只能有一個Clustered index，資料表會依照Clustered index方式存放排列資料，Clustered Index會把資料放置在Left子頁層

Cluster index好比書籍頁碼目錄。每本書只能有一個目錄

建立Clustered Index欄位有幾個重點

  1. 常用於查詢欄位
  2. 可識別度高(唯一性較高)

NonClustered Index(非叢集索引)

每個資料表能有許多NonClustered Index，像每本書可以有很多種附錄

  1. 例如依照字母排序
  2. 依照附錄A
  3. 附錄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沒有包含所有要查詢欄位

  1. 有Clustered Index，會執行Key Lookup
  2. 沒有Clustered Index，會執行RID Lookup

這裡的RID是指向真實資料位子RowID

如果Nonclustered index可以建立Unique盡量宣告成Unique,因為Leaf page就可以減少製造Unique的Row-id欄位,減少儲存空間.

RID Lookup

資料表沒有Clustered Index且使用Index所有查詢欄位不包含在Converting Index中就會透過RID Lookup查找確切Page上的Row(藉由Row-Id)

RID Key的大小8 byte

lookup會消耗Disk I/O，所以消耗成本相對會比較大.

沒有Clustered Index的資料表我們稱為Heap資料表

我們可以透過下面語法利用上圖 HEAP RID 找到資料儲存位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
--HEAP RID:0x40110F0001002900
--共8 bytes FID（2 bytes）,PID（4 bytes）,slot（2 bytes）。

--轉換RID為 FID:PID:slot格式
declare @Heaprid binary(8)
set @Heaprid = 0x40110F0001002900
select [FID:PID:Slot]=      
       CONVERT (VARCHAR(5),
       CONVERT(INT, SUBSTRING(@Heaprid, 6, 1)
       + SUBSTRING(@Heaprid, 5, 1)))
     + ':'
     + CONVERT(VARCHAR(10),
       CONVERT(INT, SUBSTRING(@Heaprid, 4, 1)
        + SUBSTRING(@Heaprid, 3, 1)
        + SUBSTRING(@Heaprid, 2, 1)
        + SUBSTRING(@Heaprid, 1, 1)))
     + ':'
          + CONVERT(VARCHAR(5),
          CONVERT(INT, SUBSTRING(@Heaprid, 8, 1)
          + SUBSTRING(@Heaprid, 7, 1)))
--1:987456:41--找到c3和c4完整資料
DBCC PAGE(AdventureWorks2012_Data,1,987456,3)

Heap RID Key:8 byte.(FID 2 Bytes,PID 4 Bytes,SLOT 2 Bytes)

Key Lookup

NonClustered Index中會存放此Row在Clustered Index相對位置，假如單單靠搜尋Non-Clustered Index沒有辦法滿足所有查詢需要資料就會去Key Lookup(by Clustered key)回找Clustered Index取出相對應的資料.

Nonclustered Index Lookup I/O 操作計算公式

Index層數 + 讀取幾個Page + (幾筆資料 * clustered index層數)

此存取就稱為Lookup，lookup會消耗Disk I/O，所以所耗的時間相對會比較大

在NonClustered Index中頁層會包含Clustered Index的Key

範例演示

我們先準備10000筆樣本資料

1
2
3
4
5
6
7
8
9
10
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

建立完資料後我們利用下面條件來查找資料.

1
2
3
SELECT *
FROM dbo.T
WHERE id = 10000

因為沒有建立Index，導致我明明只需要撈取一筆資料,但資料庫卻全表掃描


建立一個 NonClustered Index

我們在表中建立了一個NonClustered Index，並利用相同查詢語法查詢資料

1
2
3
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，並且執行相同查詢

1
2
3
CREATE CLUSTERED INDEX CIX_T_UserId on  dbo.T(
	UserId
)

能看到執行計畫的不同了，已經透過Key Lookup回去查找資料，原因是目前資料表已經有Clustered Index但此查詢使用條件使用NonClustered Index所以導致需要Lookup回去Clustered Index的B+ Tree查找資料

此文作者：Daniel Shih(石頭)
此文地址： https://isdaniel.github.io/dbindex-1/
版權聲明：本博客所有文章除特別聲明外，均採用 CC BY-NC-SA 3.0 TW 許可協議。轉載請註明出處！

Related Posts

如果本文對您幫助很大，可街口支付斗內鼓勵石頭^^