#41 Load Balance 負載平衡

Load Balance 顧名思義就知道是在兩個以上的運算器環境下將每個運算器的運算負載量達成一致的目的．這樣子的概念應該在許多的情境之下，例如大型網站或是大型的資料庫等．這種類型的情境一定都有一個共同的特點，那就是 request 的 client 很多而提供 service 的 server 很少．

我們以大型網站服務為例子．最先開始架設一台網站伺服器來服務某一數量的用戶端，只要用戶端不繼續增加或是服務本身的運算邏輯沒有變的更複雜時，則一切都會相安無事．只要其中一個有增多的現象時，最終總是會面臨到該網站伺服器的資源不用使用的情況．因為每個用戶端連線都需要佔用 CPU/Memory 資源，所以既便是 CPU 再快 Memory 再多，也是會遇到上限．因此，要解決的方法有兩種，一個稱為 scale up，另一個稱為 scale out．Scale up 是指在同一個伺服器內進行硬體的升級以求在同一時間內服務更多的用戶端，例如升級 CPU，記憶體，網路卡等等．Scale out 是指再加入其他的伺服器來服務用戶端．通常來說，scale up的方式比較受限，而且一台伺服器若是要能裝入更多的 CPU 和 Memory，則價錢通常都是非常地高，所以比較經濟的做法就是 scale out．

Scale out 第一個會遇到的問題就是該如何分派工作．既然要達到負載平衡，也就是每台伺服器的運算負載量是接近一致的，那麼首要考慮的事情就是該如何達到一致．如果每個用戶端所要求的工作量都是固定的，很容易就可以做到負載量是一致的．因為只要在這些伺服器前都有一個 dispatcher 來輪流地分配工作，就可以達成負載量一致的效果，就如下圖一樣．

這種方式有一個缺點，dispatcher 將會是 single point of failure，單一失敗點，也就是說它若壞掉了，整個系統便無法運作．這種運作方式也稱為 Round-robin，輪流分配工作．在直實世界中，我們很難要求每一個用戶端都會有相同的運算工作量，因此每個用戶端送過來的需求一定會有不同的運算工作量，因此用 round-robin 的方式是很難達成負載量一致的，只能說是用戶端需求分配數量是一致的，因為很有可能某一個伺服器都會收到運算量很大的工作導致它比別的伺服器來的更加忙碌或是資源更吃緊．Round-robin 的方式算是集中式的管理，因為都是透過 dispatcher 來運作．

另外還有一種比較常見的負載平衡的方法是不需要 dispatcher，而是伺服器之間要互相溝通訊息，把自己的負載量資訊傳給其他的伺服器．所以每個一伺服器都會有一份每個伺服器負載量的資料，而且這分資料是經常地在更新．因此，當新的用戶端需求進來時，這份需求會先被某一個伺服器接收，然後該伺服器會依照這份資料來決定這份工作是要自己做還是傳給其他伺服器來做，這就看系統實作的是什麼樣的演算法．若採用最簡單的，也就是挑選負載量最小的伺服器，那這份工作就會被傳送到負載量最小的伺服器來處理．

這個方式聽起來似乎比較好，因為不會有 single point of failure 的問題，只是這樣的伺服器集合不適合有太多的伺服器在一起．我們簡單地想像一下，如果這個群組有十台伺服器，每一台伺服器在每隔幾秒鐘就要彼此交換負載量的資訊，這似乎不會是一個太麻煩的工作，但如果這群組變成是一百台或是一千台伺服器時，這樣的方法顯然會有問題，因為光是和其他 999 台伺服器完成一輪的負載量資訊交換可能就要花上一段時間和不少的 CPU 與 Memory，顯然不是一個經濟的做法，而且也不見得能儘量達成負載平衡．

其實在許多伺服器之間要對一份資料取得共識，也就是說一號伺服器上收集到的資料和 n 號伺服器上收集到的資料是一樣的，這也是一個很大的學問．往後的主題將會來討論這部份．

閱讀全文

#40 Coding 面試 - LeetCode #150 Evaluate Reverse Polish Notation

原文題目網址 : https://leetcode.com/problems/evaluate-reverse-polish-notation/

這題蠻有趣的．剛看到這題時，老實說並不知道什麼是 Reverse Polish Notation．如果你在被考到這題時也不知道的話，其實也沒關係，因為你可以直接問主考官，主考官一定會告訴你什麼是 Reverse Polish Notation．因為你要懂了這是什麼表示法，你才能做這個題目．

