一种SQLite空闲链表节点的解析方法和装置

摘要

本发明提供了一种SQLite空闲链表节点的解析方法和装置，所述方法包括：读取SQLite空闲链表节点；从所述空闲链表节点中查找所有满足预设条件的记录关键点；对上述关键点进行记录重组；其中，所述记录关键点为4个字节组成的二元组，所述预设条件为：value(NFP)＞addr(NFP)并且value(FTL)∈(0，PSZ-addr(NFP)]。本发明基于SQLite数据库文件格式及记录的删除和插入规则，采用删除记录二元组信息的通用关键点特征识别关键点信息，然后对上述关键点中的所有数据记录进行重组，实现快速、准确地解析SQLite空闲链表节点的多记录元组的发明目的。

说明书

技术领域

本发明涉及计算机数据处理技术领域，特别是涉及一种SQLite空闲链表 节点的解析方法和装置。

背景技术

SQLite数据库是遵守数据库事务正确执行四要素-原子性、一致性、隔 离性和持久性(ACID，Atomicity、Consistency、Isolation、Durability)的关联 式数据库管理系统，其设计目标是嵌入式的，目前在很多嵌入式产品得到广 泛使用。主要特点：占用系统资源非常低，可支持Windows/Linux/Unix等等 主流的操作系统，可与很多程序语言相结合，并具有ODBC接口。与Mysql、 PostgreSQL这两款开源数据库管理系统相比，其处理速度更快。

传统的SQLite删除数据解析方法是根据记录数据的特征来断定某记录的 大概范围，从而解析某些关键数据，但是这种方法的弊端是只能针对某一类 具体数据库文件(如某类手机中的短信数据库文件)，而对于其他的数据库文 件(如邮件数据库文件)则需要重新提取数据特征并重新解析，无法保证通 用性。

SQLite数据库删除数据的通用解析，当前国内外研究比较少；目前市场 上的通用解析产品具有很大的局限性，特别其多记录空闲链表节点，或存在 记录碎片和关键点碎片的空闲链表节点，无法做到准确定位，解析效果不尽 如人意。测试发现对于存在较多记录碎片和关键点碎片的多记录空闲链表节 点，往往只能解析一条记录，甚至无法解析任何一条记录，而且解析结果经 常由于记录元组划分的不准确存在乱码现象，因此现有技术对多记录删除数 据重组的准确性和全面性均存在问题，无法适于实际应用。

发明内容

本发明所要解决的技术问题是提供一种SQLite空闲链表节点的解析方 法，可解决现有技术只能对SQLite数据库文件的单记录删除结构进行解析的 问题。

本发明还提供了一种SQLite空闲链表节点的解析装置，以保证上述方法 在实际中的应用。

为了解决上述问题，本发明公开了一种SQLite空闲链表节点的解析方法， 包括：读取SQLite空闲链表节点；从所述空闲链表节点中查找所有满足预设 条件的记录关键点；对上述关键点进行记录重组；

其中，所述记录关键点为4个字节组成的二元组<NFP，FTL>，所述预设 条件为：

value(NFP)>addr(NFP)并且value(FTL)∈(0，PSZ-addr(NFP)]；

NFP表示指向下一个空闲节点的指针，由2个字节组成；FTL是NFP后 面的2个字节，表示该空闲节点的大小；value(NFP)表示NFP指向的位置；

addr(NFP)表示NFP本身的偏移地址；value(FTL)表示该空闲节点的 大小；PSZ表示SQLite数据库中数据页的大小。

优选的，所述查找记录关键点的方法具体为：将所述空闲链表节点的偏 移地址的初始值设置为0；从该空闲链表节点中的当前偏移地址处开始读取4 个字节，判断是否满足上述2个条件，若是，则当前偏移地址位置对应的二 元组<NFP，FTL>为记录关键点；当前偏移地址增1，重复上述判断步骤，直 至当前偏移地址到达该空闲链表节点的末端。

