#72 一秒38萬個交易的故事 - 資料庫引擎篇

與資料庫有關的文章到目前為止已張貼了二十二篇文章，這些文章所談論的內容大部份都是描述資料庫引擎裡 Storage 和 Transaction 的內容．資料庫引擎裡的內容當然不只這些，還包括 SQL query parser, query optimizer, logging manager, 以及一些基本的功能如 security control 等等．光是有關 storage manager 的故事就能寫一本書了，除非你想做資料庫引擎的專家才需要知道所有的細節，不然的話，只要了解一些基本的設計便能幫助你在工作上做到更好的境界．在這些二十二篇與資料庫引擎有關的文章，我寫的那些內容其實簡化或跳過不少的細節，但那些細節並不會影響你對資料庫引擎設計的了解，只讓你可以用比較高層次的角度來檢視資料庫引擎會為你做的事情．畢竟這些內容主要的對象是給非電腦科系畢業的資訊人所參考用，因此忽略了許多數學上的推導與比較．若你是電腦科系的學生正在學習資料庫理論，請以課本內容為主，因為課本內容裡面會用一些數學來明確表達運作成本等事情．為什麼要說這些呢 ? 這當然是和本篇文章的主題有關，一個一秒38萬個交易的故事．

這句話是去年阿里巴巴在雙十一的購物節活動後，阿里巴巴的大老闆馬雲所講的．他用總交易數量除以總交易時間，得到一個值就是阿里巴巴的系統在購物節活動時能處理一秒三十八萬筆交易．這是一個相當驚人的數字，也證明了阿里巴巴的工程團隊能得到這樣的水準．其實這樣的水準，既便是連 Amazon 也不見得能有這機會達成，畢竟以美國的人口數和使用量，要一秒鐘達成三十八萬交易數量，似乎蠻難的．中國有更龐大的人口再加上雙十一購物節的熱潮，自然而然能在短時間內形成非常高的使用量．反觀台灣呢 ? 若我記憶正確的話，高鐵訂購系統曾因大家搶票而掛了，江蕙退隱歌壇演唱會的訂票系統也曾發生這樣的事．想想台灣人口才多少人，瞬間能產生的使用量一定遠遠不如阿里巴巴遇到的情況，但很可惜系統掛掉的事情仍是發生了．可能的原因大概有兩種，一種是工程人員無法勝任工作，另一種原因是電腦資源不足．不論是那一種原因所產生的結果都是會令人產生負面的印象．

一個能處理一秒三十八萬筆交易的系統是一個龐大的系統，每個部份都有許多故事可以講，接下來的內容只討論一些與資料庫引擎有關的內容．在網路上我曾看過一篇文章談到阿里巴巴的資料庫交易系統裡為效能改進所做的一些事情，其中最讓我印象深刻的事情是預先建立訂單資料．以資料庫引擎的角度來看，預先建立訂單資料等於把所需要的 page 先建立完成，因此在系統運行的過程中，不會有 page split 的事情產生．請參考之前的文章

• http://www.woolycsnote.tw/2015/07/19-page.html
  
• http://www.woolycsnote.tw/2015/08/21.html
  
• http://www.woolycsnote.tw/2015/08/22-page-3.html
  
• http://www.woolycsnote.tw/2016/04/45-page-fill-factor.html
  

以上這幾篇文章與 page 有關，看完後，你便能了解為何 page split 是件大事，並且也能了解預先建立訂單資料就相當預先把這些 page 都建立完成．等系統運行時，資料庫引擎便不需要在當下建立這些 page，而是直接使用這些 page．簡單的說就是不用做 insert table, 只要 update table 即可．

除此之外，把 foreign key 拿掉也是件對效能有幫助的事情．因為把 foreign key 拿掉就等於讓資料庫引擎不用去檢查 foreign key 對應 primary key 的正確性，也就是讓資料庫引擎少做事情．但這樣做有某種程度的風險，請記得要搭配一些必要的配套措施．這方面的內容請參考之前的文章 http://www.woolycsnote.tw/2015/04/7-foreign-key.html

另外還有一個比較常用的技巧是將 database schema 做 de-normalization 的處理．如果你的程式需要做很多的 table join 時，你得好好考慮 de-normalization 這件事．平常使用量不高時，table join 也許不會造成你太大的影響，一旦使用量一高時，table join 將是個高成本的動作．所以在特別的情況下，將資料做 de-normalization 減少 table join 這能讓資料庫引擎少做許多事情．這方面的內容請參考之前的文章

• http://www.woolycsnote.tw/2018/03/68-table-join.html
  
• http://www.woolycsnote.tw/2018/04/69-table-join.html
  

當整個系統過了尖峰時刻後，再將結果的資料回復到 normalization 的情況下即可．

如果為了特別的目的而需要讓資料庫引擎少做一些事情以讓它達到最大效能的運行情況，都需要進行一些特別處理，上面所講的都是不錯的特別處理，可以有效讓資料庫引擎少做一些事讓它達到盡可能好的運行效能．當然可行的方法不只是這些，還有許多其他從資料角度或硬體角度來思考的方法．這篇文章的主要目的就是幫助大家明白在做這些特別處理的事情時背後所用的原理 (原因) 是什麼，讓你有足夠強大的理由相信這樣做的確是有幫助的，這也是這個部落格的目的．

Hope it helps,

閱讀全文

#71 資料庫引擎 - Deadlock 偵測 (Wait-For graph)

前兩篇文章談完了 table join，接著這篇文章把主題拉回到資料庫的 Transaction．

