###### tags: `database` `note` `thu`
{%hackmd theme-dark %}

Note: 我也不知道會不會考我整理的，但我就寫了...

# File structure
課本上講了很多，但我們的主要目標是要最小化需要在記憶體和硬碟中移動的「block數量」，以達到加快資料庫效能的目的。

- Primary File Organization
主要是在講如何把block存在硬碟上的規劃方法。也是本頁的主題。
主要分Ordered, unordered file。
- Secondary/Auxiliary Organization
以上方除了Primary field以外的欄位進行有效存取的方式。
這裡的內容主要會在下一頁[Indexing Structures](/HrDt22JbSAuhJfKxdjLpAg)裡提到。

## Storage層級
因為資料庫是在電腦上跑的，所以你的資料勢必得存在電腦上的某個地方。
而其中又分了幾種:
### 1. Primary storage
- 也就是記憶體、快取之類的。
### 2. Secondary storage
- 也就是硬碟、SSD之類的。
### 3. Tertiary storage
- 也就是光碟、可移除式的裝置之類的。

## 存放資料的結構
照理來說，你的資料庫應該是無法全數放在記憶體當中的，所以如何規劃資料存放的結構也成為了一個很重要的議題。
這又被稱為Physical Database design。

### A. File v.s. Record
一個File是由一系列的records所組成。又有分:
- Fixed-length records (每筆record長度固定)
- Variable-length records (每筆record長度不固定)

當然，不固定長度的檔案一定會比固定長度的來得難以設計。

### B. Spanned v.s. Unspanned Records
- 因為磁碟儲存資料的最小單位為block，所以我們得要以block為單位來思考如何放置我們的資料。
- 但是我們的每筆record也不會一定剛好能fit進我們的block，像是如果$B$是我們的block大小，$R$是我們的record大小，則我們每個block會空出來的大小為:
$$B - (\lfloor B/R \rfloor * R)\ Bytes$$
那我們該如何處理這些剩下的空間？
#### 1. Unspanned
<s>解決提出問題的人</s>
直接禁止超出1個block大小的record就沒事了。
#### 2. Spanned
我們可以把record分成兩個block來放。在第一個block的結尾放入一個指標指往下一個block。

### C. 放置Block的技巧
#### 1. Contiguous allocation (連續放置)
也就是同一個檔案的block都放在一起。
- 好處: 讀取快。
- 壞處: 要增加records時會很困難。

#### 2. Linked allocation
同一個檔案的block未必放在一起，但他們的block結尾都有通往下一個block的指標。
- 好處: 增加records方便，只要改指標就行。
- 壞處: 讀取慢。

#### 3. Clusters
把兩種方法合起來。
也就可能會有好幾個不同大群的資料，每一團裡都是連在一起的，但是兩大團之間都有指標連在一起。

#### 4. Indexed allocation
取幾個block作為index blocks。裡面全都放置指往實際資料的指標。

### D. Ordered v.s. Unordered records (or 其它？)
Record在File裡放置的順序。
#### 1. Unordered file (aka heap/pile file)
<s>瞎機巴亂放</s>
先插入的就先放。
- 好處: 插入快
- 壞處: 存取效率低下，接近線性搜尋。
- 壞處: 刪除後中間會留洞，空間利用率就會下降。所以需要定期重新整理。

但這種結構通常會有其它的存取方式，不然讀取的就太慢了。

#### 2. Ordered file (aka sequential file)
按照某一個unique的欄位(稱作ordering field)來進行排序(e.g. primary key)。
- 好處: 因為是排序過的，所以可以用二分搜。
- 壞處: 插入跟刪處都很貴，因為你還要保持資料的有序性。

但通常會另外開一個unordered file來存放你要插入的資料，然後每隔一陣子再重新整理回原本的ordered file。

| 結構 | 存取方法 | 平均需要存取的block數量 |
| -------- | -------- | -------- |
| Heap (unordered)| Sequential scan(線性搜尋) | $b/2$ |
| Ordered | Sequential scan(線性搜尋) | $b/2$ |
| Ordered | Binary search(二分搜) | $b/2$ |

#### 3. 索引系列~ (下一頁會講得更仔細)
最常見的不外乎是下面兩種
##### a. Indexed-sequential file
是Ordered file的進階版，還加上了一個Primary index可供索引。如此一來就更加強了隨機存取的效能了。
##### b. Hash file
使用某個record的欄位做為索引的目標，然後把hash相同的record都放入同一個block。
再來就可以直接把整個block載入記憶體快速搜尋了。