优选的，还包括对所述所有关键点进行如下处理的步骤：若关键点<NFP_i， FTL_i>记录重组或记录碎片标记不成功，根据碎片特征调整关键点<NFP_i， FTL_i>的二元组信息，消除可能存在的关键点碎片，然后进行记录重组或记录 碎片标记。

优选的，还包括对所述关键点按从后到前的顺序进行如下伪关键点识别 处理的步骤：若关键点<NFP_i，FTL_i>重组不成功，且具备碎片重组条件，则 进一步判断<NFP_i-1，FTL_i-1>是否为重组不成功的节点，若是，将节点<NFP_i， FTL_i>向前与节点<NFP_i-1，FTL_i-1>合并，对合并后的节点<NFP_i-1，FTL_i-1>进行 记录重组或记录碎片标记，若不能满足记录重组或者记录碎片重组的条件， 则拆开合并后的节点<NFP_i-1，FTL_i-1>，对<NFP_i，FTL_i>进行记录碎片重组； 若关键点<NFP_i，FTL_i>重组不成功且不具备碎片重组条件，则进一步判断 <NFP_i-1，FTL_i-1>是否为重组成功的节点；若<NFP_i-1，FTL_i-1>是重组成功的节 点，则检查<NFP_i，FTL_i>是否为合并过的节点，对于合并节点，拆开合并节 点，从倒数第二个被合并节点开始重复上述伪关键点识别处理过程；若 <NFP_i-1，FTL_i-1>是重组不成功的节点，将节点<NFP_i，FTL_i>向前与节点<NFP_i-1， FTL_i-1>合并，对合并后的节点<NFP_i-1，FTL_i-1>用权利要求3所述的方法进 行记录重组、记录碎片标记和关键点碎片消除处理，当合并后节点重组不成 功、不具备碎片重组条件、且<NFP_i-1，FTL_i-1>的原始状态为碎片时，将合并 节点<NFP_i-1，FTL_i-1>拆开，从倒数第二个被合并节点开始重复上述伪关键点 识别处理过程。

依据本发明的另一优选实施例，还公开了一种SQLite空闲链表节点的解 析装置，包括空闲链表获取单元，关键点查找单元和记录重组单元，其中：

空闲链表获取单元用于读取SQLite空闲链表的节点；

关键点查找单元用于从所述空闲链表获取单元读取的空闲链表节点中查 找所有满足预设条件的记录关键点；

上述记录关键点为4个字节组成的二元组<NFP，FTL>，所述预设条件为：

value(NFP)＞addr(NFP)

并且

value(FTL)∈(0，PSZ-addr(NFP)]

NFP表示指向下一个空闲节点的指针，由2个字节组成；

FTL是NFP后面的2个字节，表示该空闲节点的大小；

value(NFP)表示NFP指向的位置；

addr(NFP)表示NFP本身的偏移地址；

value(FTL)表示该空闲节点的大小；

PSZ表示SQLite数据库中数据页的大小；

记录重组单元用于对所述关键点查找单元获得关键点进行记录重组。

优选的，所述关键点查找单元具体包括控制子单元和条件判断子单元， 其中：控制子单元用于控制所述条件判断子单元从偏移地址为0到该空闲链 表节点末端的遍历搜索过程；条件判断子单元用于从所述空闲链表节点中的 当前偏移地址处开始读取4个字节，判断是否满足所述预设条件，并将满足 所述预设条件的当前偏移地址位置对应的二元组<NFP，FTL>作为记录关键 点。

优选的，还包括关键点碎片消除单元，用于根据碎片特征调整重组不成 功的关键点<NFP_i，FTL_i>的二元组信息，消除可能存在的关键点碎片，然后 进行记录重组或记录碎片标记。

优选的，还包括记录碎片重组单元，用于对重组不成功且具备碎片重组 条件的关键点<NFP_i，FTL_i>作以下处理：当该关键点的前一个关键点<NFP_i-1， FTL_i-1>为重组不成功的节点时，合并节点<NFP_i-1，FTL_i-1>与<NFP_i，FTL_i>， 并对合并后的节点进行记录重组或记录碎片标记，若不能满足记录重组或记 录碎片重组条件，则拆开合并后的节点<NFP_i-1，FTL_i-1>，对<NFP_i，FTL_i>进 行记录碎片重组。

