sqlite数据库|SQLite中B-Tree的细节分析

更新时间:2021-07-05    来源:php与数据库    手机版     字体:

【www.bbyears.com--php与数据库】

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树的一个节点。 word-spacing: 0px; -webkit-text-stroke-width: 0px;"/>---------------------------------------------------------------- word-spacing: 0px; -webkit-text-stroke-width: 0px;"/>| 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(long(M))来读取,其中M是树的阶数。内存中找不到了,就发生缺页中断。 
主要是解决内存中找不到的问题。一方面换出来一些。一方面换进去一些。换进去的时候要找到他们再硬盘的哪个页面上啊。 
(B树的优点就是适合于用块儿存储的存储设备上。)利用所以,可以知道他们们在哪个页面上。 
在SQLite的实现中,一个文件可以含有1个或的过独立的BTree。每一个BTree由它的根页的索引来标识。所有入口的key和数据组成了有效负荷(payload)。数据库的一页有一个固定的有效负荷总量。如果负荷大于了预先设定的值,那么剩余的字节就会被存储在溢出页上。一个入口的有效负荷再加上前向指针(the preceding pointer)构成了一格(cell)。每一页都有一个小头部,包含了Ptr(N)指针和其它一些信息,例如key和数据的大小。 
格式细节 
一个文件分成了多个页。第一页叫做页1,第二页叫做页2,一次类推。页的个数为0表示没有页。页的大小可以从512 到 65536。每一页或者是一个btree页,或者是一个freelist页,或者是一个溢出页。 
第一页一定是一个btree页。第一页的前面100个字节包含了一个特殊的首部(文件头),它是这个文件的描述。 
文件头的个数如下: 
** OFFSET SIZE DESCRIPTION 
** 0 16 Header string(首部字符串): "SQLite format 3\000" 
** 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)这一页。 

本文来源:http://www.bbyears.com/jiaocheng/127966.html