之前文章曾提過 deadlock 的發生，這在關聯式資料庫裡算是件平常可見的事情．之前曾提過當 deadlock 發生時，資料庫引擎可利用 wait-for graph 來偵測 deadlock 的發生．這篇文章將說明什麼是 wait-for graph．

Wait-for graph 是一個簡單的圖形，是一個有方向的圖形 (directed graph)，也就是它圖形上的邊具有方向性，這裡的方向性用來代表是那一個交易等待那一個交易．如下圖:



上圖的 S(A) 代表某個交易要對 A 物件取得 shared lock，R(A) 代表某交易要對 A 物件進行 read 動作，X(B) 代表某交易要對 B 物件取得 exclusive lock，W(B) 代表某交易要對 B 物件進行 write 動作．在進行 read 動作之前必須取得 shared lock，在進行 write 動作之前必須取得 exclusive lock．

從上圖可得知，T1 等待 T2，因為 T2 正在寫入 B 物件．所以在 wait-for graph 上就會有一個邊從 T1 指向 T2，用來代表 T1 等待 T2．再來， T2 等待 T3 因為 T2 想要寫入 C 物件，但 T3 先對 C 物件進行 read 動作．T3 等待 T1，因為 T3 想對 A 物件進行寫入動作，但在這之前 T1 對 A 物件進行讀取動作．因此就變成了 T1 等待 T2, T2 等待 T3, T3 等待 T1 的情況．這個情況將使得 wait-for graph 會形成一個 cyclic graph ，意思就是圖形裡點的某個點走到其他點上後有可能再走回到原來出發的點，這便形成了一個 cycle．



資料庫引擎在這個 wait-for graph 上來辦別是否有 cycle．如果有，這表示 deadlock 發生了．此時資料庫引擎便得採用設計好的規則來決定該如何解決 deadlock．解決的方法就是讓 wait-for graph 不會有 cycle 的現象．理論上，只要在 cycle 的路徑上把某一個 transaction 刪除即可．通常來說，資料庫引擎會刪除 "年輕" 的 transaction，"年輕" 是用 transaction 啟動時間來決定，因為基本上來說年輕的 transaction 已做過的動作可能比較少，所以刪除他們再重新啟動後比較省點讀取和寫入資料成本．

Wait-for graph 的應用其實蠻廣泛，在資料庫系統或一般的作業系統都會用到它來描述物件之間的關係．甚至在程式開發工具裡，元件之間參考的關係也可以用 wait-for graph 來呈現．當 A 元件參考 B 元件，B 元件參考 C 元件，C 元件再參考 A 元件，這情況將不允許發生，因為在 wait-for graph 裡將會有一個 cycle．

Hope it helps,

閱讀全文

#69 資料庫引擎 Table Join 的運行方式 - 下集

在 table join 上集的文章裡談到了最基本的 table join 運作的方式，也讓你知道資料庫引擎是如何進行 table join．你可以發現到不論用什麼方式進行 table join，資料庫引擎所處理的資料必須位在記憶體中才能被處理，因此，將資料從硬碟讀到記憶體的次數和方式將是主宰了整個大部份的執行時間．因此，要讓 table join 的完成速度變快就得在資料從硬碟讀到記憶體的過程中去下點功夫．由於資料量有大有小，記憶體的量也有大有小，所以不同情況下可能要採用不同的方法才能達到最好的效果．接下來，這篇文章來談談另一種 table join 的處理方式，稱之為 hash join．

聽到 hash join 的名字就不難想像這是跟 hash function 有關的處理方式．假設有兩個表格 R 和 S ，其中 R 的資料量比較小，並且也假設電腦的記憶體足夠大能讀入它．此時，可以將 R 一次全部讀入記憶體中，然後對 R 裡面的每一筆資料進行 hash 運算，完成後會得到一個 hash table．另外，假設 S 表格的資料量過大而無法一次全部讀入到記憶體，因此必須分批來處理，所以就一批一批地讀入到記憶體，每一批被讀進來後，就將這一些的資料進行同樣的 hash 運算就能知道是否有符合條件的資料在 hash table 裡面．如果有符合，便將結果暫存到 output page 裡．S 表格資料分批完成之後，就將 output page 回傳給使用者．整個邏輯就像下列的 code



假設 R 表格有 m pages, S 表格有 n pages，上面的動作可以看到 R 和 S 的 page 讀入到記憶體的次數只有 m+n 次，並且迴圈裡的動作是 hash function 的計算和尋找，他們是 O(1)，因為跟 R, S 的資料量大小無關．因此整個運作的過程蠻快的．可惜世界不會如此美好，大部份的情況是 R 和 S 往往都遠大於記憶體大小，因此無法將較小的表格一次讀入到記憶體去，於是要再想出其他的方法．有一個不錯的方法叫 Grace Hash Join，它採取兩階段的方式，先對 R, S 的每一筆資料用一個 hash function 做分類，假設分類成 k buckets, 然後再到每個 bucket 裡面再用另一個 hash function 做分類以快速比對資料．整個邏輯如下:



前面用 hash function A 進行 partition 時，其結果是寫入在硬碟中，這稱之為 partition phase．如下圖:



接下來將每個 bucket 依序地讀入到記憶體中來尋找符合條件的資料，這稱之為 probe phase，如下圖:



