sqlite3.36版本 btree实现（五）- Btree的实现

2022-02-01
15分钟阅读时长
存储 , 存储引擎
sqlite3.36版本 btree实现

《sqlite3.36版本 btree实现》系列文章：

概述

前面的内容里，详细介绍了页面管理器部分的内容，回顾一下页面管理器和Btree模块的分工：

  • 页面管理器：提供页面级别的物理管理，如缓存、读取、写入、页面备份等。
  • Btree：根据btree数据结构提供页面在逻辑上的组织，以及单个页面内的划分。

还记得最开始，研究生产级别btree实现时的几个疑问：

  • 数据库教科书中，演示btree算法时，使用的都是定长的简单数据。实际应用中，存储的数据都是变长的，那么应该如何存储变长的数据呢？
  • 如果一行数据的大小，超过了一个物理页面的大小，又该如何处理？
  • 删除一行数据之后，它留下的空间如何回收利用？而回收利用时，不可避免的会出现碎片的问题，比如原先10字节的数据被回收，用来存储9字节的数据，多出来的1字节数据就被浪费了，碎片问题应该如何解决？

这些问题，都与“一个物理页面内数据如何组织”这个核心问题息息相关，带着这些问题展开btree实现的讨论。

在下文中，不会讨论btree算法的细节，这部分不熟悉的，可以回看之前的文章或者教科书：

物理页面的数据组织

数据表的逻辑组织和页面类型

在展开具体的格式讨论之前，有必要先了解一下数据库文件的大体结构，已经不同的页面类型。

sqlite中所谓的数据库文件是单一文件，按照物理页面（2的次方）的大小来划分为多个页面。其中，每个表在数据库文件中是一棵btree的结构来组织，而不同类型的btree还区分了不同的页面。

比如下图中，将平面的数据库文件，按照颜色划分成存储两个表的btree：

数据库文件的物理页面组织和逻辑页面结构

在上图中：

  • 上半部分表示，在物理的组织上，一个数据库文件以一个物理页面为基本单位来存储。
  • 下半部分表示，在逻辑的组织上，不同的表都有自己的btree树形结构，这是物理页面在逻辑上的组织方式。

因为每个表都有自己的btree树形结构，如果每个表都有一个对应的根页面编号，比如图中的两个表，对应的树形结构中，根节点所在的页面分别是1和2。

接着来看不同的页面类型，以及存储上的差异。

以一个例子来说明，创建以下的数据库，插入数据，以及索引：

// 创建数据库COMPANY
CREATE TABLE COMPANY(
   ID             INT      NOT NULL,
   NAME           TEXT    NOT NULL,
   AGE            INT     NOT NULL,
   ADDRESS        CHAR(50),
   SALARY         REAL
);

// 创建索引
CREATE INDEX id_index ON COMPANY (id);

// 插入2条数据
INSERT INTO COMPANY (ID,NAME,AGE,ADDRESS,SALARY) VALUES (1, 'Paul', 32, 'California', 20000.00 );
INSERT INTO COMPANY (ID,NAME,AGE,ADDRESS,SALARY)
VALUES (2, 'Allen', 25, 'Texas', 15000.00 );

// 查询数据
sqlite> select * from COMPANY;
1|Paul|32|California|20000.0
2|Allen|25|Texas|15000.0

// 查询rowid和数据
sqlite> select rowid,* from COMPANY;
1|1|Paul|32|California|20000.0
2|2|Allen|25|Texas|15000.0

在上面的流程里：

  • 创建一个表COMPANY，注意这个表在最开始是没有任何索引的。
  • 接下来，以字段id来创建一个索引，插入2条数据。
  • 接下来，分别作了两次查询：一次查询全量的数据，第二次出现了一个在上面没有出现的一个字段rowid。

到了这里，问题就来了，rowid是什么？为什么会自动存在这个字段，起了什么作用？

rowid是sqlite中的一个隐藏列：整数类型，自增。

为什么需要这个隐藏列？有以下两个原因：

  • 以rowid为键，来存储一行数据的全量数据。
  • 有了rowid做为一行数据的键，其它索引存储的值就可以是这行数据的rowid。
  • 即：rowid在sqlite中是做为聚簇索引（cluster index）出现的。

以上面为例，在sqlite的btree中大体就是这样的：

数据库文件的rowid全量数据表和索引表

在上图中存在两个表：

  • 以rowid为键的全量数据表，在sqlite中存储这类型数据的btree被称为“table tree”。
  • 存储id索引的索引表，这类btree被称为“index tree”，因此存储的是索引数据。这个表的键是id，而值是rowid，这样根据id索引来查询数据时，其实就是两步：
    • 首先，根据id找到对应的rowid。
    • 再根据rowid到全量数据表里查询具体的数据。

