#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 的精神.

Share:

0 意見:

張貼留言