天天看點

sqlite3存儲分析

sqlite3存儲格式

本篇介紹sqlite3資料庫檔案的存儲格式。

通過閱讀源讀源代碼可以知道sqlite的設計思想。

一個sqlite資料庫檔案對應着一個資料庫。sqlite将資料庫檔案劃分大小一緻的存儲(以區分記憶體)頁面,并通過一系列資料結構将它們組織起來。

sqlite組織頁面的資料結構主要有B樹和二維連結清單。每一個頁面要麼是B樹的葉子或結點,要麼是二維連結清單的一個節點。用作B樹的頁面都有8或12位元組的頁面資訊頭,特别地第一個頁面除了是表的根結點是資料庫檔案的根,是以它首先包含100位元組的是庫資訊,然後才是作為一個是B樹的根結點。另一方面閑置的頁面沒有頁面頭,它的鍊頭是在第一個頁面的庫資訊頭。二維連結清單的第一維由單向連結清單實作,第二維由數組實作。用作第一維節點的頁面也是一個空閑頁面,被統計在庫資訊頭。

sqlite3存儲分析

資料庫層面的表和索引,在底層存儲格式中用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樹根的頁面資訊。

sqlite3存儲分析

頁面資訊首先定義了目前頁面的類型,包含自增計數的非葉子結點并且有左孩子記錄。跟着就是目前頁面的狀态資訊,有1條記錄(單元),下一條插入的記錄(單元)的位置,結點的右孩子位于索引号為141的頁面(也就是第141個頁面)。當“number of cells on this page”和“first byte of the cell content area”越靠近,表示頁面内空閑空間越小。下面是對第一個頁面的入口B樹跟蹤。

sqlite3存儲分析

第一行是目前頁面号為1, 類型是結點,右孩子在141号頁面,左孩子分别是139号頁面以23為key,隻有一個左孩子。

第二行是目前頁面号為139,類型是葉子,存放23條記錄。根據上下文知,是1号頁面的左孩子,并且存放小于等于key23的記錄,一共有23條記錄。

第三行是目前頁面号為141,類型是葉子,存放23條記錄。根據上下文知,是1号頁面的右孩子,是剛剛分裂成139和141兩個葉子,各存放一半數量的記錄。下面是第139号頁面,作為左孩子葉子頁面的跟蹤。

sqlite3存儲分析

綠色框框是我們關心的資訊,描述了記錄在目前頁面的指針,記錄長度以及唯一鍵值(自增計數)。根據上下文139号頁面,這個B樹葉子存放自增計數小于等于23的記錄一共23條。

藍色框框是記錄單元裡的資料,是表的根頁面指針,在目前情景中,2,4,5,11和12都是某張表的根頁面索引号。下面我們對2号頁面為根的表進行跟蹤。

sqlite3存儲分析

分别對2,4以及12号頁面為根三張表的B樹存儲組織,藍色框框葉子記錄總數與使用sqlite查詢的結果一緻。最後我們跟蹤一下空閑頁面,在本篇中使用的資料庫不包含空閑頁面,現在我們truncate一個表以産生一些空閑頁面,就拿上面舉例的12号頁面為根的表,這張表包含了1個根結點和6個葉子,其中5個葉子是左孩子,1個葉子是右孩子。

sqlite3存儲分析

留意綠色框框,檔案修改次數被加1,剛剛有一個表被清空了。

藍色框框顯示了本次清空動作,産生了8個空閑頁面,而連結這些頁面的第一節點在第60号頁面。

紅色框框顯示了放在60号頁面節點的頁面索引号,對照上面12号頁面為根的表跟蹤,可以看到被清空的表的存儲B樹所使用到的頁面都被連結到空閑連結清單。介紹完以頁面為機關存儲大架構後,我們再來看頁面内的存儲。

頁面分為三部分,頁面資訊頭,單元(cell)指針(索引)數組,以及資料(記錄)單元。索引和資料分别放于頁面的一頭一尾,中間為未使用空間,各自向中間擷取配置設定空間來應對增長。當某一單元被删除,它的空間會被回收鍊入到頁面内空閑塊連結清單。當空閑塊再次被使用時可能規格不一緻,進而會産生碎片(零碎位元組),這些碎片将不能被重用,因而必須記錄下來,供往後頁面零碎程式評級用。我猜過于零碎的頁面可能會在合适的時機進行重整。也就是單元區域周遊所有單元,必須依賴頁面内索引數組。隻有索引數組内索引到的單元才是有效的。對于未曾發生過單元回收重用的頁面,單元區域可以直接周遊,但發生過單元回收後則不可,必須依賴頁面内索引。