DBMS Disk Space Management

要談論DBMS，除了SQL語法之外，我們還必須了解底層是怎麼處理資料儲存的，也就是DBMS架構的底層Disk Space Management：

Disk Space Management

提供API來讀/寫資料到硬碟，資料會以Page為傳輸單位，為什麼會一次要等到這麼大才寫入硬碟或一次要讀這麼大的資料，背後是跟儲存裝置的特性有關，這邊暫不贅述。

在資料庫中，最小的單位是row，aka一筆資料。而在Disk中，最小單位則是page(1 page read from disk or 1 page write to disk)，而所謂的block會比page大，因為block在SSD當中會含有多個page。

Disk Space Management會背後是由操作系統和文件系統來處理的，它會負責在硬碟上分配一個大而連續的空閑的文件用來存資料，每一份文件(file)裡都會有很多的page(根據設定的固定page大小來決定有幾頁)，DBMS這些檔案可能會分散在不同的機器/硬碟上。

宏觀來看，Page File裡面長怎樣：

這樣可以方便在新增資料的時候能快速找到要插入的頁面中的位置是哪裡，而不用一個一個page找每頁的閒置空間夠不夠放這筆資料。

I/O成本從n個page降到4個I/O（1.讀header page2.讀資料 3.寫資料到page 4.更新header page)。

Page Layout(通常4KB, postgresql為8KB，要看你資料庫的預設值為何):

宏觀來看，一個page中會存多個row的資料，而每一個row有多個欄位，每個欄位的長度雖會不同，但又可分為可變/不可變的而有不同page layout。

Fixed Length Records 固定長度

每個page都有一個header，裡面維護一個bitmap，每一個slot會指向record的位置，因為size固定，所以我們可以很簡單的直接藉由數學計算而得每一個slot的起始位置在哪，接著只需要維護每個slot是有值還是沒值：

Variable Length Records 可變長度

因為每一個紀錄的長度大小不同，不可直接預先知道每一個slot指向的位置為何，我們會用另外一種做法。

維護一個page footer，此時會多兩個特別的slot，最後一個slot代表這個頁面有的slot數（包含空的)，倒數第二個則指向閒置空間的位置，其餘的slot會記錄兩件事：指向有紀錄的record以及record的大小 [record pointer, record length]。

要刪除record會根據是要緊湊還是不緊湊而有所不同，如果是非緊湊的(unpacked)只要簡單的將poiner取消掉並且把紀錄長度設為null即可。之後會交由作業系統決定何時要GC。

緊湊的話，則需要將刪除的紀錄真正從page中移除，這意味著可能要更新到其餘record的位置（往前挪一格，slot也要移，這個移動不會跨頁，只會管同一個page的情況）。

插入新資料也只是很簡單的插入在free space pointer指向的位置，並且在值為null的slot中寫入資料後更新slot長度跟指標位置[record pointer, record length]、free space pointer的指標位置即可。

Tuple Layout

(待補)

延伸閱讀：

73.6. Database Page Layout

https://cs186berkeley.net/notes/note3/