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(1)指向的页和子页的所有的key的值都大于Key(0)，小于Key(1)。所有Ptr(N)指向的页和子页的key的值都大于Key(N-1)，等等。
为了知道一个特定的key，需要从磁盘上以O(long(M))来读取，其中M是树的阶数。内存中找不到了，就发生缺页中断。
**
** 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(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）这一页。 格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个字节都会被认为是数据。这就允许了64位整数变编码为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
原文链接：https://www.f2er.com/sqlite/201616.html在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）这一页。 格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个字节都会被认为是数据。这就允许了64位整数变编码为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