簡單的說，一般的數學，我們習慣寫成像我們從小到大看到的式子，例如 3+4．而 Reverse Polish Notation 就會寫成 34+ ，很簡單吧! 所以你看到題目上給你的例子， 2,1,+,3,* 就是 (2+1) * 3 ，因此答案就是 9．所以，這一題就是要考你寫一個 function，輸入是 Reverse Polish Notation，而輸出是數字答案．因此，我們假設輸入是一個 string array，而輸出是 int．

不知道你看到這種題目時，你會不會馬上聯想到 stack 或是 queue 之類的資料結構，因為可以依序地把數字儲存下來，又可以正向或反向地把數字取出來．如果你能想到這個，解題的方向也算是對的了．

除此之外，一開始還要為輸入字串做檢查，檢查是不是合格可運算的．例如，如果輸入字串都是運算符號而沒有數字，那這是不能算的，需要回傳錯誤．或者是輸入字串只有數字而沒有運算符號，這也是不能計算的．另外，輸入字串的第一個和第二個元素一定不會是運算符號，一定會是數字．所以這幾個條件就當做是程式裡的 throw exception 的條件．

接著，只需要一個 for loop ，把符合所有條件的數字用 stack 記錄下來，然後遇到運算符號時，把從 stack 把之前的數字拿出來運算，算完後再寫回去 stack．所以，用這樣的邏輯就可以把這題的答案寫出來了．

程式碼參考如下:

閱讀全文

#39 物件導向 - Interface 的基本應用範例

記得以前在學習物件導向語言的時候, 學到了 Class 定義,也學到的物件跟物件之間的關係, 後面也學到繼承關係. 在學習這些物件導向內容的時候也有看到 interface, 不過當時對 interface 並沒有太深刻的了解. 所以在這一篇文章裡面就來談一談 interface.

如果你做過一些小專案或者只是個人在用的一些小程式, 基本上來說 interface 用到的機會應該是不多. 相反的, 如果你曾參與大型專案, 那麼 interface 應該是到處可見的. 為什麼呢? 那是因為大型的專案通常是由多個開發者所共同進行, 所以不同的開發者會負責不同的項目, 你也可以把看成不同的開發者會負責不同的元件. 而在一個大型的專案裡, 元件跟元件之間的溝通是件基本的事情. 然而，元件跟元件之間的溝通不一定只是單純的資料傳遞, 傳遞的內容中有可能是物件本身. 所以, 元件和元件之間就必須要遵守特定的規則, 這樣子我們才能夠成功的將資料或者是物件傳送給對方. 除此之外, interface 的好處也可以應用在軟體測試上. 接下來用一些簡單的例子來說明.


這個例子是微軟開發工具產品裡面的某一個視窗, 而在視窗裡面有一些控制項, 它的長相大概就如下圖所示:

可以看到在這個視窗中有一塊大的空白, 裡面顯示這個不同的專案範本. 假設製作視窗元件的團隊和製作專案範本的團隊是不一樣的, 也就是說他們的程式碼是來自兩個不同的專案, 他們要怎麼做才能夠達成協同運作的目的. 其中的關鍵技巧就是使用 interface. 例如說有一個 interface 的定義如下,

public interface ITemplate {
    List<Template> GetTemplate(TemplateKind kind);
    List<TemplateKind> GetTemplateKind();
}

製作視窗的團隊中, 他們一定會去採用這個 interface 定義, 因為在這一個 interface 定義裡面提供了兩個方法. 第一個方法是取得有多少範本, 第二個方法是去取得有多少範本種類. 在他們顯示這一個空白區域的內容時, 他們就可以將這個介面定義作為參數,

public void ShowTemplates(ITemplate templates)

ShowTemplates 方法本身是可以由外部程式來呼叫的, 所以只要能夠準備好所需要的參數, 就可以將物件參數傳進去, 然後這一個方法就可以依照 interface 提供的方法把範本的種類和範本顯示在空白地域上.

所以透過這種方法, 開發範本的團隊就可以很清楚的知道需要傳過去的參數內容長相是什麼樣子．這樣看起來就像是兩個團隊之間有著共同的合約, 合約裡面的內容就是定義這會有哪些屬性或方法.

閱讀全文

#38 Coding 面試 - LeetCode #2 Add Two Numbers

原文題目 https://leetcode.com/problems/add-two-numbers/