优选的，还包括伪关键点处理单元，用于对重组不成功且不具备碎片重 组条件的关键点<NFP_i，FTL_i>进行如下处理：当该关键点的前一个关键点 <NFP_i-1，FTL_i-1>为重组成功的节点时，检查<NFP_i，FTL_i>是否为合并过的节 点，对于合并节点，拆开合并节点，从倒数第二个被合并节点开始重复上述 伪关键点识别处理过程；当该关键点的前一个关键点<NFP_i-1，FTL_i-1>为重组 不成功的节点时，将<NFP_i，FTL_i>向前与<NFP_i-1，FTL_i-1>合并，对合并后 的节点<NFP_i-1，FTL_i-1>进行记录重组、记录碎片标记和碎片消除处理，当合 并后节点重组不成功、不具备碎片重组条件、且<NFP_i，FTL_i>的原始状态为 碎片时，将合并节点<NFP_i，FTL_i>拆开，从倒数第二个被合并节点开始重复 上述伪关键点识别处理过程。

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

本发明优选实施例方案中，基于SQLite数据库文件格式及记录的删除和 插入规则，采用SQLite空闲链表节点的删除记录二元组信息的通用关键点特 征识别关键点信息，然后对上述关键点中的所有数据记录进行重组，实现快 速、准确地解析SQLite空闲链表节点的多记录元组的发明目的；另外，由于 本发明优选实施例方案采用的是SQLite数据库空闲链表的通用特征进行识别 处理的，因此，本发明方案不局限于某一个特定数据库文件(如手机中的电 子邮件数据库)进行解析，而是对所有sqlite数据库的空闲节点多记录元组的 解析都适用，具有很强的通用性。

在本发明进一步的优选实施例中，利用节点合并和分离方法识别真伪关 键点，并且自适应消除关键点碎片，可增强空闲节点多记录元组解析的准确 性。

附图说明

图1是本发明SQLite空闲链表节点的解析方法第一实施例的流程图；

图2是本发明SQLite空闲链表节点的解析方法第二实施例的流程图；

图3是本发明SQLite空闲链表节点的解析装置一实施例的结构框图。

具体实施方式

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

SQLite数据库文件：由固定大小的页(Page)组成，页的大小为512～32768 字节(必须是2的指数)，默认大小为1024字节(1KB)。页的大小可以在创 建数据库时设置，数据库对象创建完成后就不能再修改了。页的类型包括二 叉排序树(Btree)页、空闲(free)页和/或溢出页(overflow)，Btree还可以 是B+tree或B-tree，每一种节点又可分为主干页和叶子页。

空闲链表节点位于叶子页中，由删除记录构成，可以是单个删除记录， 也可以是多个删除记录(包括完整记录和记录碎片)。

单个删除记录构成的空闲链表节点的结构如表1所示，其中，前2个字 节表示指向下一个空闲节点的指针NFP，第3～4字节表示该空闲节点的大小 FTL。

  NFP(2B)  FTL(2B) …  索引2 …  索引N  数据1  数据2 …  数据N

表1、单记录空闲链表节点的结构

对于多个删除记录构成的空闲链表节点，由于相邻的空闲节点会合并成 一个空闲链表节点，而且插入记录是又会从空闲节点中分配空间，从而破坏 简单的空闲节点结构；如此经过多次记录插入和删除之后，空闲节点的结构 将变得很混乱：节点中存在多条记录或者记录碎片，内部每个NFP指向的位 置呈随机化趋势，FTL的大小也未必表示后续空闲空间的大小，其中NFP和 FTL组成的二元组<NFP_i，FTL_i>称为关键点，上述i∈[1，N]，N表示该节点 中包括的删除记录数。

表2、多记录空闲链表节点的结构

