#22 資料庫的資料實體儲存單位 Page - 3

在來延續上一篇文章 (#21  資料庫的資料實體儲存單位 Page - 2) 的內容．在上一篇的文章中看到了如果沒有 page 的概念時，資料庫引擎有那些可行的方法來在硬碟上管理資料，從上一篇文章中，你看感受到空白空間的處理與以及資料的定位並不是很方便．於是在階層管理的方便性上多加了一層 Page．

在一般市面上常見的資料庫產品中，Page 的大小都大約在幾Kb之間，類似於作業系統的儲存單位大小．所以，一個資料庫可能會包含一個或多個資料庫檔案，而每一個資料庫檔案都會包含多個 Page．

我們再看看如何用 Page 來管理資料．如上一篇文章的情況，資料有可變長度與固定長度兩種．固定長度的情況是比較單純好處理，可以參考下圖:

上圖是某一個 Page 的示意圖，由於每筆資料都是固定長度，所以每一個 Page 都可以儲存相同數量的資料筆數 (除了最後一個 page 可能因為資料筆數無法除盡，所以不一定有相同筆數)．在每個 Page 的最後面會留下一些小空間用來做為目錄式的記錄，所以可以從這小空間中可以知道這一個 Page 一共儲存了多少筆數的資料，同時也可以知道每一個位置是不是都有資料．以上圖為例，我們透過 delete 語法刪除了一筆資料，而這筆資料剛好是位在這個 Page 的第二個位置，所以可以看到在目錄式記錄上第二個位置是 False (boolean)，用一個 bit 就可以表達完成．所以，當有新資料要寫入時，資料庫引擎就可以讀取每個 Page 上的這目錄就可以知道那一個 Page 有多少的空間是可以寫入新資料的．因此，這種實作方式對 storage manager 的開發者來說相當簡單，而且空白空間也易於維護．

另一個情況是可變長度的資料．因為每筆資料的長度不見得會一樣，所以每個 Page 能放多少筆的 record 完全得視實際上每個 record 的長度來決定．在 Page 上安排位置時，在 manifest 那段小空間裡所放的內容就會有點差異了，如下圖:

由於資料非固定長度，所以在 manifest 上每一個位置都會有一個 pointer 指定到那個資料的位置，同時也會指出來空白空間是從什麼位置開始．上圖的狀態等於是資料經過了一些 update/delete 指令後才會出現的情況，因為每筆資料之間還是有空白空間的存在，但那些空白空間不會被資料庫引擎所使用，因為管理上實在太麻煩了，所以當有一筆新資料要寫入到這個 Page 時，資料庫引擎只會找這個 Page 上的空白空間 (灰色區塊)，只要有足夠的空白空間，那麼新資料就會被寫進來，同時更新 manifest 的相關 pointer 內容．

以上的內容是資料庫引擎對在一個 Page 內針對固定長度與可變長度資料的存取安排，所以你就可以想像的到當一個資料庫運行了一段時間之後，零零碎碎的空白空間一定是散落在資料庫檔案的各角落，而那些零零碎碎的空白空間是不會被資料庫引擎所使用．所以，資料庫的產品通常都會一個功能把這些零零碎碎的空白空間給消除，也就是讓資料靠的更緊密些，讓儲存空間可以在容量上得到發揮更好的效果．

閱讀全文

#21 資料庫的資料實體儲存單位 Page - 2

延續上一篇文章 (#19 資料庫的資料實體儲存單位 Page) 的內容，在這篇文章裡，我們來談談有關資料庫的實體儲存結構．所謂的實體儲存結構是指資料放在硬碟中的情況．

首先，我們先來看看一個很簡單的結構，資料長度是固定的．這種情況在前面的文章有提過．因為長度都是固定的，所以每筆資料的長度便可以固定，這樣好處是在於方便計算也方便存取．

另一種情況是資料長度不是固定的，這種情況在前面文章也有提過．因為長度不是固定的，因此必須要想一個方法把不同欄位的資料做一個區隔，這樣在讀取資料時才知道什麼情況下是資料欄位的終點．在實體資料儲存時，有兩個方式可以來達成這種目的．第一，在每個資料欄位之間都用一個特殊符號隔開來，長相如下:

上圖是用一個 # 來當特殊符號，這是很笨的例子，但只是方便說明用．在資料寫入到硬碟時，資料欄位之間會透過特殊符號做為間隔，而在讀取資料時，資料庫引擎也知道該如何處理資料了，而這樣的好處就是非常直覺且簡單，並不會浪費多餘的硬碟空間，缺點就是會浪費較多的資料讀取時間，例如我只要讀取表格裡欄位五的資料，那麼資料庫引擎就必須從欄位一讀取過四個特殊符號才能取得欄位五的資料．從前面文章中，你應該有學到一個精神就是當你對時間不滿意時，那就犧牲點空間去換取時間．所以可以把上述的儲存方式最一點小改良如下圖:

在整筆資料的最前面加上一個導覽式的目錄，裡面存放著每個資料欄位開始的位址起點，所以每筆資料有五個欄位，因此目錄裡就有五個 pointer，而每個 pointer 的內容就是一個硬碟位址用來記得資料的起點．所以當資料庫引擎要讀取欄位五的資料時就不用從欄位一開始讀取了，可以透過目錄裡的第五個 pointer 就可以直接找到欄位五的位址．

以上所說的方法都是很直覺且自然的，但我們來想像一下如果進行資料更新或刪除時會發生什麼事情?

先針對資料更新來討論，如果把欄位三的內容更新成較小的內容時，此時影響不大，只是欄位三後面會有空白空間，而我們該討論的是該不該保留這個空白空間．因為這裡討論的是每個資料欄位都有一個 pointer 會對應到資料，所以若我們保留空白空間的話，可以讓資料少了些移動，但也可能會浪費許多細小的空白空間．如果此時的情況是欄位三的內容被更新成比較大的內容時，例如更長的字串，接著就面臨到沒有足夠的空間問題了，解決方法會有很多種，也許比較簡單的是把整筆資料搬移到足夠大的空間，好讓欄位三可以容納下新的內容，同時前面的五個 pointer 的內容也需要一起改變．如果是刪除呢? 那就更單純了，只要把整筆資料在刪除或是做一個已刪除的 flag 即可．所以，從這裡我們可以看到，其實在更新時所面到的挑戰是比刪除的挑戰還要大很多．而且不論是那一種更新 (內容變多或變小)，都會遇到空白空間管理的問題．

所以我們可以發現，當資料庫的資料筆數越來越多時，讓資料庫引擎直接去對每一筆資料做管理時，其實是有點不方便的．因此，我們需要在這中間多一層實體儲存的管理單位，而這管理單位就是我們前面文章中所介紹的 Page．這種感覺就有點像一個國家不可能直接管理到每一個家庭，中間一定會有省，市之類的層級來做為分類，以便於管理上的應用．而 Page 也就是這樣的感覺．

閱讀全文

#20 The Power of Ten - 撰寫可靠軟體的思維

標題為 The Power of Ten - Rules for Developing Safety Critical Code 的文章刊登在 IEEE Computer 2006 年 6 月的月刊中，作者是位在 NASA JPL 實驗室的研究科學家，同時也是位學者和工程師．這篇文章可以在 http://spinroot.com/gerard/pdf/P10.pdf 看到．

若以武功修練來比喻的話，這篇文章就像是一個得道高人所寫下來的內功心法，他把自己在 JPL 實驗室工作的多年 C 語言工作心得濃縮成十項重點，作者也為每一個重點留下說明．雖然這一篇文章是將近十年前的文章了，但它的參考價值極高，而且我相信許多資深的軟體工程師幾乎都會同意作者所寫的內容．

其中有幾點並非在所有的程式語言中都會碰的到，尤其是跟記憶體管理有關的工作．以現在一般商業應用裡最常見的 C# 和 Java 語言都應該有其 runtime 環境的設計，所以記憶體管理的工作並不在程式設計者上，而是在開發其語言的公司上，所以這樣等於你把記憶體管理的工作交給其他人來處理了．我想這對 NASA 來說應該是不太能接受的事情，畢竟能打上太空的物體都是極為龐大的資金，因此 NASA 應該是不可能用類似像 C#, JAVA 這般的語言來打造火箭或衛星要用的軟體．回歸最基本的本質，用 C 應該是相當原始且基礎了．所以，在那篇文章裡，作者談了一些與 C 語言有關的準則．在這裡我不談特定語言，我們來看看其他的通用的準則．

1. Restrict all code to very simple control flow constructs – do not use goto statements, setjmp or longjmp constructs, and direct or indirect recursion.

這一點應用也沒什麼好再做說明的了，就是這樣，沒有 GOTO，沒有 recursion．所以在前面的文章裡，有些程式的寫法我提供了 recursive 和 iterative 的寫法，那時也提過 iterative 的寫法是比較好的．

2. All loops must have a fixed upper-bound. It must be trivially possible for a checking tool to prove statically that a preset upper-bound on the number of iterations of a loop cannot be exceeded. If the loop-bound cannot be proven statically, the rule is considered violated.

你想想看你寫程式時做到了這一點嗎? 你有沒有做過 while (true) 之類的語法呢 ?

4. No function should be longer than what can be printed on a single sheet of paper in a standard reference format with one line per statement and one line per declaration. Typically, this means no more than about 60 lines of code per function.

這是一定要的．若以 OO 的角度來看，有一個 function 能寫的很長，我都會懷疑程式碼一定在某些地方會有重覆功能的現象．

5. The assertion density of the code should average to a minimum of two assertions per function.

每個 function 平均來說至少有兩個檢查．這邊的檢查就是要防止一些不尋常的參數發生．比如你今天要寫一個加法，接收兩個 int ，如果傳入的參數是負數，那你的程式能處理嗎? 或是加起來的數字 overflow 了，你的程式能處理嗎?

6.  Data objects must be declared at the smallest possible level of scope

這應該是很直覺的想法，因為你不需要把不相干的資料物件提供給不需要該資料物件的程式碼．

7.  The return value of non-void functions must be checked by each calling function, and the validity of parameters must be checked inside each function.

這應該是每一個程式工程師要做的，只要呼叫的參數皆符合要求，那麼回傳值也需要檢查，同時還要注意是否有可能會產生其他的 exception ，都要記得做好 try catch 的反應動作．

10. All code must be compiled, from the first day of development, with all compiler warnings enabled at the compiler’s most pedantic setting.

最後這一點就是在考驗你們的專案裡有沒有良好的軟體工程流程以及 build system．工程師們一旦把程式碼 check-in 之後，所有的程式就應該要重新編譯，然後所有的測試案例都要執行．這樣才能即早發現問題，即早解決．

閱讀全文

#19 資料庫的資料實體儲存單位 Page

在上一篇文章中提到了有關資料庫 Storage manager 一點點的資訊．因此，這一篇文章就來談談更基礎的東西，叫 Page．它是什麼呢 ? 它就是 Storage manager 在處理儲存資料上的一種邏輯格式，也就是每個邏輯儲存空間的大小．這樣說可能還不好了解，讓我來直接舉個例子．資料庫引擎中有一個管理員叫 storage manager，它是負責資料儲存和讀取用，也就是說，今天使用者發出一個請求如 select * from table123，那麼這個命令就會經由資料庫引擎裡各式各樣的管理員來做語法確認解析，來做語法最佳化，然後可能還會經由其他管理員的檢查，最後才會到 storage manager，而 storage manager 負責的工作就是到磁碟機上正確的位置點，把資料讀取出來然後再回傳給呼叫它的管理員，最後資料就一直這樣被回傳到使用者端．因此，storage manager 就是負責找到資料在硬碟上的那個地方，然後進行資料讀寫．所以，你現在可以知道 storage manager 的工作是非常底層的．

那 Page 和 storage manager 又是什麼關係呢 ? Page 是資料儲存空間的一種單位．依不同的產品設計，Page 的大小可能不同，如 Microsoft SQL Server 的 Page 設計成 8KB. 所以，如果你的資料庫檔案設定為 8000KB，那就表示你這個資料庫檔案就有 1000 個 Page．然後這一千個 page 並不是全部都可以做為使用者資料儲存的用途，因為需要有一些空間用來儲存資料庫的設定與變數等，但我們在此先不討論這些系統所需的空間，我們把 1000 個 page 視為都是可供使用者儲存資料用．而 Page 設計的概念就是我們以前說過的 Linked List 概念，所以 Page 裡會有一個 pointer 指向下一個 Page 在那裡，因此，相鄰的 Page 在實體位址上不一定要在隔壁，他們可以分別位在硬碟裡前後不同的位置上．

所以，假設你現在要寫入一筆資料到一個新的表格，也假設這個表格只有一個欄位，其 data type 是 char(1000)，而且這個欄位是 primary key．當你寫入第一筆資料 "1111" 時，這筆資料就會被記錄在 page 1 的最前面，如果你寫入第二筆資料 "2222" 時，這筆資料也會被記錄在 Page 1 且在 "1111" 的後面，如下圖所示:

在上圖中，假設寬度剛好是 1000 字元，所以你會到 "1111" 在第一行，由於 data type 是 char，所以後面有 996 個空白，而第二行是 "222"，後面接著是 996 個空白字元．如果你繼續寫入更多的資料時，第一個 Page 看起來就會如下:

如果你再繼續寫入資料的話，後面的資料就會從第二個 Page 開始寫．所以 storage manager 在讀取這表格的資料時就會從這個表格的第一個 page 開始讀資料．

假設，此時你要寫入 "4567" 到這個表格中，因為這個欄位是 primary key，所以預設上來看，字元的順序就是實體資料要擺放的順序，因為 "4567" 必須放在 "4444" 和 "5555" 之間．但由於這一個 Page 的空間已被佔滿了，因此 storage manager 只好做一個 page split 的動作，也就是把一個 Page 拆成兩個 Page ，然後再寫入資料．

如果用 List 的動作來看，這就是在一個 List 中插入一個元素的動作．用 storage manager  的角度來看，它要先尋找一個完全沒用過的 Page ，然後將需要分開的資料搬到新的 Page 上，最後再更改 page pointer 位置來讓新 Page 的順序能安排在其中．這個動作並不是一個單純的動作，花費的成本還不小，從這裡就可以了解到，當我們做 insert 或 update 資料時，如果沒有安排好的話很可能就會造成大量的 page split 導致硬碟會很忙碌而形成效能上的瓶頸．

當我們討論到資料庫的讀寫效能時，Page 是一個很好的對象讓我們知道一份資料被讀取時一共讀了多少個 Page，這也就是代表了資料庫引擎的效能．由此可見，對資料庫引擎而言，這是多麼重要的基礎考量．

閱讀全文

#18 資料庫的表格裡有關 nchar 和 nvarchar 的選擇

今天正在思考要來寫個不學術的事情，也就是希望能寫個跟產品相關程度較高的主題，想著想著，突然有個回憶就突然閃過腦子．

大約在十年前，當時還在台灣念碩士班，有位在台灣 IBM 工作的朋友剛好介紹了一個很短期的工作，因為他們急著做一個專案，但臨時抽不出過多的人手來完成這些功能，所以就經由朋友的介紹去參與這項專案的開發，賺一點零用錢，只需要做 5 個 tasks 就行了．當時，我記得是用 Javva 開發，然後資料庫產品是 DB2．不過，當時我做的短暫工作跟資料庫並沒有直接關係．

有一天，我到專案辦公室時，剛好看到 PM 正在輸入一些新的 database schema，我好奇在他旁邊看著那些 schema 資料，然後我就發現了一件頗為特別的事情，所以字串相關的資料欄位都是設計為 nchar，比如 nchar(50)，nchar(100)之類的．於是，我就好奇一問 PM 為什麼所有的字串類的資料都是用 nchar 呢 ? PM 就馬上回答說，DBA 說這樣比較快．當我聽到這回答時，我似乎沒有完全明白為什麼這樣比較快．就這樣這個 nchar 與 nvarchar 的快慢問題就一直放在腦裡，沒特別去找答案，一切看何時有機會能遇到答案．

過了幾年後，我到了美國念書，某一個學期修了一門資料庫的進階課程，而當時的授課教授是一位印度人，他的實驗室有一個拼裝版資料庫引擎．所謂的拼裝版的資料庫引擎就是許多的功能都是由他的學生們經年累月的拼裝而成，有些是自己開發，有些是透過一些 open source 的引用，而當時我要拼裝的功能是 index search．

為了要製做 index search 用的 B-tree，我就必須學會如何透過該資料庫引擎的 storage manager 取得我需要的資料．就在了解 storage manager 的過程中，我無意間發現了一件事情而勾起了多年前的回憶，也就是 nchar 與 nvarchar 的差別．首先，我必需聲明的是 DB2 不一定是用一樣的方法，但我想以本質的精神來說是相似的．

在了解 storage manager 的過程中，我發現到如果資料欄位的 data type 設定為 nchar 時，這個固定長度會反應在硬碟的空間上，例如 nchar(500)，在硬碟上你會發現每一筆資料在硬碟上就一定會有 500 字元的長度，換句話說，你寫入進去的字串也許只有 10 個字元，但最後被放在硬碟上時還是有 500 字元的長度，而前面 10 字元是資料，後面 490 字元是空白．對熟悉資料庫的朋友們來說，這本來就是技術文件上會講的事情，但為什麼 nchar 會比較快呢 ? 那就必須再來看看資料庫引擎是如何處理 nvarchar．比如說 nvarchar(500)，你寫入進去的字串有 10 字元，在硬碟上所使用的空間就只有 10 字元，而不是 500 字元．直覺的反應下，你可能會覺得這樣跟快慢有什麼差別呢 ?

當我繼續往下看 storage manager 的程式碼後，我才發現到答案就在這裡．
我們來舉個簡單的例子，假設有一個表格，它的定義和範例資料如下:

ID - int	公司名- nchar(50)	地址- nvarchar(300)	電話- nchar(12)
1	公司 A	台北市忠孝東路1段1號1樓	02-12345678
2	公司 B	台北市忠孝東路3段300巷10弄100號5樓	02-87654321

ID 是這表格的 Primary Key，所以資料就會按 Primary key 的順序寫在硬碟上，而每一欄位寫的順序也就是跟其定義的順序一下，所以你會看到在硬碟上，寫第一筆資料時，第一個欄位是長度是固定的，第二個欄位也是也是固定的，第三個欄位不是固定的，最長可到 300 字元，而第 4 個資料是固定的．那麼問題就在此時出現了，以我們之前講過的 Array/List 來類比，如果你今天要讀取一個長度是固定的資料，你會怎麼讀取呢 ? 簡單的方法就是你會告訴 storage manager 說我要在某一個位置開始讀取 50 bytes 的資料，這樣對 storage manager 就很省事．如果情況變成長度是不固定的，就像表格的地址欄位，此時 storage manager 就不能如此瀟灑地直接讀取 300 bytes 的長度了，因為第一筆的地址沒那麼長，會把電話也讀進來了．因此，storage manager 就必須要先去 "探索" 一下這一個長度到底有多長才能決定要讀取多少長度的 bytes．就是因為這樣的 "探索" 讓 storage manager 多花費了一些作業成本，因此才變成 nchar 比較快的感覺，這正好呼應了當年在執行那個 IBM 專案時所得到的答案．以上是從讀取的角度來看．若從寫入的角度來看，你就會發現還真的很麻煩．以上述表格的資料為例子，如果今天第一筆的地址要更新成跟第二筆的地址一樣，那該怎麼辦 ? Storage manager 要寫入更長的地址資料時卻發現了原本的的地址長度不夠了，若強行寫入就會把電話資料給覆蓋掉了．你可能會想那就把電話資料往後挪，這樣的話也就會造成第二筆資料都要往後挪，如果這表格有成千上萬筆的資料，你一定不會認為這是個好方法．比較簡單但也是花費較大成本的方式就是 page split．至於什麼是 page，什麼是 page split，這是一個可以做為下一篇文章的好主題．

最後，你以為用 nchar 是最好的嗎 ? 固定長度也不是十全十美，因為固定長度的資料會被全部讀出來，以上述公司名來說，大部份的公司名只有短短幾個字，可能只有少數幾家公司的名字很長，但每次讀取還是會讀取 50 bytes，所以這 50 個bytes 就會從資料庫被讀出來，然後在網路上傳送到客戶端，客戶端的應用程式也是收到 50 bytes，但你需要的資料可能只有 6 bytes 而己，你會發現後面接著一大串的空白，必須自行將空白拿掉.

因此，nchar 和 nvarchar 到底那一個好那一個快，看來就要視你站在什麼角度上來看待了．至少我能告訴你的是以資料庫引擎的角度來說，nchar 的資料的確是簡單處理多了，但這不代表客戶端應用程式或網路效能也一定會如此同意．

這是一個小小的問題但背後連接到一個程式寫法的事情，下次你遇到這問題時，可以問問你的團隊技術領導者，看看他能否給你其他更多的思考．

閱讀全文

#17 客戶說程式碼不能有 recursive function，該怎麼辦 ?

不知大家有沒有被客戶這樣要求過，寫程式一律不準出現 recursive 的寫法．這也是十年前左右的故事了，並不是我個人遇到的狀況，是我朋友們遇過的情況．當時對這樣的要求沒太多的頭緒，不過心裡還是把這問題放著，也許有一天我會知道為什麼．

後來，有一次因為一個考試，突然讓我想到這個問題可能的答案，從技術角度來看的話，我想這應該是客戶的顧慮．情況是這樣的，在作業系統中，每個工作被執行的單位是 Process．一個作業系統裡會有許多的 Process 在執行，分別負責不同的功能，例如，有 Process 是專門負責處理 DNS 封包，有 Process 專門負責與印表機的通訊．所以，我們若自己寫一個程式在作業系統裡執行，這個程式也將是一個 Process，作業系統也就會負責他所需要做的工作內容．

在每個 Process 裡都會有一個獨立的記憶體空間用來儲存該 Process 需要的變數與資訊，其中有一項資訊叫 call stack，簡單的說是你的程式某個 function 呼叫了某個 function，然後再呼叫其他的 function，一直呼叫下去到作業系統的核心．因為這個記憶體空間的大小是有一個固定的量，所以當呼叫 function 一直無窮盡的進去下去的話，就很容易造成這個記憶體空間不夠用了，而形成了 call stack overflow 的情況．一旦這情況發生了，該 Process 就會被迫中止．

如果以作業系統的角度來想，程式裡不包含 recursive 寫法是很重要的．所以，一般的習慣都會採用 iterative 的寫法來取代 recursive 的寫法．在前面的 Binary search 文章裡，我們有介紹到 Binary search 的 recursive 寫法與 iterative 寫法．不同的情況會用到不同的寫法技巧，以 Binary search 來說，就是用兩個額外的 index 來做，如果是 Tree traversal 的話，通常是用 Stack 和 List 來把 recursive 寫法改成 iterative 寫法．

未來遇到適當的內容時，再來說明不同的 recusrive 寫法是如何改成 iterative 寫法.

閱讀全文

#16 我是非電腦科系的，真的需要懂這些嗎 ?

這問題其實一個很好的問題．

我假設你是個非電腦科系畢業出身的軟體工程師，回想一下，你當初憑著自己的邏輯能力學習如何寫程式，也學習如何善用大家所熟知的 framework，便可以應付自己工作上所遇到的問題．我想那是因為你的工作以及所面臨到的專案都是屬於商業型導向的應用程式．我所謂商業型導向的應用程式就像是你在金融界中工作，每個需要處理的就是把資料讀出來做報表，或把資料新增進去到資料庫，或是把這資料用某一種格式包裝起來，然後傳到其他的系統再做更多的資料處理．又比如說你在不同領域裡做該領域的工作，例如在航空公司做訂票系統，在電信公司做帳務系統，在電子商務公司做庫存系統．這些軟體工作其實在台灣是佔大多數的．所以，在這些工作中，若你沒有懂這些資料結構或演算法，你照樣也可以把程式寫出來，系統照樣地可以上線，公司照樣可以營運賺錢．因為我自己也曾有過這一段路，所以我知道是可能的．

不知你是否曾問過自己，我怎麼知道我寫的程式是不是好的，我該怎麼評估，或是別人又會怎麼看待我的寫程式能力．我相信非電腦科系畢業的人在做軟體工程師時一定會有這樣的問題．如果你有這樣的問題，很恭喜你，因為你的內心對知識有了渴望，因為你想知道自己的能力或寫程式的技巧是在什麼程度．所以，最好的方法就是回到事情的本質去找答案．因此，資料結構是需要懂的，演算法也是需要懂的，但我們並不用像 Microsoft 或 Google 工程師那樣了解所有的細節，我們只需要知道最基本的道理，這樣就能幫助你了解當某個產品某個新功能出現時，那些大公司的工程師是怎麼做出來的．比如，之前的文章談過 ArrayList，到底是 Array 還是 List，.Net framework在台灣還算流行，幾年前 Microsoft 把基本的 .net library 都開放原始碼了，所以你可以去看看 Microsoft 的工程師是如何設計 ArrayList，看它到底是 Array 還是 List．

若你從前面的文章一直看到這裡，到目前為止你可以發現我講了很多有關時間複雜度和空間複雜度的事情．所以，你就知道我們寫程式時會在乎的事情就會包括這兩個，而別人看待你的程式好壞時，自然而然也會從這兩件事情來思考．考慮程式的好壞的因素很多，而時間複雜度和空間複雜度算是最基本的要求．

所以，即便是一般的商業型應用程式，你也可以回頭去看看你以前寫的程式碼，是不是有些地方可以用 Hash table 能加快資料處理，是不是有些地方可以用 Binary search 能加快資料搜尋，是不是有些地方可以用了 Stack 讓程式更簡單好寫了．透過這種的改進，我相信你寫的程式一定會更有品質．因此，資料結構和演算法是很重要的，在未來的各項主題中都還是會一直介紹下去．

閱讀全文

#15 資料結構 Tree

Tree 應該是我們所需要介紹的最後一個基礎的資料結構了．在資料庫的領域中，你可以看到 Tree 在那裡發揮的淋灕盡致．以我個人來說，我喜歡把 Tree 看成是一種 List 的變形金鋼．前面在談論到 List 時，你可以發現 List 的元素後面只會接著一個元素，就這樣一個一個串接下去，這種情況就可以用在作業系統的檔案儲存．你可以把一個檔案想成是一個 List，而檔案的內容就會依照固定的大小分割成很多個元素，然後依照順序排好串在一起，這些元素就會散落在硬碟空間中，他們不需要排列在一起，所以同一個檔案的內容在放置時，可能是最後的元素放在硬碟空間前面的位置，因為元素之間都有一個 link 記錄下一個元素的位置在那裡．

對 List 來說，如果一個元素有一個 link 的空間來記錄下一個元素在什麼地方，這稱為 Single link list，也就是說元素往下走了之後就回不來了，除非從頭開始．如果一個元素有兩個 link 空間，一個用來記錄下一個元素在那裡，另一個用來記錄上一個元素在那裡，這稱為 Double link list，可能在一個元素上往前走或是往後走，但這種的實務上的應用比較少些．對於 Tree 來說，它有多個 link 可以記錄下一階層的元素在那裡，所以用畫圖來表示的話，看起來就像下圖．

以上圖來說，Tree 的資料結構是:

Class TreeNode {
    public TreeNode left;
    public TreeNode middle;
    public TreeNode right;
    public string Data;
}

一個元素可以連結到三個元素，這個跟 List 的元素只有連結到一個元素是不太一樣的．也許你會提出問題，連結到一個元素和連結到三個元素或是更多的元素有什麼差別呢 ? 差別當然很多項，以我目前來看，我覺得最大的差別在於找到元素的速度．舉個例子，如果你用一個 List 來儲存一系列的數字，即便是這些數字已經依照某一個規則排列好，你在找時還是要從 List 裡的第一個元素開始，然後一個一個往下找．所以，如果都沒找到的話，你所花費的時間複雜度就是 O(n)．現在，相同的數字依照某個特定的規則製做成 Tree 的結構，而當你找某個數字時，只要從 TreeNode 某一個節點繼續往下找即可，所以每當經過一個節點往下一階層時，你就已經捨棄了 2/3 的內容，只剩下 1/3 的內容要找．所以找起來的時間複雜度是 O(logN)，這裡的 log 是以 3 為底，因為 TreeNode 可分為三個節點．

這時你可能會認為如果 Tree 在搜尋資料上是這麼好用的話，那我們是不是可以多用 Tree 少用 List ? 這就很難有一個正確答案了．雖然 List 的搜尋時間複雜度是 O(n)，不過建立 List 是相當簡單的，但要建立一個 Tree 就不像 List 那麼單純了．如果你建了一個 Tree 而只拿它來用一兩次的話，這實在是不太符合效益原則．而且，Tree 的結構是適合用來做資料尋找的速度加快用的，而不太適合用來儲存資料，你想想如果今天有一堆數字要存在電腦裡，你把它儲存成 Tree 的結構，而接下來要把所有的內容讀出來，你覺得 Tree 結構所採用的方法會比 List 或 Array 來的更方便和簡單嗎 ? 答案顯然是不會的．再說，你把資料弄成 Tree 結構來儲存，在空間使用上並沒有佔到任何便宜．

所以，通常你看到一些資料索引的技術背後的基礎資料結構一定會採用 Tree 結構，原因就是加速資料尋找速度，但真正的資料並不會用 Tree 結構來儲存，只是索引所使用的資料是以 Tree 結構來儲存．許多資料庫的產品為了加速資料尋找的速度，便採用了許多 Tree 結構．我們這邊講的是一個較廣泛的 Tree 結構，在不同的應用情況下，會有特製的 Tree 做為在那些特定情況下的解決方案．以後的文章內容會再談到那些細節．

閱讀全文

#14 資料結構 Queue

在基礎的資料結構裡，Stack有一個好兄弟，長的跟它有一點像，但是提供的行為結果卻剛好相反，它的名字叫 Queue．在 Stack 中有一個可以把資料放入的行為叫 push，而把資料讀出來的行為叫 pop，並且最重要的重點是最先放進去的資料將會後最後被讀取的，所以這是一種先進後出或後進先出的情況．

類似於 Stack，Queue 也提供了方法可以將資料寫進去和讀出來，習慣稱為 Enqeueue 和 Dequeue．而跟 Stack 最大的不同就是 Queue 先寫進去的資料將會是先被讀出來，是一種先進先出或後進後出的情況．

你可以在資料結構的課本看到以上的內容，也可以找到 Queue 是如何被實做的，通常來說用 Array 來實做 Queue 會比較單純一點，只要一個 Array 加上兩個 index 用來記錄資料的起點和結束點．

我們在這邊不談論 Queue 實做的細節，我們來談談在什麼情況下它會派上用場．

在 Stack 的文章裡，你曾聽我講故事提到有關文字編輯程式中常用的 "上一步" 功能，透過 Stack 的實作讓我們可以清楚地製做 "上一步"． 所以，你可以感受到當你在用 Stack 的時候，資料的順序會被倒過來．例如，你放 A B C 三個資料到 Stack，而讀出來時的順序是 C B A．所以，當你遇到需要這種資料巔倒的特性時，別忘了使用 Stack．

那 Queue 的特性呢 ? 你會很直覺地發現它並沒有提供什麼特別的效果，因為 A B C 的資料寫進去之後，讀出來的順序也是 A B C，那它有什麼過人之處需要我用到它呢 ? 若你能這樣直覺地想，其實也沒錯，因為若沒有什麼特別考量的話，資料先進先出的行為是帶來不了太多的好處． 但我想到了一個情況，如果你今天撰寫一個 API ，而你回傳的資料有規定必須要從頭開始讀取，如果你只是回傳一個 List 或一個 Array，那麼拿到資料的人就很容易違反規則，可以從中間或是從最後面開始讀取資料， 如果你回傳的資料結構是一個 Queue，那麼就等於限制了使用資料的人必須要從第一個資料開始讀，而且讀過之後就不能再重覆讀取相同的內容．我想這才是 Queue 所要展現的特性．

所以，Queue 的特點之一就在於第一個資料要被讀取之後，第二個資料才能被讀取． 這樣的特性似乎可以帶來某種程度的資料準確性，因為中間不會有資料被忽略而未被讀取．所以某些作業系統裡面或是某些商業產品便會依據這種特點來做成一個功能或產品，稱為 Queue system，例如在 Windows 作業系統中有 MSMQ (Microsoft Message Queue)，而 IBM 也有 MQ 的產品．只不過這些產品的範圍更大，是用在多台電腦環境下的資料傳送，而傳送的特性就是跟 Queue 一樣，前面的資料要先讀取，後面的資料才能讀取．

在不同的需求情況下，我們可以依據資料結構的特性來找出適合應用的地方，到目前為止，我介紹了基本的資料結構有 Array, List, Stack, Queue 以及 Hash table. 這些基本的資料結構常常在日常的工作中被使用到，而且也幾乎滿足了大部份的工作需要．所以，好好了解這幾個資料結構，對一個不複雜的軟體開發工作來說就相當足夠了．

不過，因為我後面有許多內容會談到資料庫，所以還需要多介紹一個基本的資料結構叫 Tree，這是下一篇的內容.

閱讀全文

#13 利用 Hash Table 來增加你的資料處理速度

還記得十多年前參加一個專案時，自己做了一件不好的資料處理方式，當時的我還不知道什麼是 hash function．在那時候專案部份的工作需要快速地處理大量的資料，透過資料庫連線讀取資料，然後再讀取相關的參考資料，再經過運算，最後把結果再寫回資料庫，如果你的方法是讀一筆寫一筆的話，那肯定會造成大量的資料庫 I/O，所以比較適合的方法是做批次的處理，也就是一次讀取某個足夠數量的資料筆數，處理完成之後再一次寫回去，這樣可以減少資料庫的 I/O，也可以讓程式運行起來速度可以快些．

以上的想法是可行的，但當時有一個小小的挑戰是有關參考資料，因為資料在運算的過程中必需依靠其他的數據才能計算，而這些數據多達 8 萬多筆資料，簡單的說，它是三個欄位構成，第一個是分行 ID，第二個是一個會計科目 ID，第三個資料值．

分行 ID

會計科目 ID

資料值

第一個 ID 和第二個 ID 是有相關的，它們之間是一個 many to many 的關係，也就是說當我要尋找資料值時，我必須要知道這兩個 ID 才行．當時專案所運用的伺服器還有相當足夠的記憶體空間，算一算資料量後，我就決定把那 8 萬多筆資料全部載入到記憶體，心裡想若一開始就把這些資料載入到記憶體之後，這樣資料在批次運算的過程中就可以直接到記憶體取得相關資料，如果一來更大大地減少資料庫的 I/O．心裡打的如意算盤正是如此，但當時我卻笨笨地用 List 結構把載入這 8 萬多筆資料到記憶體中，所以每當我要找資料時，我就用一個 for loop 把這個 List 結構從頭找到尾，只要前面兩個 ID 是相等時，就抓出第三個資料值．當時心裡，資料都在記憶體裡了，就算跑一個 for loop，以 CPU 對記憶體的速度來說也算是很快了．事後跑起來，運算速度也還是改進蠻多的，所以當時不但沒對 List 結構做改善，還一直以為自己做了一件相當聰明的事情．

後來當自己念了資料結構之後才發現到當初用 List 結構是多麼笨的事情，用時間複雜度的角度來看，那是一個 O(n)，其實可以做到 O(1)的．那要怎麼做到 O(1)呢? 以這個例子來說的話，我們就要做一個 hash table 裡面包著一個 hash table.

以 Java 語法為例子的話，其資料結構定義就變成

HashMap< UUID, HashMap<UUID, Integer>>

所以在讀取的時候就變成 hashMap.get( 分行 ID ).get( 會計科目 ID ) ，如果這兩個 ID 都存在的話，則使用 O(1) 就可以得到資料值．雖然資料都載入到記憶體了，透過 Hash function 的運用，我們還是可以讓整個運算再快一點．

Hash 在一般的軟體專案中用途非常的廣泛，常常是我們利用空間來換取時間的最常見的手法，因此熟悉它並且善用它一定會對你的程式執行有極大的幫助．

閱讀全文