从上面的这个例子里也可以看出，“逻辑意义”上的一个数据表，与实际存储时在btree中的表并不是一一对应的，由于索引表的存在，可能是一对多的关系。

有了前面的对rowid以及索引表、全量数据表的理解，就可以展开讨论不同的页面类型了。

sqlite中分为几类页面：

  • 以整数为键的页面：这类页面是以b+tree模式来组织的。即：

    • 内部节点都只有键。
    • 数据部分都存储在叶子页面。

    显然，全量数据表的页面就是这类页面，即全量数据表更准确的是b+tree结构。

  • 其他类型的页面：其他表都是以整数为值，这类型的页面都是btree类型，即内部节点、叶子节点都一样存储着键和值。

为了表示这些页面，有如下几种页面标志位：

/*
** Page type flags.  An ORed combination of these flags appear as the
** first byte of on-disk image of every BTree page.
*/
#define PTF_INTKEY    0x01
#define PTF_ZERODATA  0x02
#define PTF_LEAFDATA  0x04
#define PTF_LEAF      0x08
  • PTF_INTKEY（1）：表示key为int类型数据，一般是rowid，即前面的全量数据表。
  • PTF_ZERODATA（2）：表示这是索引表的页面。
  • PTF_LEAFDATA（4）：数据存储在叶子节点，这个标志位要和PTF_INTKEY一起作用。即：key为int类型数据的时候，有两种页面：一种只存储int类型的key，一种只存储数据。
  • PTF_LEAF（8）：仅用于表示该页面是否叶子页面。

页面标志位只可能是以下几种组合，其余组合都认为文件损坏了：

  • PTF_ZERODATA：表示这是索引表的内部页面。
  • PTF_ZERODATA | PTF_LEAF：表示这是索引表的叶子页面。
  • PTF_LEAFDATA | PTF_INTKEY：表示数据表的内部页面。
  • PTF_LEAFDATA | PTF_INTKEY | PTF_LEAF：表示数据表的叶子页面。

说明，其实以上就是分成了两组PTF_ZERODATA和PTF_LEAFDATA | PTF_INTKEY与PTF_LEAF的组合（见函数decodeFlags）：

  • PTF_ZERODATA：肯定没有数据（hasData一定为0）。
  • PTF_LEAFDATA | PTF_INTKEY：是否有数据，取决于是否有PTF_LEAF标志位（hasData取决于leaf ）。

物理页面的大体划分

来看看sqlite代码中btreeInt.h文件里对btree一个物理页面内数据组织的注释：

** Each btree pages is divided into three sections:  The header, the
** cell pointer array, and the cell content area.  Page 1 also has a 100-byte
** file header that occurs before the page header.
**
**      |----------------|
**      | 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.
**      |----------------|

页面内数组的组织

按照这里的说法，一个物理页面在btree中划分为以下几部分：

  • 文件头（file header）：100字节，但是只有第一个页面才会存在文件头。
  • 页面头（page header）：每个页面都会有页面头，根据页面的类型区分，如果是叶子页面就是8字节大小，如果是内部节点就是12字节大小。
  • 存储cell指针的数组（cell pointer array）：每个cell指针大小为2字节，按照存储的cell地址大小排序，这个数组不定长，因此是从低位往高位地址增长的。至于什么是cell，后面展开说。
  • cell内容空间（cell content area）：存储cell数据的空间，从一个物理页面的最高位置往低位增长。
  • 未分配空间（unallocated space）：上面两部分内容，一部分从从高往低增长，另一部分反之，而未分配空间就夹在这两者中间。

有了这里大体的划分，我们来展开看看具体的内容。

file header（文件头）

其中，file header部分只有第一页才有，固定长度100字节，存储整个数据库文件的元信息。

页面1是一个特殊的页面，其前100个字节是整个数据库的header部分，内容如下：

**   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
**     36       4     Number of freelist pages in the file
**     40      60     15 4-byte meta values passed to higher layers
**
** All of the integer values are big-endian (most significant byte first).

逐个解析这个header里的内容：

  • 0-16字节：magic string。
  • 16-18字节：页面大小，不能小于512或者大于32768，同时需要是8位对齐。
  • 18-19：大于1表示数据库只读。
  • 19-20：必须大于1。
  • 20-21：每个页面最后无用空间的大小。即可用空间=页面大小-无用空间，这部分空间不得小于500字节。
  • 21-23：写死了必须是"\100\040\040"。其中：
    • 21：Max embedded payload fraction，写死了是64。
    • 22：Min embedded payload fraction，写死了是32。
    • 23：Min leaf payload fraction
  • 24-28：File change counter
  • 32-36：第一个空闲页面编号。
  • 36-40：空闲页面数量。