如表2所示，NFP₁指向下一个空闲链表节点的地址，其他的NFP_i(i∈ (1，N])指向的位置有可能是下一个空闲链表节点的地址，也可能是NFP_j(j∈(i，N])，还可能是后续插入的记录的内容区；FTL₁表示当前多记录构 成的空闲节点的大小，FTL_i(i∈(1，N])可能是表示该空闲节点后续的空 间大小，也可能是记录碎片的大小；此外关键点<NFP_i，FTL_i>(i∈[1，N]) 有可能因为被覆盖而变成关键点碎片。

对于删除记录REC_i(i∈[1，N])，前2字节NFP_i指向下一块空闲节点的 地址，后续2个字节FTL_i表示该空闲节点的大小，经过一系列的删除、插入 操作之后，空闲节点的结构可能带来如下变化：

(1)NFP_i指向的可能不是下一个空闲节点的地址；

(2)FTL_i表示的可能是多条记录的长度或者仅为记录碎片的长度；

(3)关键点<NFP_i，FTL_i>可能因为被覆盖而变成碎片(小于4字节)。

但是，关键点<NFP_i，FTL_i>的最原始特性使得该关键点至少保持了2个 基本特征：

(1)NFP_i本身的位置偏移(记为addr(NFP_i))和NFP_i指向的位置(记 为value(NFP_i))之间的关系是线性增长关系，满足关系式：

value(NFP_i)>addr(NFP_i)

(2)FTL_i表示的是相应的空闲节点或子节点的大小(记为value(FTL_i))， 其取值范围满足：

value(FTL_i)∈(0，PSZ-addr(NFP_i)]

上述PSZ表示SQLite数据库文件的Btree数据页的大小。

方法实施例：

参照图1，示出了本发明SQLite空闲链表节点的解析方法第一实施例的 流程，具体包括以下步骤：

步骤S101：读取SQLite空闲链表节点；

步骤S102：从上述空闲链表节点中查找所有满足预设条件的记录关键点；

上述预设条件即上文所述的关键点<NFP，FTL>的2个基本特征：

value(NFP_i)＞addr(NFP_i)

且

value(FTL_i)∈(0，PSZ-addr(NFP_i)]

在本优选实施例中，可采用下述方法查找记录关键点：

步骤S102-1：将该空闲链表节点FRN偏移地址offset的初始值设置为0；

步骤S102-2：判断offset是否已经达到该FRN的末端，若是，结束关键 点的查找过程，转步骤S103；否则，转步骤S102-3；

步骤S102-3：从FRN中offset处开始读取4个字节，组成<NFP，FTL>；

步骤S102-4：判断该<NFP，FTL>是否满足上述的2个基本特征，若是， 转步骤S103-5；否则，转步骤S102-6；

步骤S102-5：该offset位置对应的二元组即可能为记录关键点，将该关键 点信息加入关键点链表FLIST，并且修正相关的二元组信息；转步骤S102-6；

步骤S102-6：offset++(即将偏移地址offset增1)，转步骤S102-2；

步骤S103：对上述关键点进行记录重组；

参照图2，示出了本发明SQLite空闲链表节点的解析方法第二实施例的 流程；考虑到value(NFP_i)＞addr(NFP_i)和value(FTL_i)∈(0，PSZ-addr(NFP_i)]只 是判断关键点<NFP_i，FTL_i>的必要条件，仅仅满足这2个特征未必是真关键 点，还有可能是伪关键点，优选实施例为提高数据解析的精确性，除上述第 一实施例所包括的步骤外，还包括进一步识别处理其中包括的伪关键点和关 键点碎片的步骤，具体流程如下：

步骤S201：读取SQLite空闲链表节点；

步骤S202：从上述空闲链表节点中查找所有满足预设条件的记录关键点， 并将上述关键点信息加入关键点链表FLIST；

步骤S203：正序遍历FLIST，检测各关键点是否满足记录重组或碎片重 组条件，若是，则为相应关键点设置重组标记或碎片标记；

在本优选实施例中，可采用下述方法实现记录重组及碎片消除过程：

步骤S203-1：令i＝1；

步骤S203-2：对<NFP_i，FTL_i>进行完整记录重组；