假設 R , S 分別有 m, n pages，在 partition phase 中，R 所有的 pages 會讀入到記憶體，並且 partition 完成後也會寫入分類好的資料，也是有一樣的 page 數，所以資料庫引擎會有 m 次的讀和 m 次的寫．相同地，對 S 表格而言，也會有 n 次的讀和 n 次的寫，因此在 partition phase 中一共用 2m + 2n 的 page 讀寫．

在 probe phase 中，每個 bucket 都會被讀入到記憶體一次，所以對 R, S 表格來說，一共會有 m + n 次．如果我們不計算寫入 output data 的成本花費，則整個 Grace Hash Join 的動作將用了 3m + 3n 次的 page 讀寫．這個比起上一篇文章裡將的方法大約是 m * n 次要來的好，當 m 和 n 夠大時．

你可以看到依記憶體大小的不同以及資料量大小的不同，採用不同的 join 方式會得到不同的效果．一個好的資料庫引擎便會依照這些條件來決定用何種方式來進行 table join．但不論何種方式，table join 本身就是一個高成本的動作．依此對於超大資料量的表格，不需要 join 的情況是最好的，因此有時為了一些效能成本的考量，才會適當地做一點 de-normalization 的動作讓 table join 可以少見．但這樣做也會產生其他的問題，必須搭配其他的配套措施．

Hope it helps,

閱讀全文

#68 資料庫 Table Join 的運行方式 - 上集

在資料庫引擎中，table join 是一個很重要並且常見的動作．這一篇文章將討論以邏輯上來看資料庫引擎是如何進行 table join 的動作．

假設資料庫中有兩個表格，一個是學生表格，一個老師表格，這兩個表格裡都各自有一個 id 欄位用來代表學生編號與老師編號．對這兩個表格來說，這個 id 非常適合做為 primary key．學生表格裡有一個欄位是老師 id，這用來代表某學生的班導師是某位老師．這是一個一對多的關係，所以只要在學生表格上有一個老師 id 的欄位便能說明這個關係．用一個簡單的 SQL 語法可以用來表示這樣的關係

Select S.Name, R.Name
From S join R
On S.TeacherId = R.TeacherId    ( S = Student, R = Teacher)

假設你是資料庫引擎的程式設計師，需要處理以上的語法並回傳結果，你會怎麼處理呢? 所有的資料都儲存在磁碟中，但運算時你得把資料搬到記憶中才能計算，於是你可能會想到最直覺的方法就是把所有老師和學生的資料放到記憶體中，然後用兩個 for loop 將學生與老師的資料一筆一筆的比對，把比對成功的結果暫存起來，執行完畢之後就把結果回傳給使用者．這方法是假設所有的資料並沒有任何 index 建立的情況下．

以上的想法很直覺，但會面臨到幾個問題．第一個問題是有可能把學生和老師的資料全部載入到記憶體中嗎 ? 如果學生老師人數不多，這是可能的．但如果是一家龐大電子商務公司的訂單與客戶資料呢 ? 資料量一定大於記體量容量，所以把兩個表格的全部資料載入到記憶體是不可行的．因此，當你寫兩個 for loop 做資料比對時，資料必須一批一批地從硬碟載入到記憶體．如同以前的文章提過，所有資料的儲存單位是以 page 為主，所以可以一個一個 page 依序地載入到記憶體，然後對該 page 裡的資料進行比對的動作．如下圖所示:

比如老師表格 (R)  有二個 page，學生表格 (S) 有五個 page．當第一個老師 page 被載入到記憶體，接著第一個學生 page 被載入記憶體進行資料比對，然後再換第二個學生 page 被載入，一直到第五個學生 page，然後再換成第二個老師 page 被載入到記憶體，接著再依序 (反向) 將學生 page 一一載入比對資料．符合條件的資料將被放在記憶體另一個區域，如上圖的粉紅區域．整個比對完成之後，就將粉紅區域的資料回傳給使用者．如果採用這個方法，老師和學生的 page 將被載入 2+5+4 = 11 次．以速度來看，這 11 次從硬碟載入到記憶體的 page 讀取時間應該主宰了這個動作大部份的時間．

如果將以上的點子做一個小改進，也就是將其中一個表格絕大部份的內容載入到記憶體，而另一個表格一次只載入一個 page 到記憶體，如下圖所示 :

假設，老師的兩個 page 一次全被載入到記憶體，而學生表格的五個 page 將依序載入到記憶體，然後進行資料比對．這樣的 page 載入將發生 2 + 5 = 7 次．理論上應該比前一個方式來的好．這也是典型的用空間換時間的方法．

Select S.Name, R.Name
From S join R
On S.TeacherId = R.TeacherId    ( S = Student, R = Teacher)
Where S.Age = 20

上述語法是另外一種情況．如果表格資料的數量很大並且在適當的欄位上 (S.Age) 皆建立 index 的話，那麼就不用將所有的 page 都載入到記憶體中來進行資料比對．只要透過 Index tree 的尋找機制，將符合條件的資料所在的 page 載入到記憶體進行比對．所以，在 table join 時，若能適當地加上條件 (where)  並且該條件有 index，這將對 table join 的處理速度有莫大的幫助．

其實，以上所說的方法用在表格資料不大的情況下都算能應付的過去，但如果表格資料太大時，以上的方法並不具有效率，為什麼呢 ? 顯而易見，你看到了兩個 for loop 的想法是整個運算方式的主體．有這兩個  for loop 在，速度當然是快不起來．因此，下一篇資料庫的文章將介紹更快的方式．

閱讀全文

#65 資料庫引擎的交易資料鎖定 (Lock) 策略

