一种SQLite空闲页上被删数据表的记录分析方法和装置

摘要

本发明一种SQLite空闲页上被删数据表的记录分析方法和装置，该方法从主表去分析被删除的数据表的建表记录，并且根据建表记录来分析空闲页。该装置包括：读取单元、建表记录获取单元、节点读取标记单元、数据表的结构FTS获取单元、删除记录获取单元。本发明极大的增强空闲页上删除记录挖掘的准确性和全面性，尤其是数据表被删除的情况，恢复效果十分显著。

说明书

技术领域

本发明涉及计算机数据处理技术领域，特别涉及一种SQLite空闲页上被删 数据表的记录分析方法和装置。

背景技术

SQLite是一款轻型的数据库。它的设计目标是嵌入式的，广泛运用于各种 嵌入式设备中，具有占用资源小的特点。相比于Mysql、PostgreSQL这两款开 源的世界著名数据库管理系统，具有更快的处理速度。

传统的SQLite删除数据解析方法是根据记录数据的特征来识别记录关键数 据的起始和终止标志，从而解析某些关键数据，但是这种方法的弊端是只能针 对某一类数据库文件的某些关键数据，而无法提取全部数据，并且对于其他的 数据库文件则需要重新提取数据特征并重新解析，无法保证通用性。

SQLite数据库删除数据的通用解析，当前国内外研究比较少；目前市场上 的通用解析产品具有很大的局限性，其空闲页删除记录挖掘，由于对于记录特 征提取不够精确，对于整表删除的数据，基本无法恢复出任何数据，这样影响 了删除记录解析的准确性和全面性。

目前现有专利中对于删除数据的通用解析均为对于未删除数据表的恢复， 如专利CN201110266852.1以及CN201110266852.1，而不适用于已删除数据表。

发明内容

本发明提出一种SQLite空闲页上被删数据表的记录分析方法和装置，可以 快速、准确地挖掘SQLite的空闲页上删除记录，主要包括被删除的数据表上的 记录。

具体方案如下：

一种SQLite空闲页上被删数据表的记录分析方法，包括以下步骤：

S1：读取主表的B+tree树以及空闲页链表；

S2：若被删数据表已知，直接手动构造FTLIST，若被删数据表未知，则从 步骤S1得到的主表B+tree和空闲页链表中，解析得到删除的完整的建表记录 集合FTLIST；

S3：读取FTLIST中的下一个未读节点，记为FTNODE，并将该节点标记为已 读；

S4：分析FTNODE节点中的建表SQL语句，得到该被删除的数据表的结构FTS；

S5：获取空闲页中符合该FTS结构的删除记录。

进一步的，所述的步骤S2中解析得到删除的完整的建表记录集合FTLIST 的具体步骤是：

S21：从主表B+tree和空闲页链表中，解析得到初步的删除建表记录集合 FTLIST1；

S22：从FTLIST1排除重复记录并且过滤掉碎片记录和非建表记录，得到集 合FTLIST2；

S23：从数据库主表中查询得到所有未删除的建表记录集合TLIST；

S24：在FTLIST2中排除与TLIST中重复的记录，得到的集合FTLIST，该集 合FTLIST即为最终的删除建表记录集合。

进一步的，所述的步骤S5的具体步骤是：

S51：读取SQLite空闲页链表节点；

S52：从空闲页链表节点中查找所有与FTS相匹配的记录关键点；

S53：对关键点进行记录重组。

其中，所述的步骤S24中FTLIST2中排除与TLIST中重复的记录根据为表 名字、根页号和建表SQL语句的一种或多种。

其中，所述步骤S52中所述记录关键点为4个字节组成为二元组<NFP,FTL> 或<TL,HL>，其中<NFP,FTL>对应记录头部4个字节被覆盖的情况，NFP表示指向 下一个空闲节点的指针，由2个字节组成，FTL是NFP后面的2个字节，表示 该空闲节点的大小，而<TL,HL>对应的是记录头部完整的情况，TL表示记录总长 度，是记录的第一个变长整数，HL表示头部总长度，是记录的第三个变长整数。 一种SQLite空闲页上被删数据表的记录分析装置，所述的装置包括：

