SQLite在存儲在外部的數(shù)據(jù)庫是以B-Tree來組織的。關(guān)于B-tree的細(xì)節(jié)，參考
**
** Donald E. Knuth, THE ART OF COMPUTER PROGRAMMING, Volume 3:
** "Sorting And Searching", pages 473-480. Addison-Wesley
** Publishing Company, Reading, Massachusetts.
**
基本思想是文件包含的每一頁都包括N個數(shù)據(jù)庫入口和N+1個指向子頁的指針。文件分成很多頁存儲。為什么這么干，因?yàn)閮?nèi)存分頁管理機(jī)制鬧得。外存中每個頁就是B樹的一個節(jié)點(diǎn)。
----------------------------------------------------------------
| Ptr(0) | Key(0) | Ptr(1) | Key(1) | ... | Key(N-1) | Ptr(N) |
----------------------------------------------------------------
Ptr(0)指向的頁上的所有的key的值都小于Key(0)。所有Ptr(1)指向的頁和子頁的所有的key的值都大于Key(0)，小于Key(1)。所有Ptr(N)指向的頁和子頁的key的值都大于Key(N-1)，等等。

為了知道一個特定的key，需要從磁盤上以O(shè)(long(M))來讀取，其中M是樹的階數(shù)。內(nèi)存中找不到了，就發(fā)生缺頁中斷。
主要是解決內(nèi)存中找不到的問題。一方面換出來一些。一方面換進(jìn)去一些。換進(jìn)去的時候要找到他們再硬盤的哪個頁面上啊。
（B樹的優(yōu)點(diǎn)就是適合于用塊兒存儲的存儲設(shè)備上。）利用所以，可以知道他們們在哪個頁面上。

在SQLite的實(shí)現(xiàn)中，一個文件可以含有1個或的過獨(dú)立的BTree。每一個BTree由它的根頁的索引來標(biāo)識。所有入口的key和數(shù)據(jù)組成了有效負(fù)荷(payload)。數(shù)據(jù)庫的一頁有一個固定的有效負(fù)荷總量。如果負(fù)荷大于了預(yù)先設(shè)定的值，那么剩余的字節(jié)就會被存儲在溢出頁上。一個入口的有效負(fù)荷再加上前向指針（the preceding pointer）構(gòu)成了一格(cell)。每一頁都有一個小頭部，包含了Ptr(N)指針和其它一些信息，例如key和數(shù)據(jù)的大小。

格式細(xì)節(jié)
一個文件分成了多個頁。第一頁叫做頁1，第二頁叫做頁2，一次類推。頁的個數(shù)為0表示沒有頁。頁的大小可以從512 到 65536。每一頁或者是一個btree頁，或者是一個freelist頁，或者是一個溢出頁。
第一頁一定是一個btree頁。第一頁的前面100個字節(jié)包含了一個特殊的首部(文件頭)，它是這個文件的描述。
文件頭的個數(shù)如下：
** OFFSET SIZE DESCRIPTION
** 0 16 Header string（首部字符串）: "SQLite format 3\000"
** 16 2 Page size in bytes（頁的字節(jié)數(shù)）.
** 18 1 File format write version（文件寫操作的版本）
** 19 1 File format read version （文件讀操作的版本）
** 20 1 Bytes of unused space at the end of each page（每一頁結(jié)尾未使用的字節(jié)）
** 21 1 Max embedded payload fraction（最大的嵌入有效負(fù)荷分片）
** 22 1 Min embedded payload fraction（最小的嵌入有效負(fù)荷分片）
** 23 1 Min leaf payload fraction（最小的頁有效負(fù)荷分片）
** 24 4 File change counter （文件變化計數(shù)器）
** 28 4 Reserved for future use （保留字節(jié)）
** 32 4 First freelist page （第一個freelist頁）
** 36 4 Number of freelist pages in the file （本文件中freelist頁的個數(shù)）
** 40 60 15 4-byte meta values passed to higher layers（）
**
所有的整數(shù)都是大端的。

每次修改文件時，文件變化計數(shù)器都會增加。這個計數(shù)器可以讓其他進(jìn)程知道何時文件被修改了，他們的cache是否需要清理。

最大嵌入有效負(fù)荷分片是一頁的所有可用空間，被標(biāo)準(zhǔn)B-tree（非葉數(shù)據(jù)）表的單獨(dú)的一個所能使用的總量。值255代表100%。默認(rèn)情況下，一格(cell)的最大量被限制為，至少有4格才能填滿一頁。因此，默認(rèn)的最大嵌入負(fù)荷分片是64。