延續上一次資料庫的交易文章內容，在一個資料庫系統中同一時間可以執行多個交易 (Transaction)．在這同時執行的交易內容中，當遇到共同讀取和寫入同一個物件時，此時便有很大的機會將發生如上一篇文章中提到的資料衝突現象．為了要解決這個現象，資料庫引擎得採取一種策略．以學術的角度而言，策略有好幾種，但比較常見和合理的策略將是本篇文章中將討論的資料鎖定 (Lock)．

Lock

首先定義上一段文字中所說的 "共同讀取和寫入同一個物件"，物件是指交易內容中所感興趣的資料．可能是一筆資料，例如某一個學生的基本資料，可能是符合某條件的資料，例如去年十月份的所有訂單．以邏輯處理而言，通常來說這資料可能只存在於同一個表格，但也有可能存在於多個表格．以實體上而言，資料有可能在同一個 page，但更有可能分散在不同的 page．以邏輯上而言，資料庫引擎可以對一筆資料進行鎖定，也可以對一整個資料表格進行鎖定，或是鎖定某些特定條件的資料．以實體上而言，通常是以鎖定 page 為單位，資料庫引擎比較方便進行鎖定．

資料鎖定策略定義兩種鎖，第一種鎖是共享鎖 (Shared lock)，也就是當交易對某資料進行讀取動作時，則必需先取得共享鎖，共享的意思也就是其他的交易對同樣資料進行讀取時，也會取得共享鎖，代表這資料只供讀取．所以取得共享鎖的交易可以馬上對資料進行讀取．第二種鎖是互斥鎖 (Exclusive lock)，這是當交易對某資料進行寫入動作所需要取得的鎖，其顧名思義，互斥鎖在同一時間只能被一個交易取得使用，如果其他交易也要取得同份資料的互斥鎖，則必須等待．一般而言，我們將共享鎖簡稱為 S lock，互斥鎖稱為 X lock．透過這兩種 lock 便能解決上一篇文章裡所提出的問題．接下來，舉些例子來說明這兩種 lock 如何確保資料鎖定策略能成功．

首先來看下圖的範例，有兩個交易，他們對同一個資料 (A) 先進行讀取動作 (R) 再進行寫入動作 (W)

由於他們將對資料 A 進行寫入，因此他們都需要取得 X lock．假設是 T1 交易先啟動，因此當 T1 啟得 X lock 之後，T2 就得等待．當 T1 完成後 (Commit完成後)，對資料 A 的 X lock 就會被釋出，因此 T2 才能得取資料 A 的 X lock，接著 T2 才能執行．因此，真正的執行情況將變成下圖．

如果執行的情況變成 T2 先啟動，則 T1 就必須等到 T2 執行完成後才能取得 X lock 接著執行．因此，不論是那一個交易先執行，另一個交易都必須等待．這是一個很單純的例子．接下來來看一個對多個資料進行讀和寫的例子．

以上是兩個交易 (T3,T4) 對資料 A,B,C 進行動作, 其中 T3 讀取資料 A，讀取和寫入資料 C，而 T4 讀取資料 A，讀取和寫入資料 B．由於 T3, T4都對資料 A進行讀取，所以他們都會取得 S lock，因此可以同時讀取資料A．之後他們分別對不同的資料 (B ,C) 進行寫入動作，因此取得 X lock時是針對不同的資料，所以不用等待對方就能馬上進行寫入動作．

以上所說的方法是採用漸進式的方式來進行資料鎖定，也就是當交易讀取或寫入某資料時，才需要對該資料取得 S lock 或 X lock，而且 S lock 和 X lock 將決定交易是否馬上繼續執行或是需要等待．因此，這樣的方式對資料庫引擎來說是漸漸增加 lock 的數量，然後在交易 commit 或 abort 時，一次釋放該交易所擁有的 lock，就有如下圖一樣：

DeadLock

以上的策略會讓死結 (deadlock) 有機會產生，主要的原因在於 X lock，舉例如下圖:

當 T1 嘗試著取得資料B 的 X lock，結果資料 B 的 X lock 在被 T2 使用中，因此得等到 T2 完成才行，結果 T2 後面有個動作要對資料A 進行寫入，欲取得資料A 的 X lock 時，此時它正被 T1 所使用，需得到 T1 完成才行．因此就進入了一個你等我，我等你的狀態，也是電腦科學領域中常見的 deadlock 問題．資料庫引擎需要有能力來偵測死結的情況，並且要有能力處理死結．以理論上來說，偵測不是難事，資料庫引擎得維護一個 waits-for graph 來對整體系統裡那些交易在等待那些交易完成，透過 waits-for graph 可讓資料庫引擎偵測死結．這對資料庫引擎來說是一項不得不花費的成本，因為要偵測死結的存在，才能對死結的現象進行解決．解決死結最簡單的方法就是將造成死結的交易終止，好讓其他交易可以順利取得 lock，然後再將被終止的交易重新啟動．無論如何，資料庫引擎在這能做的只是事後的預防與問題的排除，若想要盡量避免死結，還需要程式開發人員的配合．交易是程式開發人員所撰寫，因此在寫交易時要儘量避免死結的發生便很重要．有幾個簡單的準則可供參考:

• 若非必要，不要為你的 stored procedure 設定成以交易的方式進行．
  