读取单元，用于读取主表的B+tree树以及空闲页链表；

建表记录获取单元，用于若被删数据表已知，直接手动构造FTLIST，若被 删数据表未知，则从读取单元得到的主表B+tree和空闲页链表中，解析得到删 除的完整的建表记录集合FTLIST；

节点读取标记单元，用于读取FTLIST中的下一个未读节点，记为FTNODE， 并将该节点标记为已读；

数据表的结构FTS获取单元，用于分析FTNODE节点中的建表SQL语句，得 到该被删除的数据表的结构FTS；

删除记录获取单元，用于获取空闲页中符合该FTS结构的删除记录。

进一步的，所述的建表记录获取单元包括：

第一记录获取单元，用于从主表B+tree和空闲页链表中，解析得到初步的 删除建表记录集合FTLIST1；

第二记录获取单元，用于从FTLIST1排除重复记录并且过滤掉碎片记录和 非建表记录，得到集合FTLIST2；

第三记录获取单元，用于从数据库主表中查询得到所有未删除的建表记录 集合TLIST；

最终记录获取单元，用于在FTLIST2中排除与TLIST中重复的记录，得到 的集合，该集合FTLIST即为最终的删除建表记录集合。

进一步的，所述的删除记录获取单元包括：

空闲页链表节点读取单元，用于读取SQLite空闲页链表节点；

记录关键点查找单元：用于从空闲页链表节点中查找所有与FTS相匹配的 记录关键点；

关键点重组单元：用于对关键点进行记录重组。

其中，所述的最终记录获取单元中排除与TLIST中重复的记录根据可以为 表名字、根页号和建表SQL语句的一种或多种。

其中，所述记录关键点查找单元中所述记录关键点为4个字节组成的二元 组<NFP,FTL>或<TL,HL>，其中<NFP,FTL>对应记录头部4个字节被覆盖的情况， NFP表示指向下一个空闲节点的指针，由2个字节组成，FTL是NFP后面的2 个字节，表示该空闲节点的大小，而<TL,HL>对应的是记录头部完整的情况，TL 表示记录总长度，是记录的第一个变长整数，HL表示头部总长度，是记录的第 三个变长整数。

与现有技术相比，本发明具有以下优点：

实用性：无需人工分析介入，自动识别主表上删除的数据表的建表记录并 分析数据表的结构，并且根据分析到的数据表的结构来解析空闲页上的删除记 录；由于SQLite的使用呈广泛化趋势，该方法的重要性不言而喻，预计该方法 将对数据库信息安全技术产生一定影响，也为其它相近数据库类型的自由空间 记录挖掘提供崭新思路。

创新性：该方法创造性的从主表去分析被删除的数据表的建表记录，并且 根据建表记录来分析空闲页，增强空闲页上删除记录挖掘的准确性和全面性， 尤其是对于数据表被删除的情况；该方法不仅在算法上体现出简洁明了的特点， 更凭借其出色的环境适应性，大大增加了程序的健壮度；并且该方法不局限于 某一个数据库，而是对所有SQLite数据库的自由空间的删除记录挖掘都适用， 具有很强的通用性。

附图说明

图1为一个SQLite页面结构示意图；

图2为一个实施例的数据库展示图；

图3为本发明的主流程图；

图4为该实施例的主表数据截图；

图5为该实施例的food表残留数据截图；

图6为该实施例的主表恢复结果图；

图7为该实施例的food表的删除记录图。

具体实施方式

在结合附图和具体实施方式对本发明作进一步详细的说明之前，首先介绍 一下与SQLite数据库有关的几个概念。

