數(shù)據(jù)庫是構(gòu)建軟件系統(tǒng)的重要組成部分,用于高效地存儲和讀取數(shù)據(jù)。在這里,我們將使用 SQLite 的早期版本來討論數(shù)據(jù)庫實現(xiàn)的一些架構(gòu)細(xì)節(jié)。
SQLite 是一個小型數(shù)據(jù)庫應(yīng)用程序,用于數(shù)百萬個軟件和設(shè)備。SQLite 是由 D.Richard Hipp 于 2000 年 8 月發(fā)明的。SQLite 是一種高性能、輕量級的關(guān)系數(shù)據(jù)庫。如果您愿意在編碼級別學(xué)習(xí)數(shù)據(jù)庫的內(nèi)部結(jié)構(gòu),那么 SQLite 是最好的開源數(shù)據(jù)庫,它具有高度可讀的源代碼和大量文檔。閱讀更高版本的 SQLite 變得有點困難,因為它包含許多新功能。為了理解數(shù)據(jù)庫內(nèi)部的基本實現(xiàn),你應(yīng)該對數(shù)據(jù)結(jié)構(gòu)有很好的了解,一些關(guān)于計算理論的知識,以及操作系統(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ù)庫以適當(dāng)?shù)捻樞蚪M織數(shù)據(jù),以便數(shù)據(jù)讀取和寫入速度更快。數(shù)據(jù)可以是結(jié)構(gòu)化的、半結(jié)構(gòu)化的或非結(jié)構(gòu)化的。數(shù)據(jù)庫主要用于存儲結(jié)構(gòu)化和半結(jié)構(gòu)化數(shù)據(jù)??梢愿鶕?jù)要存儲的數(shù)據(jù)結(jié)構(gòu)類型對數(shù)據(jù)庫進(jìn)行如下挖掘。
- 關(guān)系型數(shù)據(jù)庫:常用的具有表結(jié)構(gòu)的數(shù)據(jù)庫類型。表可以與其他表有關(guān)系。SQL 語言用于操作此類數(shù)據(jù)庫上的數(shù)據(jù)。
- 鍵值數(shù)據(jù)庫:與關(guān)聯(lián)的鍵一起存儲的數(shù)據(jù)。可以使用給定的鍵檢索數(shù)據(jù)。內(nèi)存數(shù)據(jù)庫通常是這種類型的數(shù)據(jù)庫。
- 對象數(shù)據(jù)庫:數(shù)據(jù)結(jié)構(gòu)更像是一個對象而不是一個表。
- 圖數(shù)據(jù)庫:圖數(shù)據(jù)庫是節(jié)點和邊的集合,主要用于數(shù)據(jù)挖掘和社交媒體應(yīng)用程序。
SQLite 數(shù)據(jù)庫架構(gòu)
SQLite 數(shù)據(jù)庫架構(gòu)分為兩個不同的部分,分別命名為核心和后端。核心部分包含接口、分詞器、解析器、代碼生成器和虛擬機,它們?yōu)閿?shù)據(jù)庫事務(wù)創(chuàng)建執(zhí)行順序。后端包含 B-tree、Pager 和 OS 接口來訪問文件系統(tǒng)。Tokenizer、Parser 和代碼生成器統(tǒng)稱為編譯器,它生成一組運行在虛擬機上的操作碼。
從哪里開始?
要了解數(shù)據(jù)庫的架構(gòu),您需要具備以下先決條件。
- 對數(shù)據(jù)結(jié)構(gòu)和算法有很好的理解。尤其是 B 樹、鏈表、Hashmaps 等數(shù)據(jù)結(jié)構(gòu)。
- 對計算機體系結(jié)構(gòu)有一定的了解。如何讀寫磁盤,分頁和緩存如何工作。
- 有限自動機、上下文無關(guān)語法等理論計算機和一些正則表達(dá)式知識。
SQLite 架構(gòu)
VFS(虛擬文件系統(tǒng))
Unix 和 Windows 上的文件訪問彼此不同。VFS 提供通用 API 來訪問文件,而無需考慮其運行的操作系統(tǒng)類型。該 API 包括打開、讀取、寫入和關(guān)閉文件的函數(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ù)為您提供一個指向文件的指針,該文件可用于讀取或?qū)懭霐?shù)據(jù)。接下來,應(yīng)該在執(zhí)行任何讀寫操作之前獲取鎖。如果它只是一個讀操作,那么應(yīng)該獲取讀鎖。應(yīng)該為讀和寫事務(wù)獲取寫鎖。
然后可以通過將文件的偏移量提供給 sqliteOsSeek 函數(shù)來查找位置來完成讀寫。偏移量是從文件的起點到數(shù)據(jù)應(yīng)該寫入或讀取的位置的字節(jié)數(shù)。
Pager
頁是文件系統(tǒng)上數(shù)據(jù)庫事務(wù)的最小單位。當(dāng)數(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ù)結(jié)構(gòu),用于根據(jù)數(shù)據(jù)的值將數(shù)據(jù)存儲為樹。BTree 最簡單的形式是二叉樹。數(shù)據(jù)庫使用 Btree 數(shù)據(jù)結(jié)構(gòu)來存儲索引以提高數(shù)據(jù)庫的性能。Btree 的每個節(jié)點都包含一個用于索引的鍵列表。可以為表中的每一列創(chuàng)建 Btree 索引。每個 Btree 都有根頁面,這是任何 Btree 搜索的起點。
為了指向 Btree 上的一行,使用了稱為“Cursor”的特殊指針。游標(biāo)用于指向一個記錄,該記錄由頁面 id 和偏移量指定,稱為 idx。SQLite 將數(shù)據(jù)庫模式存儲在稱為“master_table”的表上。master_table 總是存儲在數(shù)據(jù)庫的第一頁上。
了解更多關(guān)于SQLite的B樹的設(shè)計在這個文章。
/*
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 是運行一組操作的虛擬機,由代碼生成器生成。包括插入、刪除、更新、選擇在內(nèi)的所有 SQL 命令都轉(zhuǎn)換成一組操作碼,然后在虛擬機上運行。每個操作碼包含三個名為 p1、p2 和 p3 的輸入。您可以將此輸入視為函數(shù)的輸入。
下面我為以下 SQL 選擇語句添加了示例執(zhí)行操作碼堆棧。PC 是程序計數(shù)器的指令 ID。 對我來說,SQLite 中最有趣的事情是我可以通過在 SQL 查詢的開頭附加“explain”關(guān)鍵字來查看給定 SQL 代碼的一組 VBDE 操作碼指令。
explain select * from foo;
個人電腦 | 操作碼 | P1 | P2 | P3 | 評論 |
1 | 列數(shù) | 1 | 0 | 將列數(shù)設(shè)置為 1 | |
2 | 列名 | 0 | 0 | 價值 | 將列名設(shè)置為“值” |
3 | 打開 | 0 | 3 | 富 | 打開光標(biāo)并將其指向第三頁,即 foo 表的根頁(p3 不重要 |
4 | 驗證Cookies | 46 | 0 | 確保架構(gòu)未更改 | |
5 | 倒帶 | 0 | 11 | 將光標(biāo)移動到第一個條目 | |
6 | 柱子 | 0 | 0 | 從 Btree 負(fù)載讀取數(shù)據(jù)并將其放入堆棧 | |
7 | 柱子 | 0 | 0 | ||
8 | ne | 1 | 10 | 從堆棧中彈出頂部的兩個元素。如果它們不相等,則跳轉(zhuǎn)到指令 P2。否則,繼續(xù)執(zhí)行下一條指令。 | |
9 | 打回來 | 1 | 0 | 從堆棧中彈出 P1 值并將它們組成一個數(shù)組。這將是此 SQL 表達(dá)式的結(jié)果行 | |
10 | 下一個 | 0 | 5 | 將光標(biāo)移動到下一條記錄,如果數(shù)據(jù)退出轉(zhuǎn)到 P2 否則轉(zhuǎn)到下一行 | |
11 | 關(guān)閉 | 0 | 0 | 關(guān)閉光標(biāo) |
編譯器
Tokenizer、Parser 和 Code Generator 統(tǒng)稱為編譯器,可生成在 VBDE 上運行的操作碼集。Tokenizer 通過掃描 SQL 代碼生成一組令牌。然后,它驗證語法并生成解析樹。Lemon 解析器用于通過預(yù)定義的上下文無關(guān)語法來解析給定的 SQL 代碼。代碼生成器將這個解析樹轉(zhuǎn)換成一個用 SQLite 操作碼編寫的小程序。
結(jié)論
SQLite 是一種簡單、輕量級、高性能的關(guān)系型數(shù)據(jù)庫,廣泛用于軟件設(shè)計。SQLite 的早期版本是用簡單的架構(gòu)和高度可讀的代碼編寫的。Pager 提供了一個抽象層,將數(shù)據(jù)作為固定大小的塊讀寫到文件系統(tǒng)中。而 Btree 提供了一種在內(nèi)存中存儲數(shù)據(jù)的高效方式,以更快地訪問數(shù)據(jù)。當(dāng) SQL 進(jìn)入 SQLite 時,它??會將 SQL 轉(zhuǎn)換為 SQLite 機器碼并在 VBDE 上運行。結(jié)果通過 API 返回給用戶。