電腦科學 ^ IT人生 ^ 公益課程

#28 資料庫基礎 - 存取 Page (Hashed File)

前面兩篇文章提到了存取 page 的兩種方式,在這一篇文章裡要介紹的是另一種方式,我們稱它為 hashed file.聽到這個名字,你可能已經猜到這是和 hash function 有關係的儲存方式.沒錯,它就是利用 hash function 來決定儲存位置,也是就說透過 hash function 的計算來決定要儲存到那一個 page 上.

前面的文章曾提到過基本的 hash function,也介紹了它最簡單的運算方式.所以,假設一開始有十個 page,然後有五筆資料,我們可以將每筆資料傳給 hash function,計算出來的結果是 0 - 9 的數字,而這數字就用來代表要儲存到那一個 page 上.一旦資料變多時,資料的筆數一定會遠遠大於 page 的數量,所以同一個 page 上一定會有許多筆資料.因此,透過 hash function 的方式來計算儲存位置也是個蠻快速的方法.不過,資料庫引擎通常不會被設計成將整筆資料拿來 hash,因為我們在找資料時很少會用全部的欄位做為搜尋的條件,因此,我們通常會選擇幾個重要的欄位或是只選擇 primary key 的欄位來做為 hash function 的輸入值,而 hash function 輸出值就是 page 的號碼.因此,資料庫引擎在為我們找資料的時候,只要欄位條件符合的話,就可以透過 hash function 的計算而快速地得到 page 號碼.

接下來,你可能會問到,一旦資料量越來越大時,一定會有很多的資料經過 hash function 計算後會得到同樣的答案,而這些資料量會遠遠超過一個 page 得記錄的資料量.這種情況在我們談論 hash function 的時候也會發生,當時所採用的方法就是在 bucket 上做一個 list 來承接更多的資料.相同地,在這裡也是可以用相同的觀念.如下圖:


如上圖的上面那個 page,當它沒有足夠的空間承載更多資料時,此時資料庫引擎就必需要一個空白的 page ,然後在前面的 page 做一個連結到空白的 page,接著就可以把屬於同一個 bucket 的資料寫進去.因此,你可以看見的是,如果 hash function 的 bucket 準備不多的話,那麼資料就會長成像幾條很長的 page life,我們並不希望碰到這樣的情況.所以若要採用 hashed file 的儲存方式,則該 hash function 需要有能力產生足夠多的 bucket,甚至最好是能彈性處理,依照資料的多少來決定,但相對地要做多的配套措施.但若以好的角度來看,用 hashed file 的結構來儲存資料,對資料庫引擎而言可以大大提供資料搜尋的速度.

有關資料如何儲存在 page 上,從儲存的方式來看基本上有三種方式,而每一種方式都有其優點和缺點,所以針對不同的資料,根據他們的特性來決定用那一種儲存方式將是比較好的決定.要怎麼評估呢 ? 我會把評估的成本估算寫在未來的文章裡,讓大家知道資料庫引擎是根據什麼樣的數據來決定要用什麼方式儲存資料.


Share:

0 意見:

張貼留言