SQLite中的B-Tree完成细节深入深入分析

SQLite在储存在表面包车型客车数据库是以B-Tree来公司的。关于B-tree的内部意况,仿效
**
** Donald E. Knuth, THE ART OF COMPUTER PROGRAMMING, Volume 3:
** “Sorting And Searching”, pages 473-480. Addison-Wesley
** Publishing Company, Reading, Massachusetts.
**

中央思维是文件包蕴的每一页都不外乎N个数据库入口和N+1个针对子页的指针。文件分为超多页存款和储蓄。为啥那样干,因为内部存款和储蓄器分页管理机制闹得。外部存款和储蓄器中每种页正是B树的三个节点。

| Ptr(0) | Key(0) | Ptr(1) | Key(1) | … | Key(N-1) | Ptr(N) |

Ptr(0卡塔尔指向的页上的具有的key的值都低于Key(0卡塔尔。全体Ptr(1State of Qatar指向的页和子页的有所的key的值都大于Key(0卡塔尔(قطر‎,小于Key(1卡塔尔(قطر‎。全体Ptr(N卡塔尔(قطر‎指向的页和子页的key的值都大于Key(N-1State of Qatar,等等。

为了知道叁个特定的key,须要从磁盘上以O(long(M卡塔尔(قطر‎State of Qatar来读取,此中M是树的阶数。内部存款和储蓄器中找不到了,就发生缺页中断。
澳门新蒲京平台,首要是消除内部存款和储蓄器中找不到的标题。一方面换出来一些。一方面换进去一些。换进去的时候要找到他们再硬盘的哪位页面上啊。
(B树的长处正是相符于用块儿存款和储蓄的存款和储蓄设备上。)利用所以,能够知晓她们们在哪些页面上。

在SQLite的贯彻中,三个文本能够蕴涵1个或的过独立的BTree。每二个BTree由它的根页的目录来标志。全数入口的key和数量整合了卓有作用载荷(payload卡塔尔。数据库的生龙活虎页有一个定点的管用载荷总量。假如负荷大于了事情发生以前设定的值,那么余下的字节就能够被储存在溢出页上。二个进口的实用载荷再增多前向指针(the
preceding
pointer)构成了大器晚成格(cellState of Qatar。每风度翩翩页都有一个小尾部,包罗了Ptr(N卡塔尔指针和其它一些音信,举个例子key和数据的高低。

格式细节
五个文件分为了三个页。第生机勃勃页叫做页1,第二页叫做页2,一回类推。页的个数为0表示不曾页。页的尺寸能够从512

65536。每黄金年代页或许是一个btree页,或许是七个freelist页,可能是叁个溢出页。
首先页一定是二个btree页。第后生可畏页的这几天玖16个字节蕴涵了三个出奇的首部(文件头卡塔尔(قطر‎,它是其一文件的描述。
文件头的个数如下:
** OFFSET SIZE DESCRIPTION
** 0 16 Header string(首部字符串): “SQLite format 300”
** 16 2 Page size in bytes(页的字节数).
** 18 1 File format write version(文件写操作的本子)
** 19 1 File format read version (文件读操作的版本)
** 20 1 Bytes of unused space at the end of each
page(每意气风发页结尾未选用的字节)
** 21 1 Max embedded payload fraction(最大的放到有效载荷分片)
** 22 1 Min embedded payload fraction(最小的嵌入有效载荷分片)
** 23 1 Min leaf payload fraction(最小的页有效载荷分片)
** 24 4 File change counter (文件变化流速计)
** 28 4 Reserved for future use (保留字节)
** 32 4 First freelist page (第一个freelist页)
** 36 4 Number of freelist pages in the file
(本文件中freelist页的个数)
** 40 60 15 4-byte meta values passed to higher layers()
**
具备的整数都以多方面的。

历次纠正文件时,文件变化流速計都会扩张。那几个计数器能够让其它进度知道何时文件被更动了,他们的cache是不是供给清理。

最大嵌入有效载荷分片是生龙活虎页的全部可用空间,被标准B-tree(非叶数据)表的独门的二个所能使用的总数。值255意味100%。私下认可景况下,生机勃勃格(cell卡塔尔(قطر‎的最多量被约束为,至稀少4格能力填满黄金年代页。因而,默许的最大嵌入负荷分片是64。

倘诺后生可畏页的管事载荷大于了最大使得载荷,那么余下的数量将在被积累到溢出页。意气风发旦分配了三个溢出页,有十分的大希望会有数不清数量也被转移到这些溢出页,可是不会让格cell的大小小于最小嵌入有效载荷分片的。

最小页有效载荷分片与小小嵌入有效载荷分片肖似,但是它是行使于LEAFDATA
tree中的叶节点。三个LEAFDATA的最大实用载荷分片为100%(恐怕是值255),它实际不是再首部钦定。

BTree的每生龙活虎页被分成三有的:首部,格(cell)指针数组,和格cell的源委。页1还大概会在页首部有100字节的文件头。
**
** |—————-|
** | 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.
**
标记位定义了那个BTree页的格式。叶leaf标记意味着那黄金年代页未有子女children。zerodata0数据表示那少年老成页只含有key,十分的少;intkey标记意味着key是三个整数,何况是被积攒在格cell首部的key大小处,实际不是在使得载荷区域。

格cell指针数组从页首部开始。格cell指针数组包蕴0个或多余2个字节的数字,这几个数字代表格cell内容区域中的格cell内容从文件起首地方的偏移量。格cell指针式有序的。系统努力确认保障空闲空间位居最终二个格cell指针之后,那样能够保险新的格cell能够飞速的充裕,而不用重新收拾(defragment)那少年老成页。

格cell内容存款和储蓄在页的末段,且是向文件的前奏方向抓实。

在格cell内容区域中的未利用的半空中被访问到链表freeblocks上。每三个freeblock至稀少4个字节。第贰个freeblock的摇晃在页首部给出了。Freeblock是增序的。因为二个freeblock至罕见4个字节,全数在格cell源委区域的3个或是啊嘿与3个的未用空间不可能存在于freeblock链表上。那么些3个或个别3个的闲暇空间被称之为碎片。全数碎片的总个数被记录下来,存款和储蓄于页首部的偏移7的职位。

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

格cell是可变长度的。格cell被积存于页的末尾格cell内容区域。指向格cell的cell指针数组紧跟在页首部的背后。格cell不必是连连或然有序的,不过格cell指针是一连和平稳的。

格cell内容丰硕利用了可变长度整数。可变长度整数是从1到9个字节,各个字节的低7位被使用。整个整数由8位的字节组成,在那之中第叁个字节的第8位被清零。整数最关键的字节出现在首先个。可变长度整数通常十分的少于9个字节。作为生机勃勃种非常情状,第八个字节的富有8个字节都会被感觉是数据。那就同意了陆11位整数变编码为9个字节。
** 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公社网址(www.linuxidc.com卡塔尔国原著链接:

相关文章

发表评论

电子邮件地址不会被公开。 必填项已用*标注

*
*
Website