SQLite物理文件结构

Btree是为磁盘存储而优化了的一种树结构，其一般性说明可参考各类《数据结构》教材。根据实现方法的不同，Btree又分为很多类型。在SQLite中，存储表数据用的是B+tree，存储表索引用的是B-tree。由于历史原因，SQLite在3.0版以前只使用B-tree，从3.0版开始，才对表数据使用了B+tree。因此，在SQLite的官方文档中，有时B-tree表示存储表索引的B-tree，有时又是两种Btree的统称 ### SQLite物理文件结构详解 #### 一、概念介绍 ##### 1.1 Btree、B-tree和B+tree Btree是一种专为磁盘存储优化的树形数据结构，广泛应用于数据库系统中以提高数据存取效率。在不同的实现方式下，Btree衍生出了多种类型，其中最为人所知的是B-tree和B+tree。 - **B-tree**：这种树结构主要用于存储索引，它的特点是所有数据节点都包含在树中，每个节点都可以存储一个或多个键以及与之相关的数据或子节点的指针。B-tree的设计目的是为了最小化查找、插入和删除操作所需的磁盘I/O次数，这使得它非常适合用于数据库索引。 - **B+tree**：B+tree是在B-tree的基础上进一步优化的结果，主要用于存储表数据。与B-tree不同，B+tree的所有数据节点仅存在于叶子节点中，而非叶子节点仅用于导航。这意味着所有的数据节点都位于相同的深度，有利于提高数据访问速度，尤其是在范围查询时更为高效。 在SQLite的发展历程中，早期版本（3.0之前）仅使用B-tree，但从3.0版开始，为了优化表数据存储，引入了B+tree作为表数据的主要存储结构。这种变化反映出SQLite对性能和效率的持续追求。 ##### 1.2 auto-vacuum数据库 通常情况下，当数据库中的数据被删除后，数据库文件的大小并不会立即减少。相反，这些已删除的空间会被标记为空闲，等待后续的操作再次利用。然而，使用auto-vacuum机制的数据库会在删除操作完成后自动回收这些空闲空间，从而减少数据库文件的大小。虽然这种方式有助于节省磁盘空间，但它可能会增加数据库操作的时间开销，因此需要根据实际需求权衡使用。 ##### 1.3 数据库映像、数据库文件和日志文件 SQLite数据库的核心存储形式是单一的数据库文件，通常我们所说的“数据库映像”实际上是指这个文件的内容。但在某些情况下，例如正在进行事务处理时，数据库的实际状态会分布于数据库文件和一个临时的日志文件之间。日志文件用于记录事务期间的所有修改，确保即使在系统故障的情况下也能恢复到一致的状态。 #### 二、数据库存储结构 ##### 2.1 数据库头结构 数据库的第一个页(Page 1)总是被用作B-tree的根节点，并且其前100字节是专门用来描述数据库文件特性的“文件头”。文件头包含了创建数据库时设定的各种重要参数，例如数据库的版本信息、页大小、编码规则等。这些信息对于正确解析和使用数据库至关重要。 - **文件头结构**： - 偏移量0至15：固定的字符串"SQLite format 3"，表明文件格式为SQLite 3。 - 偏移量16：页大小，决定了每个页所包含的数据量。 - 偏移量18：文件格式版本（写），当前版本为1，大于1则表示文件为只读。 - 偏移量19：文件格式版本（读），同样，当前版本为1，大于1则拒绝打开。 - 偏移量20：页尾保留空间大小，默认为0。 - 偏移量21：内部节点最大单元使用空间比例，默认为64%（0x40）。 - 偏移量22：内部节点最小单元使用空间比例，默认为12.5%（0x20）。 - 偏移量23：叶节点最小单元使用空间比例，默认为12.5%（0x20）。 这些设置确保了SQLite能够高效地管理数据库中的数据。 ##### 2.2 sqlite_master表 `sqlite_master`是一个特殊的系统表，用于维护数据库中的所有表和索引信息。每个表或索引都有一个对应的根节点页（Root Page），这些根节点页的编号都存储在`sqlite_master`表中。通过查询这个表，可以获取数据库中所有表和索引的基本信息。 ##### 2.3 页结构 SQLite使用页作为基本的存储单元，每个页都是B-tree的一个节点。页结构可以大致分为以下几类： - **页结构总体概述**：页的基本结构包括页头、内部页和叶子页等部分。每个页的大小是由数据库头中的页大小字段决定的，常见的大小为1024字节。 - **页头结构分析**：页头包含了页的基本属性信息，如页类型、占用空间大小等。 - **表数据存储格式（B+Tree）** - **B+tree格式介绍**：B+tree是一种特殊的树形结构，用于存储表数据。 - **B+tree内部页格式分析**：内部页用于存储指向其他页的指针和相关的键值，帮助快速定位到特定的数据页。 - **B+tree叶子页格式分析**：叶子页是实际存放数据的地方，所有数据行都在叶子页中按顺序排列。 - **索引数据存储格式（B-Tree）** - **索引内部页**：类似于B+tree内部页，但主要存储索引键和指向数据页的指针。 - **索引叶子页**：存储索引键和与之关联的数据页的地址，用于快速查找数据。 #### 三、附录 ##### 3.1 可变长整数 在SQLite中，为了更有效地存储数据，采用了可变长整数编码的方式。这种方式允许根据实际数值的大小动态选择最短的字节数来表示整数，从而节省存储空间。 ##### 3.2 字段的数据类型和宽度说明 SQLite支持多种数据类型，包括整型、浮点型、文本、Blob等，每种数据类型的宽度和表示方式都有明确的规定。例如，整型数据可以使用不同位数来表示，而文本数据则使用UTF-8、UTF-16LE或UTF-16BE编码。 ##### 3.3 参考资料 - [SQLite 官方文档](https://www.sqlite.org/fileformat.html) - [数据结构与算法分析](https://www.amazon.com/Data-Structures-Algorithms-Analysis-Third/dp/032144146X) 以上是对SQLite物理文件结构的详细介绍，包括概念介绍、数据库存储结构及附录等内容，旨在深入探讨SQLite是如何组织和管理其数据的。通过对这些内容的理解，可以更好地掌握SQLite的工作原理和优化策略。