#47 資料庫基礎 - 以 Hash 為基礎的 Index

前面的文章介紹了資料庫的 Index 是以 tree 為基礎的方式，一般來說大部份資料庫產品都用 B-tree 來建立 Index．然而，除了用 tree 以外，還可以用 Hash 的方式來建立．

可以用上圖來說明 hash index 的運作方式．首先，輸入值會先經過 hash function 的運算後而得到一個 hashed value，這個運作如以前的文章講的是一個 constant time 的運算．輸入值就是使用者要過濾的條件，也就是 SQL statement 中 where 的內容的欄位值．例如，學生證號碼，病歷編號等等．然而，這種輸入值若不是 key 的話，便會發生多筆同樣資料會得到一樣的 hashed value，例如我們是用學生的姓來做 hash index 的話，則同樣的姓就會得到一樣的 hashed value．因此，一個 hashed value 可能會對應到一個或多個在 Data page 上的資料．，以上圖來看，每個 hashed index 的資料可以對應到一筆或多筆在 data page 上的資料，這樣的做法其實並不太好，因為每個 hashed index 的資料大小是無法確定的，就因為我們無法預測每個 hashed index 會對應到多少筆 data page 的資料．因此，可以再改一下如下圖，

我們規定每個 hashed index 的資料只能對應到一筆 data page 上的資料，這樣就可以固定住每個 hashed index 的資料大小．因此，當輸入值經由 hash function 運算之後到達第一個 hashed index 上的位置，便可以得到一筆 data page 的位置而取得資料，然後還要往下一個 hashed index 移動，如果 hashed value 也是一樣的話，就要再取得它所對應在 data page 上的資料，一直到 hashed index 上的值不同了或是沒有下一個了．

以 hashed index 的運作方式來看，其效率比以 tree 為基礎的 index 還要來的好，那為什麼一般的資料庫產品不採用它呢 ? 我想主要的原因就在於 hashed index 無法支援有範圍的尋找．例如，如果用學生證編號做 index，當你下 SQL statement where ID > 10 and ID < 100 時，這在 tree-based index 上可以有很好的尋找效果，只要找到 10 之後就再延著 tree node 一直往下或往旁邊找到 100 就可以停住了．但 hashed index 來說並不是這樣，因為在 hashed index 裡, 10 旁邊的很可能就是 100，要看 hash function 如何設計．所以在 hashed index 上我們找不到一直可以連續讀取資料的方式．如果我們把編號從 10 開始代入一直到 100，這聽起來好像可行，但如果 index 的資料不是數字而是文字，難道要把筆畫漸大的字都帶進去運算嗎 ? 顯然不可能．

雖然 hashed index 不適合用在有範圍的尋找，所以就不適合被一些商業資料庫產品所採用，但還是透過這篇文章介紹 hashed index 讓讀者們可以了解 index 的做法不見得只有 tree 的方式，不同的方式有好有壞，有長處也有短處．