SQLite数据库由系列的数据表组成的，而这一系列的数据表表及其对应的 索引表(index)和触发器(trigger)均由主表(sqlite_master)来管理，而主表和 普通的数据表没有区别，由一系列页面来记录数据表、索引表和触发器等的变 更(创建、删除等)，并且这些页面组织由B+tree来管理，每个B+tree节点 对应一个SQLite页面。

SQLite主表具有以下3个特征：

1)以一棵B+tree组织；

2)以第一页为根页；

3)由5个字段组成：(typetext,nametext,tbl_nametext,rootpage integer,sqltext)

SQLite主表及其管理的数据表由B+tree来组织页面管理，而数据表对应的 索引表有B-tree来组织页面管理，在这一系列Btree(包括B+tree和B-tree) 之外的页面统称为空闲页。

空闲页以链表形式组织起来，图1为SQLite页面结构示意图，其中

a.链表首指针存放在文件头32字节偏移处的4个字节；

b.若只有一个空闲页，则没有主干页，仅有的一个空闲页是叶子页；

c.每个主干页的第0-3字节，指向下一个主干页的页号，0表示链表结束；

d.每个主干页的第4-7字节，表示该主干页的叶子页的数量；

e.每个主干页的第8个字节开始，分别以4字节表示一个空闲页的页号。

空闲页上被删数据表的分析：

如上述所描述，空闲页已经脱离了B+tree的管理范围，已经无法得知某一 个空闲页是归属于哪个B+tree或者归属于哪张数据表，不过对于数据库中存在 的数据表，依然可以用尝试的方式来分析空闲页，从而把空闲页中的删除记录 解析出来，但是对于数据库中已删除的数据表，就无法尝试分析了。

基于上述主表的三个特征可得知，数据库中表格的删除，依然可以通过主 表的B+tree来分析出被删表格的名称、根页和创建表的SQL语句等，其恢复的 方式与一般的表格的删除记录恢复方式类似。

因此，我们可以通过主表的记录解析(包括删除记录)并且排重得到删除 的表格的基本属性，包括表格名字、根页和SQL语句等，然后根据SQL语句分 析出该删除的数据表的表结构属性，并且根据分析得到的表结构去解析空闲页 链表，从而解决数据库中已删除数据表无法删除恢复的问题。

此外，对于某些特定的已知数据库(比如Android手机的QQ数据库等)， 我们可以跳过主表的记录分析，直接自行构造建表记录来达到解析空闲页的目 的。

为进一步说明各实施例，本发明提供有附图。这些附图为本发明揭露内容 的一部分，其主要用以说明实施例，并可配合说明书的相关描述来解释实施例 的运作原理。配合参考这些内容，本领域普通技术人员应能理解其他可能的实 施方式以及本发明的优点。现结合附图和具体实施方式对本发明进一步说明。

结合图2，数据库只有一张数据表f3，删除的数据表为food，图3示出了 本发明SQLite空闲页上被删数据表的记录分析方法的一实施例流程，基于本发 明的方法，分析出food表的删除记录，具体包括以下步骤：

S1：根据SQLite数据表结构和文件格式，从数据库文件中读取主表的B+tree树；

S2：根据SQLite数据表结构和文件格式，从数据库文件中读取空闲页链表；

S3：从步骤1和步骤2得到的主表B+tree和空闲页链表中，解析得到删除 的完整的建表记录集合FTLIST：

S31：从主表B+tree和空闲页链表中，解析得到初步的删除建表记录集 合FTLIST1；

S32：从FTLIST1排重并且过滤掉碎片记录和非建表记录，得到集合 FTLIST2；

S33：从数据库主表中查询得到所有未删除的建表记录集合TLIST；

S34：在FTLIST2中排除与TLIST中重复的记录，得到的集合FTLIST即 为最终的删除建表记录集合，其中，排重的根据有表名字、根页号和建表SQL 语句等；

S4：读取FTLIST表中的下一个未读节点，记为FTNODE，并将该节点标记为 已读；