• 交易應盡量短．如果交易過長，這表示交易將進行更多的讀取或寫入的動作，無形中也增加了死結的機會．因此，最好把交易分割到最小不可分割的單位．過於複雜的商業邏輯由外面的程式邏輯層執行，資料庫只要做基本的資料操作動作．
• 盡量讓交易對資料有相同順序的讀取或寫入．如前面的例子，死結的發生往往在於你等我，我等你的情況．因此，若把資料讀寫的順序盡可能排成一樣，這樣就能大大減少你等我我等你的機會．

以理論上來說，資料鎖定的策略不只以上介紹的方法，還有其他不同的鎖定策略以及死結預防和處理的方式．不論是用那一種，對資料庫來說都是相對應要付出成本．若能將這方面的成本降低，這將有助於資料庫引擎效能．

閱讀全文

#64 資料庫引擎交易 (Transaction) 進行中的讀寫異常

前面的文章曾談到交易 (Transaction) 需要具有 ACID 的特性．在一個繁忙的資料庫系統中一定會有許多的交易同時執行，這篇文章便來談論許多交易同時執行時會遇到那些挑戰．

許多交易在進行時，非常有可能會遇到對相同的資料進行讀或寫的動作．如果所有的交易對相同的資料進行讀的動作，則這情況並沒有什麼好擔心的，因為所有的交易對這份資料都是讀的動作，早讀和晚讀都是同一個答案，所以不會造成任何的資料異常現象．但如果情況變成其中有一個交易或多個交易對同一份資料進行寫的動作時，那麼早寫和晚寫就會有很大的影響了．因此，我們在乎的情況便是當有交易在進行寫的動作．以下假設某個資料庫系統中有兩個交易，這兩個交易會對同一份資料進行讀和寫的動作:



如上圖所示，T1 做的動作是 A=A-100 和 B=B+100，T2 做的動作是 A=A*1.5 和 B=B*1.5．如果交易執行的情況如上圖的話，假設 A 和 B 的初始值都是 300，你認為當這兩個交易完成後，A 和 B 的值會多少呢 ? 沒算錯的話，A 應是 300，B 應是 550．如果 T1 和 T2 執行的情況不是像上圖一樣，而是 T1 先執行，完成後再執行 T2，此時答案是多少呢? 沒算錯的話，A 還是 300，但 B 是 600．這時你就會發現怪怪的，執行的順序果然會影響答案，這可是不得了的大事呀．如果你把 A 和 B 想像成是銀行中的戶頭，而 T1 就像在執行匯款的動作，T2 就像是在執行加值的動作．這兩組不同目的動作是可以同時被觸發的，但很顯然地你一定發現 T1 在執行動作時，T2 不應該執行，因為他們會對相同的資料進行寫的動作．如果你允許他們可以同時對相同資料進行寫的動作，則就會發生資料異常的現象．所謂資料異常就是指不應該發生的情況．正常的情況是 T1 先執行再執行 T2，或是 T2 先執行再執行 T1．我們再來看另一種例子:



這一個例子是 T1 的讀寫動作完成後 T2 才開始進行讀寫，但最大的差別是 T2 在進行讀寫時，T1 還沒有 commit．等到 T2 commit 完成之後，最後 T1 才決定 abort．這種情況也是我們不希望看到的，因為這也是一種資料異常的現象，因為 T2 在對 A資料進行讀寫時，它的基礎是建立在 T1 對 A 完成的結果上，結果 T1 對其結果是否定的 (abort)，所以 T2 的結果就便成是一個大笑話了．

看到這裡時，你就可以知道當某一個交易對某一個資料進行 "寫" 的動作時，在這交易尚未完成前 (Commit or Abort)，我們不希望其他交易能對相同資料進行 "讀" 和 "寫" 的動作．相同地，當某一個交易對某一個資料進行 "讀" 的動作時，在這交易尚未完成前 (Commit or Abort)，我們也不希望其他交易能對相同資料進行 "寫" 的動作．如下圖所示:



為了防止以上資料異常的現象發生，資料庫引擎裡需要某些特別的設計來防止這類的事情發生，這個特別的設計稱為 Locking．也就是當某交易在對某份資料進行動作時，便把該份資料鎖住讓其他交易無法使用該資料．下一篇文章將會來談談這個鎖資料的內容．

閱讀全文

#58 資料庫引擎對交易 (Transaction) 的執行情況

在上一次文章裡介紹了基礎的交易 (Transaction) 性質與特點，讓你可以了解為何關聯式資料庫引擎需要它．在一般的情況下，一個資料庫引擎在同一個時間內服務的應用程式非常可能不只一個，而且同一個應用程式也可能在同一個時間發出兩個不同的交易來要求資料庫引擎執行．因此，我們都知道一個資料庫引擎在同一時間執行多個來自用戶端的交易是相當平常的事情．同時可以服務多個用戶端等於是增加了整個系統的處理效能，也因為要同時服務多個用戶端，資料庫引擎的效能對於磁碟存取就會變得相當敏感．因為磁碟存取速度快，整體效能才夠快．但只有磁碟效率快就夠了嗎? 在上一次文章裡介紹了交易的特點之後，你就能明白光是快還不夠，還需要在多個交易執行讀取之間不造成衝突才行．因此，資料庫引擎的設計就會面臨兩個挑戰:

1. 如何執行多個交易時還能保持資料的正確性?
2. 如果硬體出錯或是用戶端取消交易執行時，資料庫引擎該如何處理以保持資料的正確性．

為了面對這兩個挑戰，資料庫引擎得引進一個排程 (Schedule) 的想法．所謂 Schedule 是指一連串的動作 (讀或寫)，而這一連串的動作可以是由不同的交易而來的，更重要的是不論這份 Schedule 裡那一個交易先執行，其結果都該和 Schedule 的結果一致．這樣講可能有點抽象，直接看下圖:

