資料庫是什麼？表格、SQL與索引的運作原理

生活中的例子

在網路商店按下訂購按鈕，庫存就少1件，訂單紀錄就多1筆。打開銀行的App，馬上就會顯示目前的餘額。這兩者的背後，都是把資料存進資料庫，或從資料庫取出來。

手機裡也有資料庫。那是一個叫SQLite的小型資料庫軟體。根據開發者的官方網站，Android和iPhone裡都有它。

本文要看看：為什麼能從大量資料中瞬間找到目標，又為什麼能放心把金錢的紀錄交給它。日本的IT Passport考試和基本資訊技術人員考試的出題範圍（課程大綱）裡的用語，也會用平常的話說明。

試算表檔案為什麼不夠用？

如果只是把資料做成表格，試算表軟體也辦得到。問題出在使用的人和資料量變多的時候。主要的理由有3個。

第1個是許多人同時寫入。大型網路商店每秒會收到好幾筆訂單。如果2個人各自打開同一個檔案修改，後存檔的一方可能會蓋掉前一方的修改。

第2個是讓資料遵守規則。「數量」欄裡出現文字，或出現不存在的會員的訂單。人工輸入時，這類錯誤就會混進來。資料庫可以在寫入的當下，拒絕不符合事先定好之規則的資料。

第3個是資料量與速度。Excel的1張工作表最多只能放1,048,576列（微軟的規格）。大型服務處理的列數比這多好幾個數量級，而且必須從中找出需要的那1列，不能讓使用者久等。

承擔這些工作的，是專門管理資料庫的軟體，稱為DBMS（資料庫管理系統）。產品有PostgreSQL、MySQL、SQLite、Oracle Database等。應用程式不自己把資料寫進檔案，而是請DBMS「幫我存這個」「幫我找這個」。

原理1：表格、列、欄與「鍵」

最廣泛使用的，是把資料以表格形式保存的方式，稱為關聯式資料庫。IBM的研究人員科德（Edgar Codd）在1970年的論文中提出了這個想法。

表格的橫向排列稱為「列」，縱向排列稱為「欄」。1列是1筆資料（例如1位會員），欄則是它的項目（姓名、地址等）。和試算表軟體不同的是，每一欄都能加上「只能是整數」「不可空白」之類的規則。

為了能指定唯一的1列，要先決定一個值絕不重複的欄，例如會員編號。這稱為主鍵。就算有2位同名的會員，只要用會員編號，就不會弄錯。

訂單表格的「會員編號」這一欄，指向會員表格的主鍵。像這樣指向其他表格主鍵的欄，稱為外鍵。如果想放入會員表格裡沒有的編號的訂單，DBMS會拒絕。

為什麼不在訂單表格裡直接寫會員的姓名呢？如果每筆訂單都寫上姓名，姓名改變時就得修改幾十列。只要漏改1處，資料就會互相矛盾。把表格拆開、讓同一件事實只寫在1個地方的設計步驟，稱為正規化。

原理2：SQL是寫「想要什麼」的語言

把要求傳達給DBMS的語言是SQL（讀作S-Q-L）。它由國際標準ISO/IEC 9075規定。各產品多少有些方言，但基本的寫法是共通的。

下面3個是針對上圖表格的SQL例子。它接近英文單字，唸出來就能抓到意思。為了方便閱讀，表格和欄的名稱用中文表示（實際的系統多半使用英文名稱）。

SELECT是「選出並取出」，FROM是「從哪個表格」，WHERE是「符合什麼條件的列」。SQL只寫「想要什麼」，不寫「按什麼順序找」。找法由DBMS看表格大小等情況，自己決定。

用會員編號把2個表格連起來，就能回答「大阪的會員訂了哪些商品」這種跨越兩個表格的問題。這時，外鍵就是連接的記號。

原理3：索引一口氣縮小搜尋範圍

假設要從1億列的訂單表格中，找出會員編號457的訂單。如果什麼都沒準備，DBMS只能從第1列開始，依序檢查所有的列。如果1列是100位元組，要讀的量就是10 GB。就算是連續讀取每秒約7 GB的高速SSD，算起來也要超過1秒。

因此，另外準備一份清單：把要搜尋的欄的值由小到大排好，並附註有該值的列在哪裡。這稱為索引。許多DBMS用「CREATE INDEX」這個指令建立（主鍵的欄會自動建立）。建好之後，DBMS判斷有用時就會自己使用，每次列有變動時也會自己更新。

DBMS和SSD或記憶體交換資料時，不是1列1列地讀寫，而是以固定大小的區塊為單位。這個區塊稱為「頁」（page）。大小在PostgreSQL通常是8 KB，在MySQL的標準方式（InnoDB）是16 KB。

列數有1億時，索引的清單本身也會變得很龐大。因此把清單按頁分段，再在上面疊上「哪一頁放到幾號為止」的導引層。這樣做出的樹狀索引，稱為B樹（B-tree）。Bayer與McCreight在1972年的論文中發表了它。

如圖所示，從上層開始1次讀1頁，選擇要往哪個分支走。1頁可以寫進數百個導引，所以每往下1層，範圍就縮小到數百分之一。假設1頁能放300個導引，3層就能分辨300×300×300的2,700萬列，4層能分辨81億列。即使是1億列的表格，大約讀4頁就能知道資料列的位置。

