數(shù)據(jù)庫是構建軟件系統(tǒng)的重要組成部分，用于高效地存儲和讀取數(shù)據(jù)。在這里，我們將使用 SQLite 的早期版本來討論數(shù)據(jù)庫實現(xiàn)的一些架構細節(jié)。

SQLite 是一個小型數(shù)據(jù)庫應用程序，用于數(shù)百萬個軟件和設備。SQLite 是由 D.Richard Hipp 于 2000 年 8 月發(fā)明的。SQLite 是一種高性能、輕量級的關系數(shù)據(jù)庫。如果您愿意在編碼級別學習數(shù)據(jù)庫的內部結構，那么 SQLite 是最好的開源數(shù)據(jù)庫，它具有高度可讀的源代碼和大量文檔。閱讀更高版本的 SQLite 變得有點困難，因為它包含許多新功能。為了理解數(shù)據(jù)庫內部的基本實現(xiàn)，你應該對數(shù)據(jù)結構有很好的了解，一些關于計算理論的知識，以及操作系統(tǒng)是如何工作的。

在這里，我們將研究 SQLite 2.5.0 版本。您可以在GitHub上找到SQLite 后端的簡單實現(xiàn)。 另外，我發(fā)現(xiàn)這個存儲庫 包含用于代碼讀取的 SQLite 2.5.0 實現(xiàn)。

什么是數(shù)據(jù)庫？

將數(shù)據(jù)保存在平面文件中讀取和存儲數(shù)據(jù)的效率不高。數(shù)據(jù)庫以適當?shù)捻樞蚪M織數(shù)據(jù)，以便數(shù)據(jù)讀取和寫入速度更快。數(shù)據(jù)可以是結構化的、半結構化的或非結構化的。數(shù)據(jù)庫主要用于存儲結構化和半結構化數(shù)據(jù)。可以根據(jù)要存儲的數(shù)據(jù)結構類型對數(shù)據(jù)庫進行如下挖掘。

1. 關系型數(shù)據(jù)庫：常用的具有表結構的數(shù)據(jù)庫類型。表可以與其他表有關系。SQL 語言用于操作此類數(shù)據(jù)庫上的數(shù)據(jù)。
2. 鍵值數(shù)據(jù)庫：與關聯(lián)的鍵一起存儲的數(shù)據(jù)?？梢允褂媒o定的鍵檢索數(shù)據(jù)。內存數(shù)據(jù)庫通常是這種類型的數(shù)據(jù)庫。
3. 對象數(shù)據(jù)庫：數(shù)據(jù)結構更像是一個對象而不是一個表。
4. 圖數(shù)據(jù)庫：圖數(shù)據(jù)庫是節(jié)點和邊的集合，主要用于數(shù)據(jù)挖掘和社交媒體應用程序。

SQLite 數(shù)據(jù)庫架構

SQLite 數(shù)據(jù)庫架構分為兩個不同的部分，分別命名為核心和后端。核心部分包含接口、分詞器、解析器、代碼生成器和虛擬機，它們?yōu)閿?shù)據(jù)庫事務創(chuàng)建執(zhí)行順序。后端包含 B-tree、Pager 和 OS 接口來訪問文件系統(tǒng)。Tokenizer、Parser 和代碼生成器統(tǒng)稱為編譯器，它生成一組運行在虛擬機上的操作碼。

從哪里開始？

要了解數(shù)據(jù)庫的架構，您需要具備以下先決條件。

1. 對數(shù)據(jù)結構和算法有很好的理解。尤其是 B 樹、鏈表、Hashmaps 等數(shù)據(jù)結構。
2. 對計算機體系結構有一定的了解。如何讀寫磁盤，分頁和緩存如何工作。
3. 有限自動機、上下文無關語法等理論計算機和一些正則表達式知識。

SQLite 架構

VFS（虛擬文件系統(tǒng)）

Unix 和 Windows 上的文件訪問彼此不同。VFS 提供通用 API 來訪問文件，而無需考慮其運行的操作系統(tǒng)類型。該 API 包括打開、讀取、寫入和關閉文件的函數(shù)。以下是 VFS 中用于讀取、寫入數(shù)據(jù)到文件中的一些 API。

/* 
Create a connection to file to read write 
zFilename : file name 
id : file pointer 
pReadonly : read or write 
*/
int sqliteOsOpenReadWrite(const char *zFilename, OsFile *id,int *pReadonly);
/* 
Acqure the lock to read file. This function should be 
called before caling to any file read function. 
Return 0 if success
id : file pointer 
*/
int sqliteOsReadLock(OsFile *id);
/* 
Get the write lock to write into a file. This function should called before
doing any write operation into the file system.
Return 0 if success
id : file pointer
*/
int sqliteOsWriteLock(OsFile *id);
/* 
Move to the given number of offest to read or write into the file
*/
int sqliteOsSeek(OsFile *id, int offset);
/* 
Read amt bytes from the file with offset pointed by sqliteOsSeek
*/
int sqliteOsRead(OsFile *id, void *pBuf, int amt);
/* 
Write amt bytes from the pBuf into the file
*/
int sqliteOsWrite(OsFile *id, const void *pBuf, int amt);