page header（页面头）

除了第一页以外，其他情况下页面头在页面的开始位置（即偏移量为0开始），第一页从偏移量100开始。

其内容如下：

** The page headers looks like this:
**
**   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.

分析如下：

  • 0-1：表示页面类型的标志位，至于页面的类型上面已经有阐述。
  • 1-2：首个空闲block在页面内的偏移量。
  • 3-5：cell数组的大小。
  • 5-7：cell content的第一个字节。
  • 7-8：碎片空间总大小（注意不是空闲空间），sqlite中将小于4字节的空闲空间称为碎片空间，一旦碎片空间大小累积到一定程度，就需要进行碎片整理，这在下面展开说明。
  • 8-12（叶子页面没有这部分内容）：右子树页面的页面编号。

重点解释其中的几部分：

cell数组

cell数组中，每个元素大小为2字节，指向对应cell内容在页面中的位置。由于一个页面不会超过65535字节大小，所以2字节是足够表示这个页面内的偏移量的。

另外，cell数组中的元素，是按照key的大小有小到大按顺序排列的，这样才能方便查找。

有了对物理页面内数据组织的了解，可以看到：

  • 查找数据时，首先按照按照btree的算法，定位到数据所在的页面。
  • 再在页面内的cell数组中，根据key大小进行二分查找。

查找key的流程

空闲空间链表

所谓的“空闲空间”，就是夹在cell数组和cell内容数组中间的部分，最开始是一大整块的空间。

但是随着写入操作进行，比如一行数据被删除之后，回收的空间就会放到空闲空间链表上。空闲空间链表就是用来组织现在空闲空间的数据的，其中的每个元素为4字节，其内容是：

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

其中：

  • 0-2字节：下一块空闲空间链表的页内偏移量。
  • 3-4字节：当前这块空闲空间的大小。

另外，空闲空间链表是按照起始地址递增进行排序的，这样才能在从空闲空间中分配空间时高效查找最合适的空间。

空闲区链表

碎片空间总大小

如前所述，表示一个空闲空间至少需要4字节，因此如果一个空闲空间不足4字节时，显然是不划算的。所以，将所有空闲的、且小于4字节的空间，称为“碎片空间”，其总大小记录在头的7-8字节处，当这个值超过某个阈值时将进行页面碎片空间整理。

页面标志位

见前面页面类型部分的解释。

cell的结构

一个cell，就是存储一行数据的单位，由于要考虑一行数据有不同的长度，因此cell里面就要有应对变长数据的准备，来看cell的结构。

** The content of a cell looks like this:
**
**    SIZE    DESCRIPTION
**      4     Page number of the left child. Omitted if leaf flag is set.
**     var    Number of bytes of data. Omitted if the zerodata flag is set.
**     var    Number of bytes of key. Or the key itself if intkey flag is set.
**      *     Payload
**      4     First page of the overflow chain.  Omitted if no overflow

逐个解释：

  • 0-4：左子树的页面编号（如果是叶子页面这部分没有）。
  • 变长：数据部分的大小。
  • 变长：key部分的大小。但是如果这个页面是intkey页面，这部分直接用来保存int类型的key，即这种情况下int类型key不会出现在后面的payload部分，而是直接存在在key部分大小的位置。
  • 变长：payload。
  • 4字节：如果存在overflow页面的话，这里存储第一个overflow页面的页面编号，何为溢出页面下面再做解释。

因为叶子页面没有左子树，所以不需要存储左子树页面编号，因为如果是叶子页面的话，页面头的大小就只有8字节，反之如果是内部节点就需要12字节。

cell结构

其中，根据表类型的不同，key、data、payload部分的大小关系如下：

  • int类型的key（即table tree）：nPayload 与 nData恒相等，因为int类型的表，由于key就是一个整型数，所以不浪费空间存储这个整型数的值，而是直接放在key大小部分。区分是否有数据，有以下两种情况：

    • 无数据（即内部节点）：因为nPayload 与 nData恒相等，所以这时候nData = nPayload = 0。（分析这类型页面cell数据的入口函数是btreeParseCellPtrNoPayload）
    • 有数据（即叶子页面）：nData = nPayload = 变长数据的大小。（分析这类型页面cell数据的入口函数是btreeParseCellPtr）

  • 非int类型的表（即index tree）：

    这种类型的页面，肯定没有数据部分，只有key部分，所以这时候nPayload = nKey。（分析这类型页面cell数据的入口函数是btreeParseCellPtrIndex）

