小说网,古风

主頁(yè) > 知識(shí)庫(kù) > SQLite中的B-Tree實(shí)現(xiàn)細(xì)節(jié)分析

SQLite中的B-Tree實(shí)現(xiàn)細(xì)節(jié)分析

SQLite在存儲(chǔ)在外部的數(shù)據(jù)庫(kù)是以B-Tree來(lái)組織的。關(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.
**
基本思想是文件包含的每一頁(yè)都包括N個(gè)數(shù)據(jù)庫(kù)入口和N+1個(gè)指向子頁(yè)的指針。文件分成很多頁(yè)存儲(chǔ)。為什么這么干，因?yàn)閮?nèi)存分頁(yè)管理機(jī)制鬧得。外存中每個(gè)頁(yè)就是B樹(shù)的一個(gè)節(jié)點(diǎn)。
----------------------------------------------------------------
| Ptr(0) | Key(0) | Ptr(1) | Key(1) | ... | Key(N-1) | Ptr(N) |
----------------------------------------------------------------
Ptr(0)指向的頁(yè)上的所有的key的值都小于Key(0)。所有Ptr(1)指向的頁(yè)和子頁(yè)的所有的key的值都大于Key(0)，小于Key(1)。所有Ptr(N)指向的頁(yè)和子頁(yè)的key的值都大于Key(N-1)，等等。

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

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

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

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

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

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

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

BTree的每一頁(yè)被分為三部分：首部，格（cell）指針數(shù)組，和格cell的內(nèi)容。頁(yè)1還會(huì)在頁(yè)首部有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.
** |----------------|
**
頁(yè)首部如下圖所示：
**
** 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)志位定義了這個(gè)BTree頁(yè)的格式。葉leaf標(biāo)志意味著這一頁(yè)沒(méi)有孩子children。zerodata0數(shù)據(jù)表示這一頁(yè)只含有key，沒(méi)有數(shù)據(jù)；intkey標(biāo)志意味著key是一個(gè)整數(shù)，而且是被存儲(chǔ)在格cell首部的key大小處，而不是在有效負(fù)荷區(qū)域。

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

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

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

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

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

格cell內(nèi)容充分利用了可變長(zhǎng)度整數(shù)?？勺冮L(zhǎng)度整數(shù)是從1到9個(gè)字節(jié)，每個(gè)字節(jié)的低7位被使用。整個(gè)整數(shù)由8位的字節(jié)組成，其中第一個(gè)字節(jié)的第8位被清零。整數(shù)最重要的字節(jié)出現(xiàn)在第一個(gè)。可變長(zhǎng)度整數(shù)一般不多于9個(gè)字節(jié)。作為一種特殊情況，第九個(gè)字節(jié)的所有8個(gè)字節(jié)都會(huì)被認(rèn)為是數(shù)據(jù)。這就允許了64位整數(shù)變編碼為9個(gè)字節(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
本篇文章來(lái)源于 Linux公社網(wǎng)站(www.linuxidc.com) 原文鏈接：http://www.linuxidc.com/Linux/2012-11/75009.htm

您可能感興趣的文章:

B-Tree的性質(zhì)介紹
MySQL Hash索引和B-Tree索引的區(qū)別
bitmap 索引和 B-tree 索引在使用中如何選擇
B-樹(shù)的插入過(guò)程介紹
基于B-樹(shù)和B+樹(shù)的使用：數(shù)據(jù)搜索和數(shù)據(jù)庫(kù)索引的詳細(xì)介紹
淺談MySQL的B樹(shù)索引與索引優(yōu)化小結(jié)
完整B樹(shù)算法Java實(shí)現(xiàn)代碼
c語(yǔ)言B樹(shù)深入理解
B-樹(shù)的刪除過(guò)程介紹

標(biāo)簽：葫蘆島招商鶴崗常德石嘴山保定昆明沈陽(yáng)

巨人網(wǎng)絡(luò)通訊聲明：本文標(biāo)題《SQLite中的B-Tree實(shí)現(xiàn)細(xì)節(jié)分析》，本文關(guān)鍵詞 SQLite,中的,B-Tree,實(shí)現(xiàn),細(xì)節(jié),；如發(fā)現(xiàn)本文內(nèi)容存在版權(quán)問(wèn)題，煩請(qǐng)?zhí)峁┫嚓P(guān)信息告之我們，我們將及時(shí)溝通與處理。本站內(nèi)容系統(tǒng)采集于網(wǎng)絡(luò)，涉及言論、版權(quán)與本站無(wú)關(guān)。

濮阳杆衣贸易有限公司

SQLite中的B-Tree實(shí)現(xiàn)細(xì)節(jié)分析