資料來源: 我以前在學校的筆記

上圖是一個 Schedule，裡面有兩個交易，分別是 T1 和 T2，其中 T1 有 4 個動作，而 T2 有兩個．時間軸是由上而下，所以 R(A) 是整個 Schedule 裡第一個動作，它代表到 A 做讀取動作，而 W(C) 是最後一個，它代表到 C 做寫入動作．這份 Schedule 安排的很好，因為 T1 讀寫的對象和 T2 完全不同，所以這兩個交易之間不會產生衝突的情況．而每一個交易最後都會有一個 commit 的動作，用來告訴資料庫引擎可以把放在暫存區的結果寫回到磁碟上．如果資料庫引擎可以安排出好的 Schedule，似乎就能克服先前說的兩個挑戰．接下來看一個簡單的例子．

假設銀行要執行兩個交易，一個交易是做轉帳，從 A 帳戶轉 100 元到 B 帳戶，另一個交易是做分派利息，兩個帳戶同時增加 50% 的利息．以動作來看，第一個交易有兩個動作，A=A-100 以及 B=B+100，第二個交易也有兩個動作，A=A*1.5 和 B=B*1.5．假設，不同的用戶端分別同時發出這兩個交易，那麼資料庫引擎該怎麼設計 Schedule? (無法保證 T1 , T2 那一個會開始執行)

如果 Schedule 被安排的如下:

資料來源: 我以前在學校的筆記

這份 Schedule 是可行的，因為它的結果跟單獨先執行 T1 再執行 T2 是一樣的．如果 A , B 都有 100，先執行 T1 再執行 T2，這樣 A=0, B=300 符合這份 Schedule 的預期，所以它是可行的．

如果 Schedule 被安排成另一種:

資料來源: 我以前在學校的筆記

這份 Schedule 似乎就不行了，因為順序影響結果．假設 A, B 一開始有 100，先執行 T1 再執行 T2，變成 A=0, B=300，但是這份 Schedule 完成之後是 A=0, B=250，顯然這份 Schedule 裡動作的順序安排的不適合了．

設計出適合的 Schedule 讓資料庫引擎可以一起執行多個交易也算是增加效能的方法之一．下一篇文章會再繼續談到為何需要好的 Schedule 以及動作衝突時如何解決．

閱讀全文

#54 資料庫的 Transaction (交易) - ACID 基本介紹

在關聯式資料庫 (Relational Database) 裡，Transaction 是一個極為重要的特性，或許也可以稱為功能．若我印象沒記錯，Transaction 在台灣的書藉裡普遍翻譯成 "交易"．雖然覺得用 "交易" 來表示蠻奇怪的，但也只能將就這情況，畢竟這翻譯詞已存在很久了．基本上而言，一個 Transaction 是指用戶端傳送給資料庫引擎所要執行的動作．這些動作通常是以 SQL 語法組成，然後再由資料庫引擎來解析語法，轉成各式各樣的動作來執行．比如，用戶端傳來了一個 Update Table1 set Column1='some word'，這個語法是告訴資料庫引擎去尋找 Table1 的表格，然後將這個表格裡 Column1 欄位的內容改成 'some word'．這個語法本身就是一個 Transaction，其本身的特性需要有足夠的單獨性，一致性，持續性以及不被干擾的特質，也就是市面上書藉裡常提到的 ACID．這些特性是在 1980 年代一位著名的學者 Jim Gray 所提出，後來再經由其他學者加以擴展而成現在所看到的 ACID．

• Atomicity: 這指的是單獨性．比如，一個 Transaction 裡有一個 Update command，一個 Delete command．如果 Update command 成功了而 Delete command 失敗了，則這個 Transaction 便是失敗的，所以 Update command 必須回復修改過的資料．
• Consistency: 一致性代表的是在 Transaction 執行前後，資料皆處於合乎所有規則的狀態．例如，某個欄位具有 foreign key 的關係，其資料的內容不是能隨意產生的，必乎符合 foreign key 的關係，所以 transaction 在執行後，這樣的關係必需持續下去．
• Isolation: 這指的是不同的 Transaction 之間執行時不能被彼此干擾．假設有兩個 Transaction 在同一時間對相同的一百筆資料進行更新動作，而其中一個 Transaction 在更新到一半時產生錯誤，於是進行資料回復．然而，另一個 Transaction 是完成的．可想而知最後的資料狀態一定是無法預測，因為不清楚那些資料是失敗的 Transaction 做資料回復的，還是成功的 Transaction 所更新完成的．
• Durability: 我將它稱之為資料的耐力．資料庫引擎必須要保證一旦 Transaction 完成後，不論發生任何事情，如系統當機或電力中斷等，運作後的資料都必須存在於儲存媒介中，也就是在硬碟裡．

一個商業化的關聯式資料庫都必須提供這些特性，因為一個強大的資料庫引擎需要服務很多的用戶端，因此這些特性不只要提供，而且得做的夠好才能夠在市面上生存．未來的文章裡將會介紹更多的主題來說明資料庫引擎是如何達成這些功能．

接下來，讓我們用一些符號來說明 Transaction.

一般來說，使用 T 來表示 Transaction，而R_T(O) 代表 T 要對 O 進行讀取的動作，W_T(O) 就是代表 T 要對 O 進行寫入的動作，其中 O 代表的是資料庫裡某個儲存單元，例如表格．