为什么非int类型的表，会没有数据部分？这是因为，完整的数据，都以rowid为key的情况，存储在了int类型的表中；而非int类型的表，只要存储这个表的键值整数即可。

而溢出页面的结构如下：

** Overflow pages form a linked list.  Each page except the last is completely
** filled with data (pagesize - 4 bytes).  The last page can have as little
** as 1 byte of data.
**
**    SIZE    DESCRIPTION
**      4     Page number of next overflow page
**      *     Data

即：对于存储溢出数据的页面而言，头部的4字节存储下一个溢出页面的页面编号（如果还有溢出页面的话），而剩余则存储数据。

结合起来，一个存储了溢出数据（即当前页面不足以存储这个cell的所有数据）的结构大体是：

有溢出页面的cell结构

空间利用和碎片整理

了解了一个物理页面内部的结构，接下来看碎片整理的实现。

虽然有空闲链表用于组织已被回收的空间，但是随着分配的进行，还是会产生各种大小的碎片。可能会出现这样的情况：虽然空闲空间的总大小够用，但是由于散落在各块碎片空间里，以至于无法分配成功。

这种情况下，就需要碎片整理流程，这个流程做完之后，要达到这样的目的：空闲链表上只有一块大的整空间。

来看看碎片整理的触发条件和过程。

碎片整理的触发条件

分配空间的入口函数是allocateSpace，其入参nByte表示需要从页面中分配大小为nByte的空间返回。进入这个函数时，都会首先判断：页面剩余的空闲空间是足够满足nByte的，但是即便如此也可能由于碎片太多导致不能再分配了。

这个函数的大体逻辑如下：

  • 尝试在空闲链表中找到合适的空间分配。（函数pageFindSlot）
  • 如果上面分配不成功，且当前甚至在cell指针数组中都分配不出2字节来存储新分配出来的cell地址，那么就需要进行碎片整理。（函数defragmentPage）
  • 碎片整理结束之后，划出足够的空间（2字节的cell指针+对应大小的cell大小）返回。

所以，分别来看上面两个条件。

首先来看什么情况下在空闲链表中分配不出适合的空间，入口函数是pageFindSlot，有两种可能：

  • 因为空闲链表是按照空闲块大小从小到大排列的，因此首先按序找到第一块满足nByte大小的空闲块，假设这个空闲块划掉nByte大小之后为x，若这个x小于4字节那么认为是一个碎片，假如当前的碎片累加起来超过60字节了，那么认为碎片过多，这时候即便能满足分配也不能继续分配。

    至于为什么小于4字节认为是碎片，以及为什么碎片总大小超过60字节就认为碎片过多，可能是作者的经验值。

  • 第二种情况，就是遍历了整个链表都没有找到满足nByte大小的空间。

除此之外，如果当前cell数组结束位置，距离cell内容区域不足2字节，即无法再分配一个cell指针出来，这时候就需要进行碎片整理了。

触发碎片整理的条件

总结一下触发碎片整理的条件：

  • 从空闲链表中分配空间失败。
  • 且，在cell指针数组以及cell内容区域的空间，已经不足2字节，即连对应的cell指针都无法分配出来。

碎片整理的流程

碎片整理的流程，其实相对简单，简而言之：

  • 把各块cell内容，全部整理到从页面结尾开始的空间。
  • 这样，就能把散落在各处的空闲空间重新合并在一起形成一大块的空闲空间了。

碎片整理前后

碎片整理的整体流程在函数defragmentPage中，读者可以自行阅读。

总结

  • sqlite中分为table tree（存储全量数据）和index tree（存储任意索引到rowid的对应关系），table tree本质是一棵b+tree，而index tree是一棵btree。
  • 在物理页面内部，有根据key大小排序的cell数组，查找数据时分为两步：
    • 首先根据btree算法定位到数据所在的物理页面。
    • 然后在该物理页面内部的cell数组中，二分查找定位key的位置。
  • 物理页面内的空闲空间使用链表维护起来，小于4字节的空闲空间被称为“碎片空间”，当碎片空间累计大小超过60字节时，就会进行碎片整理。

参考资料

#存储 #存储引擎 #sqlite #btree
下一页 周刊（第3期）：一个前游戏开发者眼中的游戏后端技术

相关

sqlite3.36版本 btree实现（四）- WAL的实现
sqlite3.36版本 btree实现（三）- journal文件备份机制
sqlite3.36版本 btree实现（二）- 并发控制框架
sqlite3.36版本 btree实现（一）- 管理页面缓存
sqlite3.36版本 btree实现（零）- 起步及概述
boltdb 1.3.0实现分析（四）