這題是個基本的 Linked List 考題，如果題到這類型的 List 題目，若題目沒特別說的話，就一律想成是 Single Linked List 了．其實，我個人不是很喜歡 List 考題，原因是大部份的問題都蠻無聊的，可能就在 List 上把元素搬來搬去，而且不一定會有一個很好的邏輯來搬這些元素，所以就會造成一個 function 寫的長長的．像這一題就是這樣．

題目給了兩個 input list，要把每個元素加在一起後，然後輸出一個最後的 list．其實也蠻簡單的，你只要在這兩個 input list 上一個一個元素去拜訪，然後把加起來的答案寫到新的位置上，同時再注意進位的事情．並且你也要考慮到兩個 input list 的長度可能是一樣長，也可能是不一樣長，甚至可能是空的．如果你按照這個想法寫，答案就可以寫的出來．

但是，就這麼簡單嗎 ? 基本上是的，但要注意一件事，上面的想法是會製造出另一個新的 list，算到最後把這個 list return 出去．這樣做的話就等於空間複雜度是 O(n+m) 了，假設 n,m 分別是兩個 input list 的長度．

所以，比較好的做法是讓空間複雜度變成 O(1)，也就是說每當計算一次元素的加法時，就把答案寫到某一個 input list 上，最後 return 這一個 input list 就行了，所以就不需要宣告出其他不是 O(1) 的空間．

參考的程式碼如下:

沒錯吧，又臭又長! 如果你能想到更好的方法來簡化以上的程式碼，再麻煩你教教我! ^_^

閱讀全文

#37 資料庫基礎 - Clustered Index 與 Non-clustered Index

在編號 #33 的文章中介紹了什麼是 Index．這可以說是資料庫對資料能快速尋找的主要方法，基本上也是一個用空間換取時間的方法，也就是為了更快速地找到資料，於是犧牲了更多的硬碟儲存空間來達成這件事．也因為如此，所以資料庫引擎也需要有相對應的功能來妥善管理這些特別的儲存空間．然而，儲存空間的內容不同也會影響不同的管理方法，所以這一篇文章將來介紹不同的儲存空間 -  Clustered Index 和 Non-clustered Index．

如果你曾撰寫過資料庫應用的相關程式或是你本身是資料庫管理員，相信你一定聽過 Clustered Index 和 Non-clustered Index．這兩個 Index 有什麼不同呢 ? 給一個比較簡單直覺的答案就是 Clustered Index 是根據某個資料在儲存空間上排列的順序而建立，而 Non-clustered Index 不一定要按照實體的資料排列順序而建立．

把 #33 那篇文章中的圖片再貼過來一次．

之前提過這是一份資料，按照學生證號碼排列寫入儲存空間的概念圖，所以你可以看到學生證的號碼有 1,5,7,11,13,16,23,24,36 這些號碼，而這些號碼基本上會被選做為 primary key，所以資料庫引擎可以利用這個號碼做為資料儲存位置的順序．因此，號碼小的一定寫在號碼大的前面，若不是在同一個 page 上的話，那一定是在前面的 page 上．所以，如果資料庫引擎用學生證號碼做為依據來建立 Index 的話，它的 Index tree 就有如上圖所承現．這一個 Index tree 我們就稱為 Clustered Index，也就是這個 Index 是依據決定實體順序排列的資料而建立起來的．其他種類的 Index 就稱為 Non-clustered Index．

所以，你就能知道為什麼在建立 Clustered Index 的時候你只能建立一個，而 Non-clustered Index 可以建立好多個，那就是因為實體順序排列只會有一種．

在尋找資料時，Index 特別強大的功能是在於某一個範圍內的尋找，比如，你要找學生證號碼 5 號的資料，或是找學生證號碼大於 20 號的資料．這類型的範圍尋找對使用 Index 來說是最好的．而 Clustered Index 和 Non-clustered Index 在這方面又有什麼差別呢 ? Clustered Index 的建立是依據資料實體的排列順序，所以當你執行了一個 SQL command 如 select * from students where ( ID < 10 and ID >0) ，你就會發現這只需要讀取一個 page 而己，這是以上圖為例子．如果你執行了另一個 SQL command 如 select * from students where street = '1st'，假設有一個 Non-clustered Index 是根據 street 資料而建立的，所以當你要尋找 street = 1st 時，這一個 Non-clustered Index 就會被用到，而且很有可能會指到許多不同的 page，比如 1 號學生和 36 號學生都住在 1st street．所以，Clustered Index 的尋找所需要讀取的 page 數量理論上會小於或等於 Non-clustered Index 所需要讀取的 page 數量．

