SQLITE文件分析

SQLite文件分析作者:饶珺1前言在移动终端APP开发中，数据存储的性能是影响APP整体性能的重要因素之一，当今主流手机操作系统：IOS、Android、WindowsPhone等平台最常使用的数据库是SQLite，研究SQLite对于深度优化移动APP数据存储性能会比较有帮助。本文重点介绍SQLite主数据文件的操作原理，文中没有过多介绍具体字节级的含义，而较多使用了图例来方便大家理解。本文没有讨论SQLite日志文件等临时文件，日志文件主要用于保障主数据文件的完整性。1.1预备知识(1)Btree，B-tree，B+tree文中涉及到的最重要的数据结构是B树，SQLite文件大体就是许多棵B树的集合。每一张数据表、表的每一个索引都是以B树的形式存储在文件中的。读本文前需要了解B树相关知识。在SQLite中，存储表数据用B+tree，存储表索引用B-tree。表索引和表数据采用不同的B树的原因是为了提高IO效率。注：后面文中在不区分B-tree和B+tree的地方统一用Btree来统称这两种B树。(2)Page(页)SQLite数据库文件由固定大小的“页(page)”组成。页的大小可以在512~32768之间(包含这两个值，必须是2的指数)，默认大小为1024个字节。页大小可以在数据库刚创建时设置，创建数据库之后，Page大小不再改变。Page是SQLite中B树的结构单元，也是磁盘读写的单元。数据文件中的Page从1开始编号，顺序排列在文件中，通过Page号可以很方便定位出Page在文件中的具体位置。(3)rowid每张表里的每条记录都会有一个唯一的整数id：rowid，这个是用于查找记录的关键key值。如果建表时创建了integer型主键，该值就作为rowid使用。如果没有创建，则系统自动生成integer的rowid，rowid用变长整数来表示。(4)变长整数变长整数是SQLite的特色之一，它既可以处理大整数，又可以节省存储空间。可变长整数由1~9个字节组成，每个字节的低7位有效，第8位是标志位。在组成可变长整数的各字节中，前面字节(整数的高位字节)的第8位置1，只有最低一个字节的第8位置0，表示整数结束。可变长整数可以不到9个字节，即使使用了全部9个字节，也可以将它转换为一个64-bit整数。下面是一些可变长整数的例子，例子取自源文件btree.c中的注释：0x00转换为0x000000000x7f转换为0x0000007f0x810x00转换为0x000000800x820x00转换为0x000001000x800x7f转换为0x0000007f0x8a0x910xd10xac0x78转换为0x12345678,该值与本人验算不一致，应是笔误。0x810x810x810x810x01转换为0x1020408上面例子取自源文件bree.c中的注释，但0x12345678这个似乎是错误的，欢迎大家验算纠正。相应的计算函数是sqlite3GetVarint和sqlite3PutVarint。2文件格式2.1系统表sqlite_masterSQLite数据库文件由多棵Btree构成，每棵Btree至少占用一个完整的页，每个页是Btree的一个结点单元。每个表或索引的第1个页为根页(rootpage)，所有表或索引的根页编号都存储在系统表sqlite_master中，表sqlite_master的根页为page1。sqlite_master是SQLite系统表，保存了数据库的结构(schema)信息，它包含5个字段:编号字段说明1type值为table、index、trigger或view之一。2name对象名称，值为字符串。3tbl_name如果是表或视图对象，此字段值与字段2相同。如果是索引或触发器对象，此字段值为与其相关的表名。4rootpage对触发器或视图对象，此字段值为0。对表或索引对象，此字段值为其根页的编号。5SQL字符串，创建此对象时所使用的SQL语句。2.2Page的格式每个页由四个部分构成：1．页头2．单元指针数组3．未分配空间4．单元内容区首先介绍“单元”的概念：Btree页内部以单元(cell)为单位来组织数据，一个单元包含一个(或部分，当使用溢出页时)payload(也称为Btree记录)。由于各类数据大小各不相同，每个单元的大小也就是可变的，所以Btree页内部的空间需要进行动态分配。页内所有单元的内容集中在页的底部，称为“单元内容区”，由下向上增长。由于单元的大小可变，因此需要对每个单元在页内的起始位置(称为单元指针)进行记录。单元指针保存在单元指针数组中，位于页头之后。单元指针数组包含0个或多个指针，由上向下增长。单元指针数组和单元内容区相向增长，中间部分为未分配空间。系统尽量保证未分配空间位于最后的指针之后，这样，就很容易增加新的单元，而不需要整理碎片。单元不需要是相邻和有序的，但单元指针是相邻和有序的。每个指针占2个字节，表示该单元在单元内容区中距页开始处的偏移。页中单元的数量保存在页头中。2.3Page1的格式之所以把Page1单独说明，是因为Page1的前100个字节为文件信息头，记录整个数据库文件的相关配置信息和一些状态信息。从第101个字节开始，同普通Page页的结构相同。从Page1的101字节开始，是系统表sqlite_master的表内容信息。2.4溢出页溢出页很好理解，因为有的记录长度很大，会超过一个Page的容量，这时系统就会分配溢出页来存放记录信息。溢出页的使用如下图示例：2.5DEMO演示现在创建一个简单的表同时为该表创建一个索引来看看Page中的数据是如何组织的。创建一个表，包含两个字段（水果名，水果的索引号）createtablefruit(namenvarchar(32),fruitIdxnvarchar(32));这里fruitIdx用的是字符串型，查看下面图例时比较方便理解。该表没有创建整数主键，则系统会为每条记录自动创建整数rowid。另外一种创建方法如下：createtablefruit(IDintegerprimarykeyautoincrement,namenvarchar(32),fruitIdxnvarchar(32));则ID作为记录的rowid，系统不会再另外分配rowid，同时系统会创建一个表sqlite_sequence，这个表有两个字段（name,seq），分别记录表名和rowid当前最大值。创建索引Createindextesttable_idxONfruit(fruitIdx);插入数据insertintofruit(name,fruitIdx)values('apple','02');insertintofruit(name,fruitIdx)values('coconut','09');insertintofruit(name,fruitIdx)values('orange','01');insertintofruit(name,fruitIdx)values('banana','03');由于demo数据量不大，所以一个page就可以保存所有数据。表和索引是两棵分开单独的Btree，所以这里表数据会是一个page，索引数据是另一个单独的page，这两个page也都是叶子页并且是根页。2.5.1表叶子页格式分析来看下图示：2.5.2索引页格式分析再来看看索引页中的内容和结构。2.5.3表内部页格式分析上面的demo只有少量数据，还不足以产生内部页。如果插入足够多的数据，表fruit的Btree将分裂并生成内部页，下图是表fruit内部页的示例。索引Btree同上面的示例图基本相同，主要的改变是rowid被实际的索引数据值替代，为节省篇幅就不再画图了。3数据操作前面介绍的SQLite文件的组织方式，现在来分析下当我们对数据库进行查询、增删改等操作时，数据库是如何工作的，分析工作过程对我们了解数据库的IO性能会很有帮助。本章的示例是前后关联的，所以需要顺序阅读。3.1一个简单的查询selete*fromfruitwherefruitIdx='04';从索引找到记录的流程大体如下图：小结：在这个小DEMO中我们访问了3棵Btree：系统表sqlite_master；用户表fruit，fruit表索引fruitIdx。这三棵Btree都是1阶Btree，Btree的阶可以简易理解为需要进行的IO次数。因为表是B+tree，内部页不保存记录数据，只保存关键Key值(rowid)，所以一个Page会有很大容量，即有很多儿子分支，这使得Btree的阶很小，3阶B+tree就可以具有较大容量。再来看看索引。索引数据结构是B-tree，所以无论是内部页还是叶子页都包含索引的数据值，如果数据值字节数比较大，比如长字符串，则会比较影响Page的容量，从而影响Btree阶数。对于长字符串值，可以考虑做Hash处理为短字符串，要注意保证其唯一性。最好是尽量用整数或短字符串来做索引，来控制索引的字节数。3.2插入记录插入两条记录insertintofruit(name,fruitIdx)values('cherry','06');insertintofruit(name,fruitIdx)values('durian','15');数据页变化示意：索引页变化示意：3.3删除记录删除两条记录，删除记录主要为演示空闲块的管理deletefromfruitwherefruitIdx='09'deletefromfruitwherefruitIdx='03'数据页变化示意索引页变化示意：小结：这个小节主要演示空闲块的管理，SQLite用空闲块链表的方式管理Page内的空闲碎片，需要使用空间时优先从空闲块列表中查找空闲块使用，如空闲块大小不能满足需要，则向中部的未用区域申请空间。3.4空闲页链表类似Page内的空闲块管理，空闲Page页的管理也采用类似的链表方式，在文件的Header区域中记录了第一个空闲Page页的页号，从而形成空闲Page链表。空闲页有两种类型：trunkpage(主干页)和leafpage(叶子页)。文件头偏移为32处的指针指向空闲链表的第一个trunkpage，每个trunkpage指向多个叶子页。偏移36处的4个字节为空闲页的总数量，包括所有的trunkpage和leafpage。空闲页链表的结构如下图所示：3.5修改记录updatefruitsetname='123456789012345678901234567890',fruitIdx='08'wherefruitIdx='02'更新记录的操作==删除旧数据+插入新数据；数据页的变化示意:索引页变化示意：小结：1.从这个demo中可以看到，如果用定长的数据做索引值，可以在一定程度上减少Page内碎块。2.update是比较重的操作，即使整条记录只有一个字节的改动，也可以引起整条记录全部重写，对于记录字段很多的表，有些字段改动很频繁，有些字段可能很少改动，在设计阶段应考虑是否需要分表。4参考文献1.《SQLite数据库文件格式全面分析》作者：空转。注：空转是作者的网名，真实姓名不详。本文部分文字和图片引自该文献。2.研究时使用的SQLite源码版本是3.2.8，老版本新增内容少，更容易理解其基础设计思想。5附录5.1B-tree还是用例子来演示B-tree，插入key值序列：agfbkdhmjesirxclntupB树的M=4B树的生长过程.swf上面附件演示了B-tree的生成过程，可以用QQ影音播放。下图是最终生成的B-tree在SQLite里B-tree应用于索引，上图中的字母可以理解为表索引的索引值。图中每一个字母集合的块（例如图中红圈所框的一个节点），可以理解为SQLite文件中的一个Page.5.2B+tree还是用上面的插入序列来演示，生成的B+tree如下图：在SQLite里B+tree应用于表，上图中的字母可以理解为表记录的rowid。