步骤S203-3：判断上述记录重组是否成功，若是，为该关键点设置重组 标志，转步骤S203-7；否则，转步骤S203-4；

步骤S203-4：根据碎片特征调整<NFP_i，FTL_i>的二元组信息，消除可能 存在的关键点碎片，然后尝试完整记录重组；

步骤S203-5：判断上述消除碎片后的记录重组是否成功，若是，为该关 键点设置重组标志，转步骤S203-7；否则，还原<NFP_i，FTL_i>的二元组信息， 转步骤S203-6；

步骤S203-6：检测<NFP_i，FTL_i>是否满足碎片重组条件；若是，为该关 键点设置碎片标记；否则，根据碎片特征调整<NFP_i，FTL_i>的二元组信息， 消除可能存在的关键点碎片，然后尝试记录记录碎片重组，若记录碎片标记 失败，还原<NFP_i，FTL_i>的二元组信息；

步骤S203-7：i＝i+1；若i≤N，转步骤S203-2；否则，转步骤S204；

其中，上述N表示FLIST中关键点的数量。

步骤S204：逆序遍历FLIST，对没有记录重组标记或碎片标记的关键点， 利用节点合并和拆分方法识别真伪关键点；

在本优选实施例中，可采用下述方法实现上述记录重组及碎片消除过程：

步骤S204-1：令i＝N；其中，N表示FLIST中关键点的数量；

步骤S204-2：判断<NFP_i，FTL_i>是否有重组标志，若是，转步骤S204-9； 否则；转步骤S204-3；

步骤S204-3：判断<NFP_i，FTL_i>是否有碎片标记，若是，转步骤S204-4； 否则，转步骤S204-6；

步骤S204-4：判断前一个节点<NFP_i-1，FTL_i-1>是否有重组标记，若是， i＝i-1，转步骤S204-9；否则，转步骤S204-5；

步骤S204-5：把节点<NFP_i-1，FTL_i-1>与<NFP_i，FTL_i>合并，对于合并 后的节点<NFP_i-1，FTL_i-1>进行记录重组；若重组成功，为合并后的节点设置 重组标志，i＝i-2，转步骤S204-9；否则，拆开合并的节点，对于<NFP_i，FTL_i>， 根据二元组信息重组记录碎片，设置重组标记，i＝i-1，转步骤S204-9；

步骤S204-6：判断前一个节点<NFP_i-1，FTL_i-1>是否有重组标记，若是， 转步骤S204-7；否则，转步骤S204-8；

步骤S204-7：检查该节点<NFP_i，FTL_i>是否为合并过的节点，若是，拆 开合并节点，<NFP_i，FTL_i>指向倒数第二个被合并节点，转步骤S204-9；否 则，忽略该节点，i＝i-1，转步骤S204-9；

步骤S204-8：将节点<NFP_i-1，FTL_i-1>与<NFP_i，FTL_i>合并(当前关键 点为伪关键点)，对于合并后的节点<NFP_i-1，FTL_i-1>，用步骤S203-2～S203-6 的方法来检查是否满足重组条件或碎片重组条件，若是，设置相应的重组标 志或碎片标志，i＝i-1，转步骤S204-9；否则，当<NFP_i，FTL_i>的原始状态为 碎片时，将合并节点拆开，下标第二大的被合并节点作为当前节点，转步骤 S204-9；

步骤S204-9：若i≥1，转步骤S204-2；否则，结束流程。

对于前述的各方法实施例，为了描述简单，故将其都表述为一系列的动 作组合，但是本领域的技术人员应该知悉，本发明并不受所描述的动作顺序 的限制，因为根据本发明，某些步骤可以采用其他顺序或同时执行其次， 本领域技术人员也应该知悉，上述方法实施例均属于优选实施例，所涉及的 动作和模块并不一定是本发明所必须的。

装置实施例：

参照图3，示出了本发明SQLite空闲链表节点的解析装置一实施例的结 构框图，包括空闲链表获取单元31、关键点查找单元32、记录重组单元33、 关键点碎片消除单元34、记录碎片重组单元35和伪关键点处理单元36，其 中：