總結，對資料庫引擎而言，不論是 Clustered Index 或是 Non-clustered Index，尋找資料的過程基本上都是一樣的，由於這兩種 Index 的特性不同，所以造成 Clustered Index 所帶來的維護成本較高 (因為實體的儲存順序就是 Index 上資料的順序，要變動比較麻煩)，而 Non-clustered Index 所帶來的維護成本相對較低 (因為只要改 pointer 指到新的 page)．

閱讀全文

#36 Code Review - 檢視你的程式碼

不論是寫好一個新的功能或是修改 bug，在程式碼都能正確執行並且在 check-in 到 source control server 之前，一定都會有一個 code review 的動作．這件事情通常是由比較資深的人員或對整體程式較為熟悉的人員來執行．Code review 帶來的好處很多，在這裡不一一描述，這對比較資淺的人員或新進的人員來說是一件好事．透過 code review，新進或資淺的人員可以比較快進入情況．有時我們進入了一個龐大程式碼專案，短時間之內蠻難完全了解所有細節和該團隊寫程式碼的文化，所以透過 code review 來了解程式碼，也是一種學習．

如果你工作的地方有執行 code reivew 的動作，真的恭喜你，畢竟教學相長，透過檢視彼此的程式碼是一種良好的學習方式．因為這跟團隊文化與團隊技術能力與要求上有很大的關係，所以 code review 實在很難說有什麼標準可言．除了程式碼要符合團隊的寫作規定外，要求嚴格的團隊甚至是極為嚴苛的地步．

接下來，我分享一些我以前在 code review 中學習到的經驗．

1. 每個公司或團隊因為人的不同，所以要求的標準也不同，先不用假設對方是來找你麻煩，如果他對你寫的程式碼有意見，他一定能說的出原因，讓你相信他是對的．

2. 如果你寫的是 Java/C# 之類的物件導向的程式，可能就有點小複雜．因為同一個功能因每個人對物件設計理解程度不同而會有不同的設計，再加上會導入一些 pattern 等因素，容易造成你不明白全部的內容時，就犯了一些錯．也不用過於放在心上，這種事情是常常發生的．

3. 以我個人而言，在程式碼效能發揮到極致後，程式碼寫的簡單乾淨好閱讀就行了，但是你很可能會遇到資深的工程師要求你要改的更簡潔．例如，

bool visited;
if (isActive == true) {
    visited = true
}

改成

bool visited;
visited |= isActive

基本上這兩個邏輯是一樣的，如果你被要求要寫成下面那樣的語法，就當做是個學習經驗吧!
其他像是變數名稱，物件名稱或屬性名稱也是會有類似的情況．

4. Comment 寫註解．做產品的公司會連註解也有嚴格的格式要求．如果是一般的程式註解，也是要寫到讓人看的懂，否則有寫跟沒寫是一樣的．

所以，如果你是新人，那就好好享受 code review 的過程吧，因為當你遇到一位功力深厚的前輩幫你 code review 時，保證你會收益良多的．

閱讀全文

#35 Coding面試 - LeetCode #94 Binary Tree Inorder Traversal

這題目出現在這 https://leetcode.com/problems/binary-tree-inorder-traversal/

如果要考 Tree 相關的題目，這一題算是相當經典的考試題目了．我想經典的原因就是 Tree inorder traversal 是資料結構課本裡面一定會教到的內容．大部份的課本裡面都會提供 recursive 的方式來做 inorder traversal，其程式如下

        public List<int> InorderTraversal(TreeNode root)
        {
            List<int> result = new List<int> ();
            if (root == null) return result;
            if (root.left != null)
                result.AddRange(InorderTraversal(root.left));
            result.Add(root.val);
            if (root.right != null)
                result.AddRange(InorderTraversal(root.right));
            return result;
        }

但面試官既然要考你這一題的話，絕對不可能只問你 recursive 如何寫，也一定還會問你怎麼用 iterative 的方式來寫．
如果你完全沒做過相關的練習，一時之間還真的很難想的出來該怎麼把 recursive 改成 iterative. 在這可以分享一件小事，因為寫 recursive 有階層的關係，所以程式的 call stack 就一層一層往上加，上一層結束回到下一層時也自然知道該從什麼地方繼續執行．但是若改用 iterative 的話，就沒有這種記住上次執行到那的好處了．對於這種需要記住位置的情況，就可以直接想想 Stack，因為 Stack 能幫助我們記住走過的痕跡．