如果一頁的有效負(fù)荷大于了最大有效負(fù)荷，那么剩下的數(shù)據(jù)就要被存儲到溢出頁。一旦分配了一個溢出頁，有可能會有許多數(shù)據(jù)也被轉(zhuǎn)移到這個溢出頁，但是不會讓格cell的大小小于最小嵌入有效負(fù)荷分片的。

最小頁有效負(fù)荷分片與最小嵌入有效負(fù)荷分片類似，但是它是應(yīng)用于LEAFDATA tree中的葉節(jié)點(diǎn)。一個LEAFDATA的最大有效負(fù)荷分片為100%（或者是值255），它不用再首部指定。

BTree的每一頁被分為三部分：首部，格（cell）指針數(shù)組，和格cell的內(nèi)容。頁1還會在頁首部有100字節(jié)的文件頭。
**
** |----------------|
** | file header | 100 bytes. Page 1 only.
** |----------------|
** | page header | 8 bytes for leaves. 12 bytes for interior nodes
** |----------------|
** | cell pointer | | 2 bytes per cell. Sorted order.
** | array | | Grows downward
** | | v
** |----------------|
** | unallocated |
** | space |
** |----------------| ^ Grows upwards
** | cell content | | Arbitrary order interspersed with freeblocks.
** | area | | and free space fragments.
** |----------------|
**
頁首部如下圖所示：
**
** OFFSET SIZE DESCRIPTION
** 0 1 Flags. 1: intkey, 2: zerodata, 4: leafdata, 8: leaf
** 1 2 byte offset to the first freeblock
** 3 2 number of cells on this page
** 5 2 first byte of the cell content area
** 7 1 number of fragmented free bytes
** 8 4 Right child (the Ptr(N) value). Omitted on leaves.
**
標(biāo)志位定義了這個BTree頁的格式。葉leaf標(biāo)志意味著這一頁沒有孩子children。zerodata0數(shù)據(jù)表示這一頁只含有key，沒有數(shù)據(jù)；intkey標(biāo)志意味著key是一個整數(shù)，而且是被存儲在格cell首部的key大小處，而不是在有效負(fù)荷區(qū)域。

格cell指針數(shù)組從頁首部開始。格cell指針數(shù)組包含0個或多余2個字節(jié)的數(shù)字，這個數(shù)字代表格cell內(nèi)容區(qū)域中的格cell內(nèi)容從文件起始位置的偏移量。格cell指針式有序的。系統(tǒng)盡力保證空閑空間位于最后一個格cell指針之后，這樣可以保證新的格cell可以很快的添加，而不用重新整理（defragment）這一頁。

格cell內(nèi)容存儲在頁的末尾，且是向文件的起始方向增長。

在格cell內(nèi)容區(qū)域中的未使用的空間被收集到鏈表freeblocks上。每一個freeblock至少有4個字節(jié)。第一個freeblock的偏移在頁首部給出了。Freeblock是增序的。因?yàn)橐粋€freeblock至少有4個字節(jié)，所有在格cell內(nèi)容區(qū)域的3個或是哦啊與3個的未用空間不能存在于freeblock鏈表上。這些3個或少于3個的空閑空間被稱為碎片。所有碎片的總個數(shù)被記錄下來，存儲于頁首部的偏移7的位置。

** SIZE DESCRIPTION
** 2 Byte offset of the next freeblock
** 2 Bytes in this freeblock
**

格cell是可變長度的。格cell被存儲于頁的末尾格cell內(nèi)容區(qū)域。指向格cell的cell指針數(shù)組緊跟在頁首部的后面。格cell不必是連續(xù)或者有序的，但是格cell指針是連續(xù)和有序的。

格cell內(nèi)容充分利用了可變長度整數(shù)?？勺冮L度整數(shù)是從1到9個字節(jié)，每個字節(jié)的低7位被使用。整個整數(shù)由8位的字節(jié)組成，其中第一個字節(jié)的第8位被清零。整數(shù)最重要的字節(jié)出現(xiàn)在第一個?？勺冮L度整數(shù)一般不多于9個字節(jié)。作為一種特殊情況，第九個字節(jié)的所有8個字節(jié)都會被認(rèn)為是數(shù)據(jù)。這就允許了64位整數(shù)變編碼為9個字節(jié)。
** 0x00 becomes 0x00000000
** 0x7f becomes 0x0000007f
** 0x81 0x00 becomes 0x00000080
** 0x82 0x00 becomes 0x00000100
** 0x80 0x7f becomes 0x0000007f
** 0x8a 0x91 0xd1 0xac 0x78 becomes 0x12345678
** 0x81 0x81 0x81 0x81 0x01 becomes 0x10204081
本篇文章來源于 Linux公社網(wǎng)站(www.linuxidc.com) 原文鏈接：http://www.linuxidc.com/Linux/2012-11/75009.htm

最新評論