Transaction 的完成的結果只有兩種，一個是成功 (Commit)，另一個是放棄 (Abort)．Commit 代表的就是 Transaction 裡的每一個資料的讀取和寫入都是成功的，而 Abort 代表的是 Transaction 裡並不是有所有的資料讀取或寫入都是成功的．在符號上則使用 Commit_T 來代表 T 是 Commit 結果，用 Abort_T 來表示 T 是 Abort 結果．也許你查不同的書藉會有不同的表示方法，但這不會造成影響．介紹這些符號的目的是為了未來說明 Transaction 的動作時，可以用簡單的符號來代表一些事情．例如，

這代表了系統裡有兩個 Transaction, T1 和 T2，其中 T1 進行的動作是讀取A，寫入A，讀取B，寫入B，最後的結果是 Commit．表格裡的每一行代表同一時間上所做的動作．因此，這一個例子是不合法的，因為不能有兩個 Transaction 在同一時間對同一個物件做寫入的動作，這違反了 Isolation 的特性．

一個資料庫引擎的效能往往也由它對 ACID 特性的執行速度來決定．你可以發生問題都是發生在寫入的動作上．因為寫入代表刪除或更新，這將改變了資料庫內的資料狀態．如果你有一個資料庫只需要提供讀取而沒有寫入，那麼 ACID 特性對資料庫引擎而言就沒什麼意義了．

閱讀全文

#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 的方式，不同的方式有好有壞，有長處也有短處．

閱讀全文

#45 資料庫基礎 - Page 的 Fill Factor

前面的文章介紹了許多資料庫引擎中有關 Storage management 的部份，讓你能了解資料庫引擎在處理儲存與讀取資料時所使用的原理基礎．但這些也都只是基礎的運作原理，真正實作的方式也會因為產品的不同也有些差異，但至少你知道了原理，這就能幫助你了解資料庫引擎的工作，也希望對你的學習與工作能有所幫助．

這篇文章將說明的是一個 Storage management 中管理資料的選項，對我而言，這是一個設計技巧．還記得前面的文章中曾提過 Page - 這是資料庫引擎用來儲存資料時所用的一個管理單位．一個 page 可能會有 4K 或 8K 或其他大小的容量設計，所以每個 page 的容量幾乎都是固定的．對一般正常運作的資料庫系統來說，對資料一定會進行新增刪除與修改的功能，所以這樣子的工作就常常會導致 page split 的現象，這個現象在前面的文章曾提過．page split 就相當於是在一個 list 中插入一個新的元素一樣，其運作成本比較高，如果再加上硬碟資料散亂度過大的話．所以，為了減少 page split 的現象，因此存在了 fill factor 的設計．

Fill factor 的意思就是當一個新的 page 產生要寫入資料時，資料庫引擎不會將所有資料空間都拿來寫入資料，而是會留下某一個百分比的空閒空間．這個百分比的大小基本上是可人為控制的．比如，當我們告訴資料庫引擎 fill factor 為 80% 時，則資料庫引擎在 page split 發生或是需要建立新的 page 時，當它寫入資料時只會佔用掉  80% 的可用空間．而剩下的 20% 就留做未來在做資料新增修改時可以利用的空閒空間．舉個例子說明，你有一份學生資料放在資料庫中，而學生資料假設定依照學生姓名排序 (primary key)．假設一開始並沒有設定 fill factor，而它的預設值是 100%，所以這表示所有的學生資料都依序寫入到 page 之中．資料越多，所需要的 page 也會越多．而在這些 page 之間都沒有留下任何的空閒空間．而今天來了一個新學生，他的名字剛好是排在所有學生的中間，當它的資料寫入到資料庫時，資料庫引擎發現它需要在這些 page 中間做一個 page split．Page split 做完後，一個 page 變成 2 個 page，所以這兩個 page 都多有了 50% 的空閒空間，因此新學生的資料就可以寫進去這中間的 page 了．所以，如果一開始設定了 fill factor = 50%，那表示在一開始學生資料寫入到 page 時只會佔用一半的空間，因此每個 page 都有一半的空閒空間．當新的學生資料需要新增時，資料庫引擎找到目的 page  後發現還有一半空閒空間並且足夠用來寫入新資料，則就直接將新資料寫入而不需要做 page split 的動作，因此也讓資料新增的動作可以更快地完成．所以，你可以把 fill factor 想成是一種利用空間來換取時間的方法．這對於經常需要做新增動作的資料庫來說相當有幫助．對於資料變動很小的資料庫來說並沒有什麼太大的好處．

因此，如果你採用的資料庫引擎有提供 page split 的觀察指標，你可以查看你有那些 table 經常發生 page split 的現象，如果有的話，你可以將 table 的 fill factor 改小一點來降低 page split 的發生．

其實 fill factor 也只是一個應用，像這樣預先預留空間做為未來使用的情況，在很多產品的設計都會用到這樣子的 idea，基本上都是用空間來換點時間的做法．希望這樣的 idea 有一天也能幫助你的設計．

閱讀全文

#42 資料庫基礎 - Index 所用的資料結構 B tree

在前面的文裡談了有關資料庫 Index，說明了為什麼 index 能加速尋找資料，也說明了 index 有那些種類．在這篇文中，將來簡單談一下 index 所使用的資料結構．