空闲链表获取单元31：用于读取SQLite空闲链表节点。

关键点查找单元32：用于从空闲链表获取单元31读取的空闲链表节点中 查找所有满足预设条件的记录关键点；

上述记录关键点为4个字节组成的二元组<NFP，FTL>，预设的判断条件 为：

value(NFP)＞addr(NFP)

并且

value(FTL)∈(0，PSZ-addr(NFP))；

其中，

NFP表示指向下一个空闲节点的指针，由2个字节组成；

FTL是NFP后面的2个字节，表示该空闲节点的大小；

value(NFP)表示NFP指向的位置；

addr(NFP)表示NFP本身的偏移地址；

value(FTL)表示该空闲节点的大小；

PSZ表示SQLite数据库中数据页的大小；

本优选实施例的关键点查找单元32具体包括控制子单元32-1和条件判断 子单元32-2，控制子单元32-1用于控制条件判断子单元32-2从偏移地址offset 为0到该空闲链表节点末端的遍历搜索过程；条件判断子单元32-2用于从空 闲链表获取单元31读取的空闲链表节点中的offset开始读取4个字节，判断 是否满足上述预设条件，并将满足上述预设条件的offset位置对应的二元组 <NFP，FTL>作为记录关键点。

记录重组单元33：用于对关键点查找单元32获得关键点进行记录重组。

关键点碎片消除单元34：用于根据碎片特征调整所有重组不成功的关键 点<NFP_i，FTL_i>的二元组信息，消除可能存在的关键点碎片，然后进行记录 重组。

记录碎片重组单元35：用于对所有重组不成功且具备碎片重组条件的关 键点<NFP_i，FTL_i>作以下处理：当该关键点的前一个关键点<NFP_i-1，FTL_i-1> 为重组不成功的节点时，合并节点<NFP_i-1，FTL_i-1>与<NFP_i，FTL_i>，并对合 并后的节点进行记录重组，若不能满足记录重组或者记录碎片重组的条件， 则拆开合并后的节点<NFP_i-1，FTL_i-1>，对<NFP_i，FTL_i>进行记录碎片重组。

伪关键点处理单元36：用于对重组不成功且不具备碎片重组条件的关键 点<NFP_i，FTL_i>进行如下处理：当该关键点的前一个关键点<NFP_i-1，FTL_i-1> 为重组不成功的节点时，将<NFP_i-1，FTL_i-1>与<NFP_i，FTL_i>合并，对合并后 的节点<NFP_i-1，FTL_i-1>进行记录重组、记录碎片标记和关键点碎片消除处理， 当合并后节点还是重组不成功、不具备碎片重组条件、且<NFP_i，FTL_i>的原 始状态为碎片时，将合并节点<NFP_i-1，FTL_i-1>拆开，从倒数第二个被合并节 点开始重复上述伪关键点识别处理过程；当该关键点的前一个关键点<NFP_i-1， FTL_i-1>为重组成功的节点时，检查<NFP_i，FTL_i>是否为合并过的节点，对于 合并节点，拆开合并节点，从倒数第二个被合并节点开始重复上述伪关键点 识别处理过程。

需要说明的是，上述装置实施例属于优选实施例，所涉及的单元和模块 并不一定是本发明所必须的。

本说明书中的各个实施例均采用递进的方式描述，每个实施例重点说明 的都是与其他实施例的不同之处，各个实施例之间相同相似的部分互相参见 即可。对于本发明的装置实施例而言，由于其与方法实施例基本相似，所以 描述的比较简单，相关之处参见方法实施例的部分说明即可。

以上对本发明所提供的一种SQLite空闲链表节点的解析方法和装置进行 了详细介绍，本文中应用了具体个例对本发明的原理及实施方式进行了阐述 以上实施例的说明只是用于帮助理解本发明的方法及其核心思想；同时，对 于本领域的一般技术人员，依据本发明的思想，在具体实施方式及应用范围 上均会有改变之处，综上所述，本说明书内容不应理解为对本发明的限制。