所以，改成 iterative 的程式碼如下

        public List<int> InorderTraversal(TreeNode root)
        {
            List<int> result = new List<int> ();
            if (root == null) return result;
            Stack<TreeNode> stack = new Stack<TreeNode>();
            TreeNode node = root;
            while (stack.Count != 0 || node != null)
            {
                if (node != null)
                {
                    stack.Push(node);     // <-- 幫我們記住位置
                    node = node.left;
                }
                else
                {
                    TreeNode temp = stack.Pop();    // <-- 把上次記住的位置拿出來
                    result.Add(temp.val);
                    node = temp.right;
                }                              
            }
            return result;
        }

沒感覺嗎 ? 多寫幾次就會有了.

閱讀全文

#34 資料結構 - 非電腦科系的工程師們，你們體會多少了呢 ?

我第一次念資料結構時是因為準備台灣的資工研究所考試而念的，當時為了考試再加上時間也不夠多，所以念的很匆忙，沒有太多的時間思考著這門課程的精華．後來，念了研究所之後，研讀了一些學術論文，才慢慢了解到資料結構的精華．在許多學術論文裡都是討論著許多真實世界上的問題，通常這些問題會用一個數學公式或模型來表示，所以接下來的內容討論就可以直接在這數學公式或模型上直接去模擬．而這類的數學公式或模型若要用電腦程式來表達時，通常會發展出適合的演算法與資料結構．所以，這類的論文看多了之後，反而有幫助自己漸漸了解資料結構的精華．

基本上，電腦有二個基本的東西，一個運算器，一個是儲存空間．運算器就是大家所知的 CPU，而儲存空間就是記憶體和硬碟，其中記憶體是速度快但記憶時間較短，而硬碟是速度慢但記憶時間較長．這兩個東西你可以想成他們是長長的紙條，運算器可以在這長長的紙條上寫下資料，也可以讀取資料．

資料結構基本上就包含了兩件內容，一個是你需要用的資料是要寫在紙條上的何處，另一個就是如何在這些資料之間進行讀取或寫入．舉個例子，之前的文章提到 Array 這個資料結構．它的特性就是當你建立這個資料結構時，你必須先在紙條上找到一個符合你需要的足夠大的空間，而在資料之間進行讀取寫入的方式就是直接透過計算要讀或寫第幾個元素，就可以直接算出在紙條上的位址．例如，宣告了一個 byte array，一個有 20 個元素，如果第一個 byte 就是紙條上第 1000 個 byte 的位址，當我們要讀取第 5 個元素時，我們就知道要去 1005 byte 的位址上去讀取資料．

再舉另一個例子，Linked List．當你宣告了一個 Linked List 時，一開始你會先加入一個元素，這個元素可以寫在紙條上任何足夠空間的地方，而當你再加入另一個元素時，此時運算器就在紙條上任意一個足夠空間的地方把資料寫下，然後再回到第一個元素的位址上，把第二個元素的位址寫在第一個元素的空間中．所以，你可以知道在每個元素的空間中，除了元素的資料以後，還有下一個元素的地址．因此，當你想知道這個 Linked List 有多少元素時，你就必須從第一個元素一直讀到最後一個元素．

因此，課本裡面教的都是一些最基本的資料結構，就好像數學裡的四則運算一樣．電腦世界裡面的執行過程都是把紙條上的資料讀過來寫過去．當你發現你需要的問題很難用這些基本的資料結構來表達時，這時就是可以發明新的資料結構的時候了．

也許你會問，那這些跟平常的工作有什麼關係嗎 ? 比如，每天都在寫 JavaScript 搞前端畫面或是都在寫 java 寫後端程式．其實，多多少少會有關係的，尤其是你用物件導向在寫程式時，你所宣告的 class 就像是你定義了一種資料結構，這個 class 裡面所用到的儲存方式和運算方式都會大大地對程式在各方面有影響．就像是你知道了 Array 和 List 有何不同，你才會選得較適合的資料結構，也才能寫出比較快的程式碼．

未來的文章，不論是討論資料庫或是面試題目，你們都可以好好地思考一下是否還有其他可用的資料結構．不同的資料結構就代表程式的內容是不同的，可能會更好，也可能一樣，但也可能更差．所以，非電腦科系的工程師們，你們體會多少了呢 ?