在這里，您可以使用 sqliteOpenReadWrite 函數(shù)開始使用文件。此函數(shù)為您提供一個指向文件的指針，該文件可用于讀取或寫入數(shù)據(jù)。接下來，應該在執(zhí)行任何讀寫操作之前獲取鎖。如果它只是一個讀操作，那么應該獲取讀鎖。應該為讀和寫事務獲取寫鎖。 

然后可以通過將文件的偏移量提供給 sqliteOsSeek 函數(shù)來查找位置來完成讀寫。偏移量是從文件的起點到數(shù)據(jù)應該寫入或讀取的位置的字節(jié)數(shù)。

Pager

頁是文件系統(tǒng)上數(shù)據(jù)庫事務的最小單位。當數(shù)據(jù)庫需要從文件中讀取數(shù)據(jù)時，它會將它作為一個頁面來請求。一旦頁面被加載到數(shù)據(jù)庫引擎中，如果它經(jīng)常訪問它的緩存，它就可以存儲該頁面。頁數(shù)從一頁開始編號。第一個頁面稱為根頁面。頁的大小是恒定的。

/*
Open pager with the given file name
*/
int sqlitepager_open(Pager **ppPager,const char *zFilename,int nPage,int nEx);
/*
Get page specified by the page number
*/
int sqlitepager_get(Pager *pPager, Pgno pgno, void **ppPage);
/*
Start to write data into a page specified in pData
*/
int sqlitepager_write(void *pData);
/*
Commit page changes into the file
*/
int sqlitepager_commit(Pager*);
/*
Close the connection to the file
*/
int sqlitepager_close(Pager *pPager);

Btree

Btree 是一種數(shù)據(jù)結構，用于根據(jù)數(shù)據(jù)的值將數(shù)據(jù)存儲為樹。BTree 最簡單的形式是二叉樹。數(shù)據(jù)庫使用 Btree 數(shù)據(jù)結構來存儲索引以提高數(shù)據(jù)庫的性能。Btree 的每個節(jié)點都包含一個用于索引的鍵列表?？梢詾楸碇械拿恳涣袆?chuàng)建 Btree 索引。每個 Btree 都有根頁面，這是任何 Btree 搜索的起點。

為了指向 Btree 上的一行，使用了稱為“Cursor”的特殊指針。游標用于指向一個記錄，該記錄由頁面 id 和偏移量指定，稱為 idx。SQLite 將數(shù)據(jù)庫模式存儲在稱為“master_table”的表上。master_table 總是存儲在數(shù)據(jù)庫的第一頁上。 

了解更多關于SQLite的B樹的設計在這個文章。

/*
Open file connection to a page file name specified by zFileName with 
nCache size cache
*/
int sqliteBtreeOpen(const char *zFilename, int mode, int nCache, Btree **ppBtree)
/*
Start transaction. This function should called before any btree modification 
operations
*/
int sqliteBtreeBeginTrans(Btree *pBt)
/*
Insert key pKey with nKey byte and value pData with nData byte put 
into the Btree
*/
int sqliteBtreeInsert(BtCursor *pCur, const void *pKey, int nKey, 
                      const void *pData, int nData)
/*
Write data into the file
*/
int sqliteBtreeCommit(Btree *pBt)
/*
Move cursor to the matching pKey with nKey bytes
*/
int sqliteBtreeMoveto(BtCursor *pCur, const void *pKey, int nKey, int *pRes)

VDBE（虛擬數(shù)據(jù)庫引擎）

VDBE 是運行一組操作的虛擬機，由代碼生成器生成。包括插入、刪除、更新、選擇在內的所有 SQL 命令都轉換成一組操作碼，然后在虛擬機上運行。每個操作碼包含三個名為 p1、p2 和 p3 的輸入。您可以將此輸入視為函數(shù)的輸入。

下面我為以下 SQL 選擇語句添加了示例執(zhí)行操作碼堆棧。PC 是程序計數(shù)器的指令 ID。 對我來說，SQLite 中最有趣的事情是我可以通過在 SQL 查詢的開頭附加“explain”關鍵字來查看給定 SQL 代碼的一組 VBDE 操作碼指令。

explain select * from foo;

編譯器

Tokenizer、Parser 和 Code Generator 統(tǒng)稱為編譯器，可生成在 VBDE 上運行的操作碼集。Tokenizer 通過掃描 SQL 代碼生成一組令牌。然后，它驗證語法并生成解析樹。Lemon 解析器用于通過預定義的上下文無關語法來解析給定的 SQL 代碼。代碼生成器將這個解析樹轉換成一個用 SQLite 操作碼編寫的小程序。

結論

SQLite 是一種簡單、輕量級、高性能的關系型數(shù)據(jù)庫，廣泛用于軟件設計。SQLite 的早期版本是用簡單的架構和高度可讀的代碼編寫的。Pager 提供了一個抽象層，將數(shù)據(jù)作為固定大小的塊讀寫到文件系統(tǒng)中。而 Btree 提供了一種在內存中存儲數(shù)據(jù)的高效方式，以更快地訪問數(shù)據(jù)。當 SQL 進入 SQLite 時，它??會將 SQL 轉換為 SQLite 機器碼并在 VBDE 上運行。結果通過 API 返回給用戶。