看了前面的文章後，想必你也可以很容易猜出 index 所使用的是像 tree 那樣的資料結構．在前面的文章中也談到了最基本的 tree 資料結構概念．tree 其實在電腦科學的領域裡應用的相當廣泛，不論是學術上或工業界裡，因為 tree 帶來的好處實在很多，但要把 tree 寫出來其實也不是一件很容易的事．不同的應用會衍生出不同的 tree，而在資料庫的 index 所採用的 tree 叫做  B-tree．所謂的 B 就是平衡 balance 這英文字，所以中文你可以用平衡樹來叫它．

B-tree 所指的平衡是指樹的每一個 leaf 到 root 都是一樣的高度，所以整顆樹看起來站的很穩，不會有缺一角的感覺．

source: http://cis.stvincent.edu/html/tutorials/swd/btree

為什麼 index 要選擇這樣的 tree 來做為資料結構呢 ? 原因就在於這個 tree 是平衡的，所有 data pointer 都是在 leaf 的地方，也就是說當資料庫引擎在 B-tree 上找資料時，不論它要去那一個 leaf，它所花的成本都是一樣的，也就是樹的高度．所以，以使用者的角度來看，你今天打 select * from student where studentID ='1' 或 select * from student where stuentID='100' ，在 index 上所花的成本都是一樣的．簡單的說就是把所有的資料一視同仁，讓大家都有一樣的存取時間成本．我想這對資料庫使用者來說是件重要的事情，因為你應該不會想讓某些資料有特權來得到較低的存取成本．

接下來的問題就是，我們怎麼會知道這顆樹會一直平衡呢 ? 這並不是資料庫引擎所要擔心的事情，因為保持平衡是 B-tree 本身就要具有的能力，也就是說當一個新的節點新增到這顆樹來後，樹的平衡機制就要啟動來調整樹本身的結構以保持平衡，同樣地刪除節點也是．所以，要實做 B-tree 的重點就是要看保持 "平衡" 的程式碼是不是寫的夠好．在這裡，我就不談論太多保持平衡的細節，若你有興趣知道 B-tree 是如何保持平衡的，可以參考 http://cis.stvincent.edu/html/tutorials/swd/btree/btree.html ，這個學校用圖案來表示當 B-tree 新增和刪除節點後是如何保持平衡的．

以外，B-tree 還有一些小變形，如 B+ tree，它是在 leaf 之間再加上一個 pointer 可以從一個 leaf 到下一個 leaf，這樣做的好處是我們可以在找到資料後，很快地再移到下一個資料而不需要每次都從 root 出發．我想這應該是大部份資料庫產品會採用的資料結構．

希望透過這篇文章的說明能讓你對資料庫 index 為什麼能為你快速找到資料有幫助．在了解了基本的原理之後，相信以後你在操作資料庫設定 index 時，心裡會有一種踏實的感覺，因為你知道資料庫引擎對這項工作運行時的基本原理了．

閱讀全文

#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)．

閱讀全文

#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 的低成本給騙了．

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

閱讀全文

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

閱讀全文

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

閱讀全文

#25 資料庫基礎 - 存取 Page (Heap File)

        在前面的幾篇文章中提到了資料庫引擎讀取與寫入資料時在面對固定長度與非固定長度時所可以採用的儲存方式，其中提供了 Page 為一個儲存空間的管理單位，透過 Page 的機制，讓資料庫引擎能以 Page 為單位做資料讀取與寫入的動作．搭配上 Page 裡的 manifest 資料，資料庫引擎就可以很清楚地知道這個 Page 裡面有多少筆資料以及有多少剩餘空間可用．這時候我們把層次往上拉高一點來看，那 Page 跟 Page 之間的關係是如何定義呢 ? 舉例來說，當某一個表格裡的資料繼續變多時，這些資料很可能會需要很多的 Page 來能承載，那資料庫引擎又怎麼知道是那幾個 Page 是用來承載這表格的資料呢 ? 因此，我們也必須定義 Page 和 Page 之間的關係．

        要定義 Page 之間的關係最簡單的方法就是採用 Linked List 的概念，也就是說每一個 Page 都會記錄著上下一個 Page 的位置，這就像是 Double Linked List 一樣，所以資料庫引擎便很容易地在 Page 之間游走來尋找資料．參考下圖來看一個很簡單的例子:

上圖一共有七個 Page，其中 page 1, 3, 4, 6 前後之間有 pointer 指著上下一個 Page 的位置，這也代表這四個 Page 儲存著高度相關的資料，比如說是同一個表格的資料，或是同一份 index 的資料等．但什麼樣的資料會讓 Page 用這種方式儲存呢 ? 看來是隨意安排的資料，不需要排序，也不需要特殊的安排，資料先進來就先寫入．因此，當資料庫引擎在存取這類型的資料時所花費的成本就會很高，因為都必須從頭開始往後找．不論是找什麼樣的資料，尋找一律都是從最前面的 Page 開始找到最後的 Page．其實這也就是 Linked List 的特性之一．也就是說你要找的資料剛好落在最後一個 Page 的時候，資料庫引擎就必須要從最前面的 Page 一直找到最後一個 Page．因此，這樣所花費的成本是相當高的．

所以，這也告訴了你一件事情，如果你的資料用上述的方式來儲存，這將造成資料庫引擎花費許多時間成本來尋找與寫入資料，而這種像 Double Linked List 的 Page 關係方式，一般的課本稱它為 heap file. 後面的文章會再繼續介紹其他方法．

閱讀全文

#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 也就是這樣的感覺．

閱讀全文

#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，這也就是代表了資料庫引擎的效能．由此可見，對資料庫引擎而言，這是多麼重要的基礎考量．

閱讀全文