#26 資料庫基礎 - 存取 Page (Sorted File)

上一篇文章談的內容是針對資料之間是沒有順序的情況，因此在尋找資料時就是採用依照資料的排列順序來尋找．因此整個尋找過程的時間複雜度是 O(n) ．通常來說，資料庫設計者不會讓這樣的事情發生，除非資料本身是一個相當小的參考資料而己，否則資料一旦多了，  O(n) 實在不是一個好現象．

在真實世界中的應用，我們常常可以為資料找到至少一種排列方法，例如，在學校的資料庫中，基本上可以用學生證的號碼來排序學生的資料，因為在同一個學校裡不會有相同的學生證號碼．我們在前面的文章中也提過，一旦資料排序過了之後，時間複雜度就會從 O(n) 下降成 O(log n)，基本上就是 Binary search．因此，如果資料可排序的話，則資料庫引擎就可以依序地將資料寫在檔案中．

資料庫引擎為這些可排序的資料寫入到檔案中有兩個方式．第一種方式是直接將資料依序排列好寫在檔案中，所以每個資料的前後順序就跟排列的順序是一模一樣的，如果中間要插入一筆新資料時，就很有可能會發生 page split 的動作．如圖是一個例子．紅色的框框代表 page，而藍底的框框帶表一筆資料，而藍框裡的數字代表資料的序號，序號不一定要連續，只要不重複即可．所以一開始把資料寫入時，它的排列長相如下:

這時候如果要新增一筆序號 7 的資料，那麼它要排在 5 和 10 之間，但是該 page 已經沒有位置了，因此發生 page split．

資料 7 會放在前面的 page 還是後面的 page，這將由資料庫引擎內定的邏輯來決定．

第二種將資料寫入檔案的方式是讓資料的實體位置不需要改變，另外在建立 "目錄"，然後在這目錄上做 binary search 的動作．

在這種方式下，新增一筆序號 7 的資料時，它就可以直接在 page n+1 的地方寫入，然後資料庫引擎只要更新目錄的內容即可．

當新增一筆序號 7 的資料在目錄 page 時，此時會發現  page split 還是在有足夠的空間下把後面的資料往後移，這將由資料庫引擎的內定邏輯而定．因此，第二種方式就變成直接在目錄 page 上做  binary search ，然後再依照其內容 (pointer) 就可以找到該筆資料．

所以，你的 table schema 的設定理應當是都有 primary key 的存在，如此一來才能做為資料庫引擎排序的依據．其實，以上的內容基本上也就是 clustered index 和 non-clustered index 的精神．