所有應用軟體之中,資料庫可能是最複雜的。
MySQL的手冊有3000多頁,PostgreSQL的手冊有2000多頁,Oracle的手冊更是比它們相加還要厚。
但是,自己寫一個最簡單的資料庫,做起來並不難。 Reddit上面有一個帖子,只用了幾百個字,就把原理講清楚了。以下是我根據這篇貼文整理的內容。
一、數據以文字形式保存
第一步,就是將所要保存的數據,寫入文字檔案。這個文字檔就是你的資料庫。
為了方便讀取,資料必須分成記錄,每一筆記錄的長度規定為等長。例如,假定每筆記錄的長度是800字節,那麼第5筆記錄的開始位置就在3200位元組。
大多時候,我們不知道某一筆記錄在第幾個位置,只知道主鍵(primary key)的值。這時為了讀取數據,可以一則比對記錄。但這樣做效率太低,實際應用中,資料庫往往採用B樹(B-tree)格式儲存資料。
二、什麼是B樹?
要理解B樹,必須從二元查找樹(Binary search tree)講起。
二叉查找樹是一種查找效率非常高的資料結構,它有三個特點。
(1)每個節點最多只有兩個子樹。
(2)左子樹都為小於父節點的值,右子樹都大於父節點的值。
(3)在n個節點中找到目標值,一般只需要log(n)次比較。
二元查找樹的結構不適合資料庫,因為它的尋找效率與層數相關。越處在下層的數據,就需要越多次比較。極端情況下,n個資料需要n次比較才能找到目標值。對於資料庫來說,每進入一層,就要從硬碟讀取一次數據,這非常致命,因為硬碟的讀取時間遠大於數據處理時間,資料庫讀取硬碟的次數越少越好。
B樹是對二元查找樹的改良。它的設計想法是,將相關數據盡量集中在一起,以便一次讀取多個數據,減少硬碟操作次數。
B樹的特徵也有三個。
(1)一個節點可以容納多個值。例如上圖中,最多的一個節點容納了4個值。
(2)除非資料已經填滿,否則不會增加新的層。也就是說,B樹追求"層"越少越好。
(3)子節點中的值,與父節點中的值,有嚴格的大小對應關係。一般來說,如果父節點有a個值,那麼就有a+1個子節點。例如上圖中,父節點有兩個值(7和16),就對應三個子節點,第一個子節點都是小於7的值,最後一個子節點都是大於16的值,中間的子節點就是7和16之間的數值。
這種資料結構,非常有利於減少讀取硬碟的次數。假設一個節點可以容納100個值,那麼3層的B樹可以容納100萬個數據,如果換成二元查找樹,則需要20層!假定作業系統一次讀取一個節點,根節點保留在記憶體中,那麼B樹在100萬個資料中找出目標值,只需要讀取兩次硬碟。
三、索引
資料庫以B樹格式儲存,只解決了依照"主鍵"找出資料的問題。如果想要查找其他字段,就需要建立索引(index)。
所謂索引,就是以某個字段為關鍵字的B樹檔案。假定有一張"僱員表",包含了員工號碼(主鍵)和姓名兩個欄位。姓名可以建立索引文件,該文件以B樹格式對姓名進行儲存,每個姓名後面是其在資料庫中的位置(即第幾條記錄)。查找姓名的時候,先從索引中找到對應第幾筆記錄,然後再從表格中讀取。
這種索引查找方法,叫做"索引順序存取方法"(Indexed Sequential Access Method),縮寫為ISAM。它已經有多種實作(例如C-ISAM函式庫和D-ISAM函式庫),只要使用這些程式碼庫,就能自己寫一個最簡單的資料庫。
四、進階功能
部署了最基本的資料存取(包括索引)以後,還可以實現一些進階功能。
(1)SQL語言是資料庫通用操作語言,所以需要一個SQL解析器,將SQL指令解析為對應的ISAM操作。
(2)資料庫連線(join)是指資料庫的兩張表透過"外鍵",建立連接關係。你需要對這種操作進行最佳化。
(3)資料庫事務(transaction)是指批量進行一系列資料庫操作,只要有一步不成功,整個操作都不成功。所以需要有一個"操作日誌",以便失敗時可以回滾操作。
(4)備份機制:保存資料庫的副本。
(5)遠端操作:使得使用者可以在不同的機器上,透過TCP/IP協定操作資料庫。