閱讀全文

#33 資料庫基礎 - 什麼是 Index

Index 在資料庫的領域裡算是很基本且極為重要的項目，因為它幫助我們可以在龐大的資料裡快速地找到資料．這一篇文章就來說明 Index 運作的原理．

Index 也是一種典型的用空間換取時間的做法．這感覺就像是書籍裡最後面會有一些專有名詞在那一個頁數中可以找到，透過書籍的 Index，你可以很快找到你要找的專有名詞．同樣的，在資料庫裡也是類似像這樣的做法．資料庫引擎可以將你感興趣的資料製做成 Index，如此一來，資料庫引擎只要在 Index 上尋找目標，就可以很快速地得知該筆資料的位置是在資料庫檔案裡的什麼地方．這些就是 Index 概念．舉個例子，在資料庫裡有一個學生資料的表格，表格的 primary key 是學生證號碼，其他的欄位有名字，班級，地址，電話，性別等等．誠如以前的文章曾提過，這個表格有 primary key，所以基本上來說資料庫引擎就會以 primary key 的排序順序做為資料在 page 上儲存的順序．因此，當我們用學生證號碼做為尋找資料的依據時，資料庫引擎就會在 page 上依序地找出我們要的學生證號碼那筆資料．這是在沒有 Index 的情況下．如果你腦筋動的快，你會發現既然學生的資料已經是用學生證號碼排序好了，當我們要用學生證號碼來尋找時，何不用 binary search 呢 ? 沒錯，若你能這樣想，恭喜你已經漸漸習慣了用電腦科學來想事情了．但在這裡，binary search 真正能派上用場嗎 ? 那就要看資料是用何種方式儲存在 page 裡了．如果是用 directory based 的方式，還可行，但若是其他的儲存方式，那基本上不太實用．所以，為了不受儲存方式的干擾，我們可以用更多的空間來儲存成一個方便資料庫引擎搜找的資料結構，同時也享受快速尋找的好處．於是，有什麼資料結構適合呢 ? 答案就是 Tree．

如果我們把學生證號碼做成 Tree，如下的範例圖:

圖中數字為學生證號碼．資料庫引擎會依據學生證號碼的資料做成 Tree，也就是圖片上 Index tree 的部份，然後在 Index Tree 的末端節點上會放入該筆資料位置的 pointer．因此，只要 Index 一建立好之後，資料庫引擎就可以在 Tree 上遊走尋找想要的資料，若找到目標時，也可以馬上切換到該筆資料的位置．這就是為什麼透過 Index 的使用可以讓資料庫引擎快速找到資料的原因．

如果現在的情況改成要用學生的名字來做為搜尋目標，那麼上圖的 Index 就幫不上忙了，因為那個 Index 是以學生證號碼來建立 Tree．所以若我們希望用學生名字來搜尋時也能像之前的效果一樣，則資料庫引擎就必須以學生名字再來建立另外一個 Tree．所以，Index 的建立就必須是有意義的，如果隨便建立一些資料庫引擎用不到的 Index，那只是增加了資料庫引擎對資料維護上的成本而且也浪費更多硬碟空間．

這篇文章先為基本的 Index 概念先開個頭，之後的文章會再來介紹更多有關 Index 的故事．

閱讀全文

#32 資料庫基礎 - 資料讀取的成本評估

在前面的文章裡曾提供當資料庫引擎要儲存資料時可能有三種方式可以選擇，分別是 heap file, sorted file, 和 hashed file.

Heap file

基本上就是沒依照任何的規則來儲存資料，也就是說你先把資料A寫進去，然後再寫資料B，則自然而然地 A 的位置就會在 B 的前面．正常情況下，我們似乎不太希望用這種方式來儲存資料，因為它對資料搜找的速度上並沒有什麼幫助．

所以，假設資料一共分佈在 p 個 pages，然後每個 page 的讀取或寫入的平均時間為 d，那麼在尋找資料時所花費的成本便是 p*d，這是以最壞的情況來看的，因為我們無法知道我們要找的資料是在前面的 page 還是後面的 page，所以在成本評估時就用最壞的情況來看．

如果做 insert 動作，heap file 的特性會讓新的資料一律從最後面加入，所以必須要從第一個 page 走到最後一個 page，然後再做寫入的動作，所以寫入的成本是 p*d+d．