S5：分析FTNODE节点中的建表SQL语句，得到该被删除的数据表的结构FTS；

S51：读取SQLite空闲页链表节点；

S52：从空闲页链表节点中查找所有与FTS相匹配的记录关键点；

S53：对关键点进行记录重组。

图4为经步骤S1、S2及S3获取的SQlite主表的数据截图，其中选中部分 是已被删除的表food数据及其初步的删除建表记录，图6为food表残留数据 截图，用于从初步的删除建表记录中过滤该残留数据，图5为经步骤S1、S2及 S3最终的food表删除建表记录，最终经步骤S4、S5分析出全部的3条数据表 food的删除记录。

通过已分析出的food表的删除记录，构建SQL语句，最终可对food表进 行恢复。

本领域技术人员应该知道，步骤S5中所述记录关键点为4个字节组成的二 元组<NFP,FTL>或<TL,HL>，其中<NFP,FTL>对应记录头部4个字节被覆盖的情况， NFP表示指向下一个空闲节点的指针，由2个字节组成，FTL是NFP后面的2 个字节，表示该空闲节点的大小，而<TL,HL>对应的是记录头部完整的情况，TL 表示记录总长度，是记录的第一个变长整数，HL表示头部总长度，是记录的第 三个变长整数。

基于上述的SQLite空闲页上被删数据表的记录分析方法，本发明还提出一 种SQLite空闲页上被删数据表的记录分析装置，所述的装置包括：

读取单元，用于读取主表的B+tree树以及空闲页链表；

建表记录获取单元，用于若被删数据表已知，直接手动构造FTLIST，若被 删数据表未知，则从读取单元得到的主表B+tree和空闲页链表中，解析得到删 除的完整的建表记录集合FTLIST；

节点读取标记单元，用于读取FTLIST中的下一个未读节点，记为FTNODE， 并将该节点标记为已读；

数据表的结构FTS获取单元，用于分析FTNODE节点中的建表SQL语句，得 到该被删除的数据表的结构FTS；

删除记录获取单元，用于获取空闲页中符合该FTS结构的删除记录。

进一步的，所述的建表记录获取单元包括：

第一记录获取单元，用于从主表B+tree和空闲页链表中，解析得到初步的 删除建表记录集合FTLIST1；

第二记录获取单元，用于从FTLIST1排除重复记录并且过滤掉碎片记录和 非建表记录，得到集合FTLIST2；

第三记录获取单元，用于从数据库主表中查询得到所有未删除的建表记录 集合TLIST；

最终记录获取单元，用于在FTLIST2中排除与TLIST中重复的记录，得到 的集合，该集合FTLIST即为最终的删除建表记录集合。

进一步的，所述的删除记录获取单元包括：

空闲页链表节点读取单元，用于读取SQLite空闲页链表节点；

记录关键点查找单元：用于从空闲页链表节点中查找所有与FTS相匹配的 记录关键点；

关键点重组单元：用于对关键点进行记录重组。

其中，所述的最终记录获取单元中排除与TLIST中重复的记录根据可以为 表名字、根页号和建表SQL语句的一种或多种。

其中，所述记录关键点查找单元中所述记录关键点为4个字节组成的二元 组<NFP,FTL>或<TL,HL>，其中<NFP,FTL>对应记录头部4个字节被覆盖的情况， NFP表示指向下一个空闲节点的指针，由2个字节组成，FTL是NFP后面的2 个字节，表示该空闲节点的大小，而<TL,HL>对应的是记录头部完整的情况，TL 表示记录总长度，是记录的第一个变长整数，HL表示头部总长度，是记录的第 三个变长整数。

尽管结合优选实施方案具体展示和介绍了本发明，但所属领域的技术人员 应该明白，在不脱离所附权利要求书所限定的本发明的精神和范围内，在形式 上和细节上可以对本发明做出各种变化，均为本发明的保护范围。