sqlite3存儲格式
本篇介紹sqlite3資料庫檔案的存儲格式。
通過閱讀源讀源代碼可以知道sqlite的設計思想。
一個sqlite資料庫檔案對應着一個資料庫。sqlite将資料庫檔案劃分大小一緻的存儲（以區分記憶體）頁面，并通過一系列資料結構将它們組織起來。
sqlite組織頁面的資料結構主要有B樹和二維連結清單。每一個頁面要麼是B樹的葉子或結點，要麼是二維連結清單的一個節點。用作B樹的頁面都有8或12位元組的頁面資訊頭，特别地第一個頁面除了是表的根結點是資料庫檔案的根，是以它首先包含100位元組的是庫資訊，然後才是作為一個是B樹的根結點。另一方面閑置的頁面沒有頁面頭，它的鍊頭是在第一個頁面的庫資訊頭。二維連結清單的第一維由單向連結清單實作，第二維由數組實作。用作第一維節點的頁面也是一個空閑頁面，被統計在庫資訊頭。
資料庫層面的表和索引，在底層存儲格式中用B樹結構組織，第一張表或索引都對應着一棵B樹。底層存儲中所有空閑（閑置）頁面，都由二維連結清單連結起來。
B樹頁面，有統一的存儲格式。首先是頁面資訊頭，然後緊跟着頁内資料排序索引（請區分資料庫的表索引，這裡是資料結構中的外部排序索引）數組；而頁内資料存儲在頁面的尾部。資料索引和資料單元分别從正反兩個方向向頁面中間伸展，頁面中間部分形式空閑區域。
sqlite資料庫檔案使用自然位元組序存儲資料，這種位元組序有利于它裡面使用到可變長整形解釋。
各種具體的資料結構和詳細的格式編排請自行參閱源代碼，不一一貼上劃水。自行用任意一門程式設計語言寫程式周遊解讀sqlite資料庫檔案其中的内容。
在這裡定義本篇使用的一些術語：
頁面，資料庫檔案頁面，請區分記憶體頁面或虛位址空間頁面，盡管sqlite預設頁面大小也是4KB。
指針，請區分c語言指針，這裡指檔案内位址索引，或頁面内位址偏移。
單元，cell,存儲在B樹頁面的機關資料。
整型主鍵，sqlite表預設的自增計數。
變長整型，sqlite存儲中使用到的一種基于自然位元組序的變長整數存儲方式。每位元組低7位為有效數值位，高位标記下一位元組是否繼續為目前變長整數的一部分，高位為0表示為變長整數的最後一個位元組。
葉子，B樹的葉子結點。
結點，B樹的非終端結點。
索引，當提及結構化查詢時指索引表，而當提及低層存儲格式時等同于編号，位址和指針。
前面總括了底層存儲組織，現在結合上一層資料庫層來看存儲組織，庫和表的存儲。sqlite将一切表和索引視作表，并以B樹的形式儲存在資料庫檔案。sqlite資料庫預設有一張管理表，名為sqlite_master。這張表記錄着使用者建立的所有表和索引的名字，左聯合表名，表的根頁面索引号以及建立sql語句。也就是資料庫檔案的第一頁面一棵入口B樹的根，通過這棵樹可以索引到其它B樹（資料庫層面表或索引）的根。當sqlite打開某一張表時，必須周遊管理表找出與表名比對的記錄，進而找出記錄中根頁面索引号，才能定位到表的入口位置。索引和表是分開存儲的，表預設使用是自增計數，因為存儲在B樹中，是以每條記錄都必須有一個唯一鍵。索引就是一張索引鍵與自增計數的映射表。當使用索引查詢記錄時，就相當于索引左聯合到資料記錄的表，條件為自增計數。總結來說，就是sqlite資料庫檔案裡儲存了多于一棵的B樹，第一棵B樹入口位于第一頁面，其它B樹的根必須通過第一棵B樹才能索引出來。
首先我們來看sqlite資料庫的總起資訊，也就是入口，位于第一頁面的開頭100位元組。
<img dbheader/>
可看到資料庫檔案開頭作了檔案類型标記“SQLite format 3\0”。目前資料庫以4KB尺寸來劃分頁面。資料庫檔案迄今被修改過461次，并且沒有空閑頁面。目前預設編碼方式為UTF-8。
接着就是第一個頁面作為B樹根的頁面資訊。
頁面資訊首先定義了目前頁面的類型，包含自增計數的非葉子結點并且有左孩子記錄。跟着就是目前頁面的狀态資訊，有1條記錄（單元），下一條插入的記錄（單元）的位置，結點的右孩子位于索引号為141的頁面（也就是第141個頁面）。當“number of cells on this page”和“first byte of the cell content area”越靠近，表示頁面内空閑空間越小。下面是對第一個頁面的入口B樹跟蹤。
第一行是目前頁面号為1, 類型是結點，右孩子在141号頁面，左孩子分别是139号頁面以23為key，隻有一個左孩子。
第二行是目前頁面号為139，類型是葉子，存放23條記錄。根據上下文知，是1号頁面的左孩子，并且存放小于等于key23的記錄，一共有23條記錄。
第三行是目前頁面号為141，類型是葉子，存放23條記錄。根據上下文知，是1号頁面的右孩子，是剛剛分裂成139和141兩個葉子，各存放一半數量的記錄。下面是第139号頁面，作為左孩子葉子頁面的跟蹤。
綠色框框是我們關心的資訊，描述了記錄在目前頁面的指針，記錄長度以及唯一鍵值（自增計數）。根據上下文139号頁面，這個B樹葉子存放自增計數小于等于23的記錄一共23條。
藍色框框是記錄單元裡的資料，是表的根頁面指針，在目前情景中，2,4,5,11和12都是某張表的根頁面索引号。下面我們對2号頁面為根的表進行跟蹤。
分别對2,4以及12号頁面為根三張表的B樹存儲組織，藍色框框葉子記錄總數與使用sqlite查詢的結果一緻。最後我們跟蹤一下空閑頁面，在本篇中使用的資料庫不包含空閑頁面，現在我們truncate一個表以産生一些空閑頁面，就拿上面舉例的12号頁面為根的表，這張表包含了1個根結點和6個葉子，其中5個葉子是左孩子，1個葉子是右孩子。
留意綠色框框，檔案修改次數被加1，剛剛有一個表被清空了。
藍色框框顯示了本次清空動作，産生了8個空閑頁面，而連結這些頁面的第一節點在第60号頁面。
紅色框框顯示了放在60号頁面節點的頁面索引号，對照上面12号頁面為根的表跟蹤，可以看到被清空的表的存儲B樹所使用到的頁面都被連結到空閑連結清單。介紹完以頁面為機關存儲大架構後，我們再來看頁面内的存儲。
頁面分為三部分，頁面資訊頭，單元（cell）指針（索引）數組，以及資料（記錄）單元。索引和資料分别放于頁面的一頭一尾，中間為未使用空間，各自向中間擷取配置設定空間來應對增長。當某一單元被删除，它的空間會被回收鍊入到頁面内空閑塊連結清單。當空閑塊再次被使用時可能規格不一緻，進而會産生碎片（零碎位元組），這些碎片将不能被重用，因而必須記錄下來，供往後頁面零碎程式評級用。我猜過于零碎的頁面可能會在合适的時機進行重整。也就是單元區域周遊所有單元，必須依賴頁面内索引數組。隻有索引數組内索引到的單元才是有效的。對于未曾發生過單元回收重用的頁面，單元區域可以直接周遊，但發生過單元回收後則不可，必須依賴頁面内索引。