同樣的1億列，如果用每次把範圍減半的二分搜尋來找，最多比較27次。不過一開始比較的位置彼此相隔很遠，每比較1次就要讀不同的頁。同樣假設1頁放300筆，要讀的頁數將近20頁。B樹在1頁之中一次比較數百個候選，減少從慢速儲存裝置讀取的頁數。

PostgreSQL和MySQL（InnoDB）一般建立的索引，也屬於B樹家族。實際使用的是改良型，例如把最下層各頁橫向連起來、方便範圍搜尋的「B+樹」。

不過，索引不一定每次都會用到。如果符合條件的列占了表格的大半，從頭讀表格，有時比查索引再1列1列去取更快。要選哪一種，由DBMS估算後決定。

原理4：交易就是「全部做完，或完全不做」

想像A要轉帳1萬日圓給B。在資料庫裡，這需要2項修改：從A的餘額扣掉1萬日圓，以及在B的餘額加上1萬日圓。

如果第1項剛做完，伺服器就因停電而停止，會怎麼樣呢？A的錢減少了，卻沒有轉到B，1萬日圓就這樣消失了。為了防止這種情況，必須把2項修改當成不可分割的1組來處理。

這1組處理稱為交易（transaction）。在PostgreSQL等系統中，以BEGIN開始，最後寫上COMMIT，結果就會確定。途中發生問題時，用ROLLBACK回到開始前的狀態。

交易應該遵守的4項性質，取英文的字首，稱為ACID特性。Theo Härder與Andreas Reuter在1983年的論文中為它命名。下表用轉帳的例子，整理各項的意思。

為了守住隔離性，當2個處理要修改同一列時，DBMS會讓其中一方等一下。這就像在資料列上掛「使用中」的牌子，稱為鎖定（lock）。因此，即使2筆轉帳同時從同一個帳戶扣款，餘額的計算也不會出錯。

不過，讓處理等太久，整體就會變慢。因此可以用設定選擇要守到多嚴格。這個設定稱為隔離等級。

持久性靠寫入順序的巧思來守住。DBMS在改寫SSD上的表格之前，會先把「要改什麼、怎麼改」寫進另一份紀錄（日誌）。確認日誌已寫入SSD等裝置後，才回覆「完成」。即使停電，重新啟動時再讀一次日誌，就能把已確定的修改恢復回來。

關聯式資料庫與NoSQL

為了不適合表格形式的資料，以及規模非常大的服務，也有人做出了不使用表格的資料庫。關聯式資料庫以外的各種資料庫，統稱為NoSQL（讀作No-S-Q-L）。

容易理解的例子，是只要給名稱就回傳內容的方式。名稱稱為「鍵」（key），內容稱為「值」（value），所以叫做鍵值型。資料庫不在意內容裡裝的是什麼。

還有一種文件型，把1筆資料整個像1份文件一樣收起來。它能把1位會員的姓名和他的訂單清單，不拆成表格，當成1個整體保存。

許多NoSQL產品把資料分散放在多台伺服器上，設計成容易靠增加台數來擴大規模。這種做法稱為水平擴展。代價是有時會放棄一部分的嚴謹性。例如Amazon在2007年的論文中發表的鍵值型資料庫Dynamo，把「不停機」放在第一優先。依故障發生的方式，它允許各伺服器的內容暫時不一致。

與其說哪一種比較好，不如說是依用途分開使用。像金錢或庫存這種不允許不一致的資料，是關聯式資料庫的強項。想用多台伺服器處理大量存取時，NoSQL有時比較適合。

資料庫放在哪裡？

資料庫的內容，最後是伺服器裡的檔案。表格和索引都以頁的集合，寫在關掉電源也不會消失的SSD或HDD上。

不過，從SSD讀取1次要等約0.1毫秒，大約是記憶體（約100奈秒）的一千倍（「記憶體和儲存空間有什麼不同？」）。因此DBMS會把常用的頁的副本放在記憶體裡。根據MySQL的說明文件，專用伺服器常把最多約80%的記憶體分配給這個存放區。B樹的上層會被一再讀取，容易留在記憶體裡，所以多半只有下層需要到SSD去讀。

現在，向雲端業者租用資料庫服務的情況也越來越多。即使如此，資料仍放在業者資料中心裡伺服器的SSD等裝置上（「雲端運算是什麼？」）。

常見的誤解

從數字來看

B樹和全部讀取的數字，是把情況簡化後的參考值。實際的層數會隨鍵的長度和頁的填滿程度而變，讀取時間則取決於記憶體裡有沒有副本。

進一步學習

• 動手試試看：SQL練習工具、二元搜尋樹與堆積視覺化工具、RAID容量計算工具
• 用表格看差異：關聯式資料庫與NoSQL的差異、內部合併與外部合併的差異、SSD與HDD的差異
• 下一步的用語：E-R圖、第三正規化、檢視表、兩階段鎖定、死結、SQL隱碼攻擊
• 從基礎讀起：「記憶體和儲存空間有什麼不同？」、「演算法是什麼？」、「資料中心是什麼？」