B-Tree（Balanced Tree 的縮寫）是計算機科學中最具影響力的資料結構之一，特別是在資料庫系統中。其設計確保了高效的資料儲存、檢索和修改，使資料庫引擎能夠更快速地執行查詢操作。本文將探討 B-Tree 的歷史、構建方法、操作原理及其變體，提供對其在資料庫優化中作用的全面...
#72 一秒38萬個交易的故事 - 資料庫引擎篇
與資料庫有關的文章到目前為止已張貼了二十二篇文章，這些文章所談論的內容大部份都是描述資料庫引擎裡 Storage 和 Transaction 的內容．資料庫引擎裡的內容當然不只這些，還包括 SQL query parser, query optimizer, logging manager, 以及一些基本的功能如 security control 等等．光是有關 storage manager 的故事就能寫一本書了，除非你想做資料庫引擎的專家才需要知道所有的細節，不然的話，只要了解一些基本的設計便能幫助你在工作上做到更好的境界．在這些二十二篇與資料庫引擎有關的文章，我寫的那些內容其實簡化或跳過不少的細節，但那些細節並不會影響你對資料庫引擎設計的了解，只讓你可以用比較高層次的角度來檢視資料庫引擎會為你做的事情．畢竟這些內容主要的對象是給非電腦科系畢業的資訊人所參考用，因此忽略了許多數學上的推導與比較．若你是電腦科系的學生正在學習資料庫理論，請以課本內容為主，因為課本內容裡面會用一些數學來明確表達運作成本等事情．為什麼要說這些呢...
#71 資料庫引擎 - Deadlock 偵測 (Wait-For graph)
前兩篇文章談完了 table join，接著這篇文章把主題拉回到資料庫的 Transaction．
之前文章曾提過 deadlock 的發生，這在關聯式資料庫裡算是件平常可見的事情．之前曾提過當 deadlock 發生時，資料庫引擎可利用 wait-for graph 來偵測 deadlock 的發生．這篇文章將說明什麼是 wait-for graph．
Wait-for graph 是一個簡單的圖形，是一個有方向的圖形 (directed graph)，也就是它圖形上的邊具有方向性，這裡的方向性用來代表是那一個交易等待那一個交易．如下圖:
上圖的...
#69 資料庫引擎 Table Join 的運行方式 - 下集
在 table join 上集的文章裡談到了最基本的 table join 運作的方式，也讓你知道資料庫引擎是如何進行 table join．你可以發現到不論用什麼方式進行 table join，資料庫引擎所處理的資料必須位在記憶體中才能被處理，因此，將資料從硬碟讀到記憶體的次數和方式將是主宰了整個大部份的執行時間．因此，要讓 table join 的完成速度變快就得在資料從硬碟讀到記憶體的過程中去下點功夫．由於資料量有大有小，記憶體的量也有大有小，所以不同情況下可能要採用不同的方法才能達到最好的效果．接下來，這篇文章來談談另一種 table...
#68 資料庫 Table Join 的運行方式 - 上集
在資料庫引擎中，table join 是一個很重要並且常見的動作．這一篇文章將討論以邏輯上來看資料庫引擎是如何進行 table join 的動作．
假設資料庫中有兩個表格，一個是學生表格，一個老師表格，這兩個表格裡都各自有一個 id 欄位用來代表學生編號與老師編號．對這兩個表格來說，這個 id 非常適合做為 primary key．學生表格裡有一個欄位是老師 id，這用來代表某學生的班導師是某位老師．這是一個一對多的關係，所以只要在學生表格上有一個老師 id 的欄位便能說明這個關係．用一個簡單的 SQL 語法可以用來表示這樣的關係
Select...
#65 資料庫引擎的交易資料鎖定 (Lock) 策略
延續上一次資料庫的交易文章內容，在一個資料庫系統中同一時間可以執行多個交易 (Transaction)．在這同時執行的交易內容中，當遇到共同讀取和寫入同一個物件時，此時便有很大的機會將發生如上一篇文章中提到的資料衝突現象．為了要解決這個現象，資料庫引擎得採取一種策略．以學術的角度而言，策略有好幾種，但比較常見和合理的策略將是本篇文章中將討論的資料鎖定 (Lock)．
Lock首先定義上一段文字中所說的 "共同讀取和寫入同一個物件"，物件是指交易內容中所感興趣的資料．可能是一筆資料，例如某一個學生的基本資料，可能是符合某條件的資料，例如去年十月份的所有訂單．以邏輯處理而言，通常來說這資料可能只存在於同一個表格，但也有可能存在於多個表格．以實體上而言，資料有可能在同一個...
#64 資料庫引擎交易 (Transaction) 進行中的讀寫異常
前面的文章曾談到交易 (Transaction) 需要具有 ACID 的特性．在一個繁忙的資料庫系統中一定會有許多的交易同時執行，這篇文章便來談論許多交易同時執行時會遇到那些挑戰．
許多交易在進行時，非常有可能會遇到對相同的資料進行讀或寫的動作．如果所有的交易對相同的資料進行讀的動作，則這情況並沒有什麼好擔心的，因為所有的交易對這份資料都是讀的動作，早讀和晚讀都是同一個答案，所以不會造成任何的資料異常現象．但如果情況變成其中有一個交易或多個交易對同一份資料進行寫的動作時，那麼早寫和晚寫就會有很大的影響了．因此，我們在乎的情況便是當有交易在進行寫的動作．以下假設某個資料庫系統中有兩個交易，這兩個交易會對同一份資料進行讀和寫的動作:
如上圖所示，T1...
#58 資料庫引擎對交易 (Transaction) 的執行情況
在上次文章裡介紹了基礎的交易 (Transaction) 性質與特點，讓你可以了解為何關聯式資料庫引擎需要它．在一般的情況下，一個資料庫引擎在同一個時間內服務的應用程式非常可能不只一個，而且同一個應用程式也可能在同一個時間發出兩個不同的交易來要求資料庫引擎執行．因此，我們都知道一個資料庫引擎在同一時間執行多個來自用戶端的交易是相當平常的事情．同時可以服務多個用戶端等於是增加了整個系統的處理效能，也因為要同時服務多個用戶端，資料庫引擎的效能對於磁碟存取就會變得相當敏感．因為磁碟存取速度快，整體效能才夠快．但只有磁碟效率快就夠了嗎? 在上次文章裡介紹了交易的特點之後，你就能明白光是快還不夠，還需要在多個交易執行讀取之間不造成衝突才行．因此，資料庫引擎的設計就會面臨兩個挑戰:
1....
#54 資料庫的 Transaction (交易) - ACID 基本介紹
在關聯式資料庫 (Relational Database) 裡，Transaction 是一個極為重要的特性，或許也可以稱為功能．若我印象沒記錯，Transaction 在台灣的書藉裡普遍翻譯成 "交易"．雖然覺得用 "交易" 來表示蠻奇怪的，但也只能將就這情況，畢竟這翻譯詞已存在很久了．基本上而言，一個 Transaction 是指用戶端傳送給資料庫引擎所要執行的動作．這些動作通常是以 SQL 語法組成，然後再由資料庫引擎來解析語法，轉成各式各樣的動作來執行．比如，用戶端傳來了一個 Update Table1 set Column1='some...
#47 資料庫基礎 - 以 Hash 為基礎的 Index
前面的文章介紹了資料庫的 Index 是以 tree 為基礎的方式，一般來說大部份資料庫產品都用 B-tree 來建立 Index．然而，除了用 tree 以外，還可以用 Hash 的方式來建立．
可以用上圖來說明 hash index 的運作方式．首先，輸入值會先經過 hash function 的運算後而得到一個 hashed value，這個運作如以前的文章講的是一個 constant time 的運算．輸入值就是使用者要過濾的條件，也就是 SQL statement 中 where 的內容的欄位值．例如，學生證號碼，病歷編號等等．然而，這種輸入值若不是...
#45 資料庫基礎 - Page 的 Fill Factor
前面的文章介紹了許多資料庫引擎中有關 Storage management 的部份，讓你能了解資料庫引擎在處理儲存與讀取資料時所使用的原理基礎．但這些也都只是基礎的運作原理，真正實作的方式也會因為產品的不同也有些差異，但至少你知道了原理，這就能幫助你了解資料庫引擎的工作，也希望對你的學習與工作能有所幫助．
這篇文章將說明的是一個 Storage management 中管理資料的選項，對我而言，這是一個設計技巧．還記得前面的文章中曾提過 Page - 這是資料庫引擎用來儲存資料時所用的一個管理單位．一個 page 可能會有 4K 或 8K 或其他大小的容量設計，所以每個 page 的容量幾乎都是固定的．對一般正常運作的資料庫系統來說，對資料一定會進行新增刪除與修改的功能，所以這樣子的工作就常常會導致...
#42 資料庫基礎 - Index 所用的資料結構 B tree
在前面的文裡談了有關資料庫 Index，說明了為什麼 index 能加速尋找資料，也說明了 index 有那些種類．在這篇文中，將來簡單談一下 index 所使用的資料結構．
看了前面的文章後，想必你也可以很容易猜出 index 所使用的是像 tree 那樣的資料結構．在前面的文章中也談到了最基本的 tree 資料結構概念．tree 其實在電腦科學的領域裡應用的相當廣泛，不論是學術上或工業界裡，因為 tree 帶來的好處實在很多，但要把 tree 寫出來其實也不是一件很容易的事．不同的應用會衍生出不同的 tree，而在資料庫的 index 所採用的...
#37 資料庫基礎 - Clustered Index 與 Non-clustered Index
在編號 #33 的文章中介紹了什麼是 Index．這可以說是資料庫對資料能快速尋找的主要方法，基本上也是一個用空間換取時間的方法，也就是為了更快速地找到資料，於是犧牲了更多的硬碟儲存空間來達成這件事．也因為如此，所以資料庫引擎也需要有相對應的功能來妥善管理這些特別的儲存空間．然而，儲存空間的內容不同也會影響不同的管理方法，所以這一篇文章將來介紹不同的儲存空間 - Clustered Index 和 Non-clustered Index．
如果你曾撰寫過資料庫應用的相關程式或是你本身是資料庫管理員，相信你一定聽過 Clustered...
#33 資料庫基礎 - 什麼是 Index
Index 在資料庫的領域裡算是很基本且極為重要的項目，因為它幫助我們可以在龐大的資料裡快速地找到資料．這一篇文章就來說明 Index 運作的原理．
Index 也是一種典型的用空間換取時間的做法．這感覺就像是書籍裡最後面會有一些專有名詞在那一個頁數中可以找到，透過書籍的 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...
#28 資料庫基礎 - 存取 Page (Hashed File)
前面兩篇文章提到了存取 page 的兩種方式，在這一篇文章裡要介紹的是另一種方式，我們稱它為 hashed file．聽到這個名字，你可能已經猜到這是和 hash function 有關係的儲存方式．沒錯，它就是利用 hash function 來決定儲存位置，也是就說透過 hash function 的計算來決定要儲存到那一個 page 上．
前面的文章曾提到過基本的 hash function，也介紹了它最簡單的運算方式．所以，假設一開始有十個 page，然後有五筆資料，我們可以將每筆資料傳給 hash function，計算出來的結果是...
#26 資料庫基礎 - 存取 Page (Sorted File)
上一篇文章談的內容是針對資料之間是沒有順序的情況，因此在尋找資料時就是採用依照資料的排列順序來尋找．因此整個尋找過程的時間複雜度是 O(n) ．通常來說，資料庫設計者不會讓這樣的事情發生，除非資料本身是一個相當小的參考資料而己，否則資料一旦多了， O(n) 實在不是一個好現象．
在真實世界中的應用，我們常常可以為資料找到至少一種排列方法，例如，在學校的資料庫中，基本上可以用學生證的號碼來排序學生的資料，因為在同一個學校裡不會有相同的學生證號碼．我們在前面的文章中也提過，一旦資料排序過了之後，時間複雜度就會從 O(n) 下降成 O(log...
#25 資料庫基礎 - 存取 Page (Heap File)
在前面的幾篇文章中提到了資料庫引擎讀取與寫入資料時在面對固定長度與非固定長度時所可以採用的儲存方式，其中提供了 Page 為一個儲存空間的管理單位，透過 Page 的機制，讓資料庫引擎能以 Page 為單位做資料讀取與寫入的動作．搭配上 Page 裡的 manifest 資料，資料庫引擎就可以很清楚地知道這個 Page 裡面有多少筆資料以及有多少剩餘空間可用．這時候我們把層次往上拉高一點來看，那 Page 跟 Page 之間的關係是如何定義呢 ? 舉例來說，當某一個表格裡的資料繼續變多時，這些資料很可能會需要很多的...
#22 資料庫的資料實體儲存單位 Page - 3
在來延續上一篇文章 (#21 資料庫的資料實體儲存單位 Page - 2) 的內容．在上一篇的文章中看到了如果沒有 page 的概念時，資料庫引擎有那些可行的方法來在硬碟上管理資料，從上一篇文章中，你看感受到空白空間的處理與以及資料的定位並不是很方便．於是在階層管理的方便性上多加了一層 Page．
在一般市面上常見的資料庫產品中，Page 的大小都大約在幾Kb之間，類似於作業系統的儲存單位大小．所以，一個資料庫可能會包含一個或多個資料庫檔案，而每一個資料庫檔案都會包含多個 Page．
我們再看看如何用 Page 來管理資料．如上一篇文章的情況，資料有可變長度與固定長度兩種．固定長度的情況是比較單純好處理，可以參考下圖:
上圖是某一個...
#21 資料庫的資料實體儲存單位 Page - 2
延續上一篇文章 (#19 資料庫的資料實體儲存單位 Page) 的內容，在這篇文章裡，我們來談談有關資料庫的實體儲存結構．所謂的實體儲存結構是指資料放在硬碟中的情況．
首先，我們先來看看一個很簡單的結構，資料長度是固定的．這種情況在前面的文章有提過．因為長度都是固定的，所以每筆資料的長度便可以固定，這樣好處是在於方便計算也方便存取．
另一種情況是資料長度不是固定的，這種情況在前面文章也有提過．因為長度不是固定的，因此必須要想一個方法把不同欄位的資料做一個區隔，這樣在讀取資料時才知道什麼情況下是資料欄位的終點．在實體資料儲存時，有兩個方式可以來達成這種目的．第一，在每個資料欄位之間都用一個特殊符號隔開來，長相如下:
上圖是用一個...