sqlite 內部概述二 · 深入理解sqlite

## SQLite入門與分析(三)---內核概述(2) 寫在前面:本節是前一節內容的后續部分，這兩節都是從全局的角度SQLite內核各個模塊的設計和功能。只有從全局上把握SQLite，才會更容易的理解SQLite的實現。SQLite采用了層次化，模塊化的設計，而這些使得它的可擴展性和可移植性非常強。而且SQLite的架構與通用DBMS的結構差別不是很大，所以它對于理解通用DBMS具有重要意義。好了，下面我們開始討論SQLite剩余的兩部分：Back-end(后端)和compiler(編譯器)。 ###2、B-tree和Pager B-Tree使得VDBE可以在O(logN)下查詢，插入和刪除數據，以及O(1)下雙向遍歷結果集。B-Tree不會直接讀寫磁盤，它僅僅維護著頁面(pages)之間的關系。當B-TREE需要頁面或者修改頁面時，它就會調用Pager。當修改頁面時，pager保證原始頁面首先寫入日志文件，當它完成寫操作時，pager根據事務狀態決定如何做。B-tree不直接讀寫文件，而是通過page cache這個緩沖模塊讀寫文件對于性能是有重要意義的（注：這和操作系統讀寫文件類似，在Linux中,操作系統的上層模塊并不直接調用設備驅動讀寫設備，而是通過一個高速緩沖模塊調用設備驅動讀寫文件,并將結果存到高速緩沖區）。 ####2.1、數據庫文件格式（Database File Format）數據庫中所有的頁面都按從1開始順序標記。一個數據庫由許多B-tree構成——每一個表和索引都有一個B-tree（注：索引采用B-tree，而表采用B+tree，這主要是表和索引的需求不同以及B-tree和B+tree的結構不同決定的：B+tree的所有葉子節點包含了全部關鍵字信息，而且可以有兩種順序查找——具體參見《數據結構》，嚴蔚敏。而B-tree更適合用來作索引）。所有表和索引的根頁面都存儲在sqlite_master表中。數據庫中第一個頁面（page 1）有點特殊，page 1的前100個字節包含一個描述數據庫文件的特殊的文件頭。它包括庫的版本，模式的版本，頁面大小，編碼等所有創建數據庫時設置的參數。這個特殊的文件頭的內容在btree.c中定義，page 1也是sqlite_master表的根頁面。 ####2.1、頁面重用及回收(Page Reuse and Vacuum ) SQLite利用一個空閑列表(free list)進行頁面回收。當一個頁面的所有記錄都被刪除時，就被插入到該列表。當運行VACUUM命令時，會清除free list，所以數據庫會縮小，本質上它是在新的文件重新建立數據庫，而所有使用的頁在都被拷貝過去，而free list卻不會，結果就是一個新的，變小的數據庫。當數據庫的autovacuum開啟時，SQLite不會使用free list，而且在每一次commit時自動壓縮數據庫。 ####2.2、B-Tree記錄 B-tree中頁面由B-tree記錄組成，也叫做payloads。每一個B-tree記錄，或者payload有兩個域：關鍵字域(key field)和數據域(data field)。Key field就是ROWID的值，或者數據庫中表的關鍵字的值。從B-tree的角度，data field可以是任何無結構的數據。數據庫的記錄就保存在這些data fields中。B-tree的任務就是排序和遍歷，它最需要就是關鍵字。Payloads的大小是不定的，這與內部的關鍵字和數據域有關，當一個payload太大不能存在一個頁面內進便保存到多個頁面。 B+Tree按關鍵字排序，所有的關鍵字必須唯一。表采用B+tree，內部頁面不包含數據，如下： ![document/2015-09-15/55f7c2997b305](https://box.kancloud.cn/document_2015-09-15_55f7c2997b305.png) B+tree中根頁面(root page)和內部頁面(internal pages)都是用來導航的，這些頁面的數據域都是指向下級頁面的指針，僅僅包含關鍵字。所有的數據庫記錄都存儲在葉子頁面(leaf pages)內。在葉節點一級，記錄和頁面都是按照關鍵字的順序的，所以B-tree可以水平方向遍歷，時間復雜度為O(1)。 ####2.3、記錄和域（Records and Fields）位于葉節點頁面的數據域的記錄由VDBE管理，數據庫記錄以二進制的形式存儲，但有一定的數據格式。記錄格式包括一個邏輯頭（logical header）和一個數據區(data segment)，header segment包括header的大小和一個數據類型數組，數據類型用來在data segment的數據的類型，如下： ![document/2015-09-15/55f7c2b0b1587](https://box.kancloud.cn/document_2015-09-15_55f7c2b0b1587.png) ####2.4、層次數據組織(Hierarchical Data Organization) ![document/2015-09-15/55f7c2cb8a7a2](https://box.kancloud.cn/document_2015-09-15_55f7c2cb8a7a2.png) 從上往下，數據越來越無序，從下向上，數據越來越結構化. ####2.5、B-Tree API B-Tree模塊有它自己的API，它可以獨立于C API使用。另一個特點就是它支持事務。由pager處理的事務，鎖和日志都是為B-tree服務的。根據功能可以分為以下幾類： 2.5.1、訪問和事務函數 ~~~ sqlite3BtreeOpen: Opens a new database file. Returns a B-tree object. sqlite3BtreeClose: Closes a database. sqlite3BtreeBeginTrans: Starts a new transaction. sqlite3BtreeCommit: Commits the current transaction. sqlite3BtreeRollback: Rolls back the current transaction. sqlite3BtreeBeginStmt: Starts a statement transaction. sqlite3BtreeCommitStmt: Commits a statement transaction. sqlite3BtreeRollbackStmt: Rolls back a statement transaction. ~~~ 2.5.2、表函數 ~~~ sqlite3BtreeCreateTable: Creates a new, empty B-tree in a database file. sqlite3BtreeDropTable: Destroys a B-tree in a database file. sqlite3BtreeClearTable: Removes all data from a B-tree, but keeps the B-tree intact. ~~~ 2.5.3、游標函數(Cursor Functions) ~~~ sqlite3BtreeCursor: Creates a new cursor pointing to a particular B-tree. sqlite3BtreeCloseCursor: Closes the B-tree cursor. sqlite3BtreeFirst: Moves the cursor to the first element in a B-tree. sqlite3BtreeLast: Moves the cursor to the last element in a B-tree. sqlite3BtreeNext: Moves the cursor to the next element after the one it is currently pointing to. sqlite3BtreePrevious: Moves the cursor to the previous element before the one it is currently pointing to. sqlite3BtreeMoveto: Moves the cursor to an element that matches the key value passed in as a parameter. ~~~ 2.5.4、記錄函數(Record Functions) ~~~ sqlite3BtreeDelete: Deletes the record that the cursor is pointing to. sqlite3BtreeInsert: Inserts a new element in the appropriate place of the B-tree. sqlite3BtreeKeySize: Returns the number of bytes in the key of the record that the cursor is pointing to. sqlite3BtreeKey: Returns the key of the record the cursor is currently pointing to. sqlite3BtreeDataSize: Returns the number of bytes in the data record that the cursor is currently pointing to. sqlite3BtreeData: Returns the data in the record the cursor is currently pointing to. ~~~ 2.5.5、配置函數(Configuration Functions) sqlite3BtreeSetCacheSize: Controls the page cache size as well as the synchronous writes (as defined in the synchronous pragma).sqlite3BtreeSetSafetyLevel: Changes the way data is synced to disk in order to increase or decrease how well the database resists damage due to OS crashes and power failures. Level 1 is the same as asynchronous (no syncs() occur and there is a high probability of damage). This is the equivalent to pragma synchronous=OFF. Level 2 is the default. There is a very low but non-zero probability of damage. This is the equivalent to pragma synchronous=NORMAL. Level 3 reduces the probability of damage to near zero but with a write performance reduction. This is the equivalent to pragma synchronous=FULL.sqlite3BtreeSetPageSize: Sets the database page size.sqlite3BtreeGetPageSize: Returns the database page size.sqlite3BtreeSetAutoVacuum: Sets the autovacuum property of the database.sqlite3BtreeGetAutoVacuum: Returns whether the database uses autovacuum.sqlite3BtreeSetBusyHandler: Sets the busy handler ####2.6、實例分析最后以sqlite3_open的具體實現結束本節的討論(參見Version 3.6.10的源碼)： ![document/2015-09-15/55f7c2ee529be](https://box.kancloud.cn/document_2015-09-15_55f7c2ee529be.png) 由上圖可以知道，SQLite的所有IO操作，最終都轉化為操作系統的系統調用(一名話：DBMS建立在痛苦的OS之上)。同時也可以看到SQLite的實現非常的層次化，模塊化，使得SQLite更易擴展，可移植性非常強。 ###3、編譯器（Compiler） ####3.1、分詞器(Tokenizer) 接口把要執行的SQL語句傳遞給Tokenizer,Tokenizer按照SQL的詞法定義把它切分一個一個的詞，并傳遞給分析器(Parser)進行語法分析。分詞器是手工寫的，主要在Tokenizer.c中實現。 ####3.2、分析器(Parser) SQLite的語法分析器是用Lemon——一個開源的LALR(1)語法分析器的生成器，生成的文件為parser.c。一個簡單的語法樹： SELECT rowid, name, season FROM episodes WHERE rowid=1 LIMIT 1 ![document/2015-09-15/55f7c30630412](https://box.kancloud.cn/document_2015-09-15_55f7c30630412.png) #### 3.3、代碼生成器（Code Generator）代碼生成器是SQLite中取龐大，最復雜的部分。它與Parser關系緊密，根據語法分析樹生成VDBE程序執行SQL語句的功能。由諸多文件構成：select.c,update.c,insert.c,delete.c,trigger.c,where.c等文件。這些文件生成相應的VDBE程序指令，比如SELECT語句就由select.c生成。下面是一個讀操作中打開表的代碼的生成實現： ~~~ /* Generate code that will open a table for reading. */ void sqlite3OpenTableForReading( Vdbe *v, /* Generate code into this VDBE */ int iCur, /* The cursor number of the table */ Table *pTab /* The table to be opened */ ){ sqlite3VdbeAddOp(v, OP_Integer, pTab->iDb, 0); sqlite3VdbeAddOp(v, OP_OpenRead, iCur, pTab->tnum); VdbeComment((v, "# %s", pTab->zName)); sqlite3VdbeAddOp(v, OP_SetNumColumns, iCur, pTab->nCol); } ~~~ Sqlite3vdbeAddOp函數有三個參數：（1）VDBE實例（它將添加指令），（2）操作碼（一條指令），（3）兩個操作數。 ####3.4、查詢優化代碼生成器不僅負責生成代碼，也負責進行查詢優化。主要的實現位于where.c中，生成的WHERE語句塊通常被其它模塊共享，比如select.c，update.c以及delete.c。這些模塊調用sqlite3WhereBegin()開始WHERE語句塊的指令生成，然后加入它們自己的VDBE代碼返回，最后調用sqlite3WhereEnd()結束指令生成，如下： ![document/2015-09-15/55f7c31b54538](https://box.kancloud.cn/document_2015-09-15_55f7c31b54538.png)