SQLSERVER 的主鍵索引真的是物理有序嗎？
2023-01-05 15:01:22
一：背景
1. 講故事
最近在看 SQL SERVER 2008 查詢效能優化，書中說當一個表建立了聚集索引，那麼表中的行會按照主鍵索引的順序物理排列，這裡有一個關鍵詞叫：物理排列，如果不瞭解底層原理，真的會被忽悠過去，其實仔細想一想不可能實現嚴格的 物理排列 ，那對效能是非常大的損害，本篇我們就從底層出發聊一聊到底是怎麼回事。
二：原理探究
1. 我認為的物理排列
如果用 C# 程式碼來演示嚴格的物理排列，大概是這樣的。
static void Main(string[] args)
{
List<int> list = new List<int>() {1,2,4,5 };
list.Insert(2, 3);
Console.WriteLine(string.Join(",", list));
}
從程式碼看我用 Insert 將 3 插入到了 list 集合中形成了物理有序，但不要忘了 Insert 的複雜度是 O(N)，而且還要將 3 後面的資料整體挪動，可以參考原始碼中的 Array.Copy 方法。
public void Insert(int index, T item)
{
if (_size == _items.Length)
{
EnsureCapacity(_size + 1);
}
if (index < _size)
{
Array.Copy(_items, index, _items, index + 1, _size - index);
}
_items[index] = item;
_size++;
_version++;
}
現在你可以想一想，如果我們每次在 Insert 的時候 SQLSERVER 都要將資料頁上的資料往後挪，那這個效能有多差？
2. 觀察聚集索引下的資料排序
為了方便講述，先建立一個測試表，插入 4 條記錄，再建立一個聚集索引，sql 程式碼如下：
IF OBJECT_ID('t') IS NOT NULL DROP TABLE t;
CREATE TABLE t (a CHAR(5), b INT)
INSERT INTO t(a,b) VALUES('aaaaa',1);
INSERT INTO t(a,b) VALUES('ddddd',4);
INSERT INTO t(a,b) VALUES('ccccc',3);
INSERT INTO t(a,b) VALUES('eeeee',5);
CREATE CLUSTERED INDEX idx_a ON t(a);
從圖中看資料果然是有序的，嚴格的按照 a , c, d , e 排序，接下來用 dbcc 觀察下在底層資料頁上這幾條記錄是不是物理有序的？ 查詢 SQL 如下：
DBCC TRACEON(3604)
DBCC IND(MyTestDB,t,-1)
DBCC PAGE(MyTestDB,1,472,2)
Page資料頁的輸出結果如下：
PAGE: (1:472)
PAGE HEADER:
Page @0x000002C6E75D0000
m_pageId = (1:472) m_headerVersion = 1 m_type = 1
m_typeFlagBits = 0x0 m_level = 0 m_flagBits = 0x4
m_objId (AllocUnitId.idObj) = 269 m_indexId (AllocUnitId.idInd) = 256
Metadata: AllocUnitId = 72057594055557120
Metadata: PartitionId = 72057594048348160 Metadata: IndexId = 1
Metadata: ObjectId = 850102069 m_prevPage = (0:0) m_nextPage = (0:0)
pminlen = 13 m_slotCnt = 4 m_freeCnt = 8024
m_freeData = 160 m_reservedCnt = 0 m_lsn = (49:1616:23)
m_xactReserved = 0 m_xdesId = (0:0) m_ghostRecCnt = 0
m_tornBits = 0 DB Frag ID = 1
Allocation Status
GAM (1:2) = ALLOCATED SGAM (1:3) = NOT ALLOCATED PFS (1:1) = 0x40 ALLOCATED 0_PCT_FULL
DIFF (1:6) = CHANGED ML (1:7) = NOT MIN_LOGGED
DATA:
Memory Dump @0x000000DF137F8000
000000DF137F8000: 01010000 04000001 00000000 00000d00 00000000 ....................
000000DF137F8014: 00000400 0d010000 581fa000 d8010000 01000000 ........X...........
000000DF137F8028: 31000000 50060000 17000000 00000000 00000000 1...P...............
000000DF137F803C: 00000000 01000000 00000000 00000000 00000000 ....................
000000DF137F8050: 00000000 00000000 00000000 00000000 10000d00 ....................
000000DF137F8064: 61616161 61010000 00030000 10000d00 63636363 aaaaa...........cccc
000000DF137F8078: 63030000 00030000 10000d00 64646464 64040000 c...........ddddd...
000000DF137F808C: 00030000 10000d00 65656565 65050000 00030000 ........eeeee.......
000000DF137F80A0: 00002121 21212121 21212121 21212121 21212121 ..!!!!!!!!!!!!!!!!!!
...
從 Memory Dump 區節的記憶體地址看，這四條記錄果然是有序的，
3. 真的按照物理有序嗎
接下來就是關鍵了，到底是不是物理有序，我們再插入一條 bbbbb 記錄，看下會不會將 ccccc 所在的記憶體地址上的內容整體往後挪？測試的 sql 語句如下：
INSERT INTO t(a,b) VALUES('bbbbb',2);
SELECT * FROM t;
從圖片看，貌似真的給塞進去了，那到底是不是這樣呢？ 帶著好奇心再次觀察下底層的索引資料頁。
PAGE: (1:472)
PAGE HEADER:
Page @0x000002C6D76C4000
m_pageId = (1:472) m_headerVersion = 1 m_type = 1
m_typeFlagBits = 0x0 m_level = 0 m_flagBits = 0x0
m_objId (AllocUnitId.idObj) = 269 m_indexId (AllocUnitId.idInd) = 256
Metadata: AllocUnitId = 72057594055557120
Metadata: PartitionId = 72057594048348160 Metadata: IndexId = 1
Metadata: ObjectId = 850102069 m_prevPage = (0:0) m_nextPage = (0:0)
pminlen = 13 m_slotCnt = 5 m_freeCnt = 8006
m_freeData = 176 m_reservedCnt = 0 m_lsn = (49:1640:2)
m_xactReserved = 0 m_xdesId = (0:0) m_ghostRecCnt = 0
m_tornBits = 487522741 DB Frag ID = 1
Allocation Status
GAM (1:2) = ALLOCATED SGAM (1:3) = NOT ALLOCATED PFS (1:1) = 0x40 ALLOCATED 0_PCT_FULL
DIFF (1:6) = CHANGED ML (1:7) = NOT MIN_LOGGED
DATA:
Memory Dump @0x000000DF0FDF8000
000000DF0FDF8000: 01010000 00000001 00000000 00000d00 00000000 ....................
000000DF0FDF8014: 00000500 0d010000 461fb000 d8010000 01000000 ........F...........
000000DF0FDF8028: 31000000 68060000 02000000 00000000 00000000 1...h...............
000000DF0FDF803C: b5010f1d 01000000 00000000 00000000 00000000 ....................
000000DF0FDF8050: 00000000 00000000 00000000 00000000 10000d00 ....................
000000DF0FDF8064: 61616161 61010000 00030000 10000d00 63636363 aaaaa...........cccc
000000DF0FDF8078: 63030000 00030000 10000d00 64646464 64040000 c...........ddddd...
000000DF0FDF808C: 00030000 10000d00 65656565 65050000 00030000 ........eeeee.......
000000DF0FDF80A0: 10000d00 62626262 62020000 00030000 00002121 ....bbbbb.........!!
000000DF0FDF80B4: 21212121 21212121 21212121 21212121 21212121 !!!!!!!!!!!!!!!!!!!!
...
000000DF0FDF9FF4: 21219000 80007000 a0006000 !!....p...`.
OFFSET TABLE:
Row - Offset
4 (0x4) - 144 (0x90)
3 (0x3) - 128 (0x80)
2 (0x2) - 112 (0x70)
1 (0x1) - 160 (0xa0)
0 (0x0) - 96 (0x60)
從 Memory Dump 節的記憶體地址看，bbbbb 並沒有插入到 aaaaa 和 cccccc 之間，而是寫入到頁面尾部的空閒空間中，接下來就有一個問題了，為什麼 sql 輸出中是有序的呢？怎麼做到的？ 如果你瞭解 Page 的 Slot 佈局，你會發現 Slot1 指向的就是 bbbbb 這條記錄的首地址，畫一張圖就是這樣。
從圖中我們就明白了最終的原理，當 Insert 時，SQLSERVER 並沒有對錶記錄重排，而只是將指向的 Slot 槽位進行了重排，將物理無序做成了一種邏輯有序。
三：總結
其實大家只要往高效能上想，肯定不會實現物理有序的，太傷效能了，在 物理無序 上抽象出一層 邏輯有序 不失為一種好辦法。