如果換成是一個資料刪除的動作，那就是尋找資料的時間再加上一個資料寫入的時間，所以也是 p*d+d．這也是以最壞的情況來打算的．

如果我們平均來看的話，假設需要找的資料有一半在前面一半的 page，另外一半落在後面一半的 page，而每筆資料都會被尋找，則搜尋的時間成本就可以想像成 p/2 * d，也就是說長時間下來每一筆資料都會被尋找，所以搜尋成本才會除以2．同樣的想法也可以推廣到 delete 的動作．Insert 的動作都是加在最後一個 page，所以平均來看的話，這並沒有差別．

Sorted file

資料會依照某一個規則來排放在 page 之中，這個規則如果能讓每筆資料能顯露出獨立的效果是最好的，比如依照身分證號碼或是員工編號，但這不是必要條件．我們也可以用員工的姓氏來做為排列的規則，這樣至少你可以確定同一個姓氏的員工資料就會被放在同一個或是附近的 page．所以，我們可以明確地知道如果資料是用 sorted file 方式來儲存，這將對於搜尋會很有幫助 ? 為什麼呢 ? 還記得之前文章曾提過的 binary search 嗎 ? 當資料以某一種規則排列好時，binary search 可以讓搜尋更快速，有多快呢 ? 還記得 binary search 的時間複雜度嗎 ? 它是 O(log n)，再重複一次，在電腦科學的世界裡，大部份的情況下 log 是以 2 為基底．

因此，對於 sorted file 而言，尋找資料的成本就是 log (p*d)，這裡的 p 和 d 跟前面的定義是一樣的．

如果是 insert 的動作，因為這是 sorted file，所以需要找到適當的位置然後再做 insert 的動作，所以 insert 的成本就是尋找 + 寫入，因此就是 log (p*d) + d，前提 insert 動作不會造成 page split 的現象發生，也就是說 page 裡面有足夠的空白空間可以寫入新資料．

如果是一個刪除的動作，資料必須要先找到，然後再加上寫入的動作，所以成本也是 log(p*d) +d．以上這些成本評估都是基於資料排序的規則會被應用到，比如，如果是員工資料用員工編號來排序時，那麼資料在被尋找，被新增與刪除時，都必須提供員工編號才能達到上述的成本評估．

Hashed file

Hashed file 的安放方式是讓資料經過 hash function 的計算之後才決定要放到那一個 page．如果 page 有足夠的量而且 hash function 夠好的話，就不會有 overflow page 的發生，也就是說 hash function 計算出一樣答案的資料在同一個 page 能提供足夠的空間了，不需要再連結到其他的 page．由於 hash function 的時間複雜度是 O(1)，所以這是相當有吸引力的儲存方式．

因此，如果是要找資料的話，只是經過 hash function 運算，然後就知道去那一個 page 進行讀取，所以成本是 d，這前提是沒有 overflow page．如果有 overflow page，那成本就還是加上拜訪這些 overflow page 的成本．

如果動作是 insert，一樣經過 hash function 運算後，就知道要去那一個 page 進行資料寫入動作．假設該 page 仍有足夠大的空白空間，則成本也是 d．如果動作是 delete，一樣經過 hash function 運算後就知道要去那一個 page 做資料寫入的動作．假設沒有 overflow page 的情況，則 delete 的成本也是 d．

你可能會覺得用 hashed file 有很好的成本效果．在真實世界的情況下，資料量通常會大，當然硬碟空間也相對地很大，所以 page 的量也會很大．如果你今天要找的資料是很接近的，比如要找員工第一號和第二號，用 hashed file 的方式很可能會造成兩筆資料會被儲存在相距很遠的 page，雖然資料庫引擎很快就計算出來要去那些 page 抓資料，但是硬碟就會忙於東奔西跑去讀取資料，所以也別被 hashed file 的低成本給騙了．

不同的實體儲存方式都有各自的優點和缺點，資料庫引擎會看資料的情況或管理者的安排來決定什麼樣的安排方式會比較好．如果我們不是專門的資料庫管理員，這種實體的儲存方式通常不需要我們來操心．但若你是專門的資料庫管理員而且資料已經成長到相當大的數量時，此時你就必須要知道你的資料是如何被儲存，這樣才能幫助你思考效能改進的事情．再講下去的話就會偏向市面上的商業產品與工具了，所以就到此打住，畢竟此網誌儘量不講產品和工具，只講跟電腦科學有關的想法．

閱讀全文