基于嵌入式文件系统的记录数据快速存储与检索的研究

摘要：文章探讨了基于嵌入式文件系统的记录数据存储和检索的设计方法，首先简单介绍了嵌入式文件系统的基本知识和实现原理，接着简要概述Nor Flash和Nand Flash区别，针对嵌入式系统中对文件系统的可靠性以及访问存储速度的特殊要求，重点介绍本研究课题的整体设计方案、映射表原理和链表原理，以及利用映射表和链表来实现记录数据快速存储和检索的设计原理。

关键词：快速存储；快速检索；文件系统；嵌入式系统；映射表

中图分类号：TP317 文献标识码：A文章编号：1009-2374（2012）04-0109-03

随着嵌入式技术的发展以及在各种电子产品中的广泛应用，数据存储管理已经成为嵌入式系统中一个重

要而深远的研究课题，由此诞生了嵌入式文件系统。

嵌入式文件系统是嵌入式系统中重要组成部分，它构成了嵌入式系统上所有数据基础，是系统中庞大复杂且又是最为基本和重要的资源。那么如何在文件系统上实现用户记录数据的快速可靠存储与检索是本文的研究重点。

一、文件系统定义

文件系统（File System）是系统的一个重要组成部分，通过对所管理的存储空间的抽象，向用户提供统一的、对象化的访问接口，屏蔽对物理设备的直接操作和资源管理。从系统角度来看，文件系统是对文件存储器空间进行组织和分配，负责文件的存储并对存入的文件进行保护和检索的系统。具体地说，它负责

为用户建立文件，存入、读出、修改、转储文件，控制文件的存取，当用户不再使用时删除文件等。

二、嵌入式文件系统

嵌入式文件系统中，Flash作为一种流行的存储设备，Flash存储器具有速度快、容量大、成本低等很多优点，因此大部分嵌入式系统都是把文件系统建立在Flash存储器之上。

Flash存储器主要有Nor Flash和Nand Flash两种类型。目前，针对Nor Flash设计的文件系统JFFS/JFFS2在嵌入式系统中已得到广泛的应用；随着Nand作为大容量存储介质的普及，基于Nand闪存的文件系统YAFFS(Yet Another Flash File System)正逐渐被应用到嵌入式系统中。

Nor属于芯片内执行(XIP, eXecute In Place)的读取，和我们常见的SDRAM的读取是一样，用户可以直接运行装载在Nor Flash里面的代码，Nand Flash没有采取内存的随机读取技术，它的读取是以一次读取一块的形式来进行的，通常是一次读取512个字节，采用这种技术的Flash比较廉价，用户不能直接运行Nand Flash上的代码。

针对Flash的特点，文件系统设计时还需要重点考虑Flash的损耗平衡、纠错和坏块处理问题。通常Nand中每个块的最大擦写次数是一百万次，而Nor的擦写次数是十万次。如果某块擦除次数超过寿命次数，容易导致坏块。所谓坏块并不是整个块都坏了，可能只是块中一位或某几位损坏。Nand器件中的坏块在出厂就有，且是随机分布的。Nor正常不存在该问题。Nand器件需要对介质进行初始化扫描以发现坏块，并将坏块标记为不可用。所有Flash器件都受位交换现象的困扰，一位的变化可能不很明显，但是如果发生在一个关键文件上，这个小小的故障可能导致系统停机。理论上Nand比Nor更容易受到影响。

由于这些特殊性，所以在Flash这样的设备上建立文件系统以及在文件系统上实现记录数据存储和检索的方法将直接影响嵌入式系统的运行性能和客户体验，具有深远的研究意义。

三、设计方案

（一）设计说明

文件系统操作是以文件为单位，从系统角度来看，文件系统是对文件存储器空间进行组织和分配，负责文件存储并对存入的文件进行保护和检索的系统。具体地说，它负责为用户建立文件，存入、读出、修改、转储文件，控制文件的存取，当用户不再使用时删除文件等操作。

根据文件系统的以上原理，本设计以文件为存储体对象，同时分配有一个与文件长度相等的映射内存，在映射内存上构建记录的存储结构，所有存储、检索、删除等操作首要都是在映射内存中完成，只有在需要更新时候才需要将部分数据更新到文件，避免频繁且大数据量读写文件，实现记录数据的快速存储与检索。

（二）结构图

（三）存储结构

记录的存储是以文件为存储体对象，因此需要在文件的映射內存中构建存储结构，如图1所示，存储结构包括：头信息、映射表和记录区组成。头信息主要用来存储记录相关信息，如总记录容量、已存记录数，剩余记录容量，链表信息等信息；映射表主要是描述记录与位置编号之间的关系；记录区就是用来存储真正的记录数据。

（四）头信息

头信息主要用来存储记录相关信息，如文件大小、总记录容量、已存记录数、剩余记录容量、记录域信息、记录链表信息、空闲链表信息等信息，如图2所示。通过头信息可以快速获取当前记录文件的信息，以便快速统计和存储操作。

（五）映射表和链表

映射表主要是描述记录与位置编号之间的关系，以及通过链表的方式构建记录与记录编号之间的关系，如图3所示，映射表是以链表节点为单位组成的，链表节点通过链表的方式串接起来。

链表主要用于管理记录数据，每一个记录就是一个小数据块单元，用链表将这些单元串接起来。链表有链表节点，节点编号对应一个记录位置编号，每个节点信息分为2部分，包含前向指针和后向指针，前向指针填充当前节点的前一个记录位置编号，后向指针填充当前节点的后一个记录位置编号（这里所指的前一个和后一个是逻辑上意义，非物理上排列）。

记录位置编号：是指记录区各个记录的位置编号，如有N个记录，从编号从1-N。

链表节点编号：链表节点编号与记录位置编号一样，是一一对应的。

记录编号：是指一个记录在链表中的逻辑位置，也就是该记录属于记录链表的从链表头开始的第几个节点。

从头信息可以看出，有2个链表信息（即2条链表）：记录链表信息和空闲链表信息，记录链表是将已存储的记录串接起来，空闲链表是将空闲的记录串接起来；记录链表信息的前向指针指向0，后项指针指向第1个记录编号的记录位置编号（链表节点编号），该链表节点编号所对应链表节点信息的后项指针又指向下一个记录位置编号（链表节点编号），直到结束；空闲链表信息的前向指针指向0，后项指针指向第1个空闲记录编号的记录位置编号（链表节点编号），该链表节点编号所对应链表节点信息的后项指针又指向下一个记录位置编号（链表节点编号），直到结束；。

计算记录在映射内存中的地址：根据记录编号去推算记录链表信息后项指针，得到记录位置编号，根据（（记录位置编号-1）×记录长度）得到记录地址偏移量，（记录地址偏移量+映射内存地址）得到记录在映射内存中的地址。

（六）记录区和域信息

记录区就是用来存储真正的记录数据，因此记录区将划分成等分的记录单元，每个记录单元存储一个记录数据，每个记录数据可由多个数据域组成，如排序域等，通过排序域，可以将记录按照指定的规则进行排序，具体由头信息字段中域信息决定，如图4

所示。

域信息包括：域个数和各域描述：

域个数：用于表示记录所组成的域个数；

域描述：用于描述记录的各域组成，以及每个域的属性和最大长度；域属性可参考图5所示位图表示。

（七）记录操作

通过以上原理介绍,可以快速进行记录数据的存储、删除、查找等操作，因为记录数据是通过映射表和链表来管理，通过映射表和链表检索就可以快速定位记录数据，无需去读取实际记录数据，考虑到数据存取的效率，每一个记录文件都对应有一个与之大小相等映射内存，文件中的数据与内存中的数据是同

步的。

当读取一个记录数据时，可以直接访问内存中的内容，而无需去访问文件，提高数据读取效率。

当存储一个记录数据时，只需要通过空闲链表获取一个空闲记录位置编号，根据记录位置编号计算记录所在映射内存中地址，将数据存储到所在地址，接着将该链表节点挂接到记录链表中，并支持按指定的域排序，更新记录数，最后将内存中的数据更新到文件中，当然无需将整个内存数据更新到文件中，只需要更新头信息、映射表和该记录数据，大大提高文件更新速度，同时降低Flash存储器的擦写次数，延长产品的寿命。

当删除一个记录数据时，只需要通过记录链表查找到链表节点，删除记录链表中该记录节点，接着挂接到空闲链表中，更新记录数，最后将内存中的数据更新到文件中，当然无需将整个内存数据更新到文件中，只需要更新头信息、映射表，大大提高文件更新速度，同时降低Flash存储器的擦写次数，延长产品的寿命。

当检索一个记录数据时，只需要通过记录链表查找到链表节点，获取记录位置编号，根据记录位置编号计算记录所在地址，接着根据域信息，判断该记录是否为符合要求的记录，如此将可快速找到需要的记录。

四、软件架构

数据库式存储驱动模块实现结构化的数据记录在文件系统上的存取，并在此基础上实现数据记录的排序、插入、增加以及删除等功能，该程序模块的软件框图如下图6所示。每种数据库占用一个文件，每一个文件都对应有一个与之大小相等映射内存，文件中的数据与内存中的数据是同步的，当应用层需读/写数据库文件时，均要通过映射内存进行中转；即写数据库文件前需先将数据保存在映射内存中，再从映射内存写回数据库文件；反之，读数据记录时只需要读取映射内存中的数据。

驱动对上层应用程序提供了增加记录、删除记录、插入记录等API接口，屏蔽驱动实现细节，同时上层应用程序可以通過数据库注册信息表注册多个文件及文件信息，底层驱动通过数据库注册模块获取应用层注册的文件信息来实现多个文件管理。

五、结语

本研究课题提供了一种嵌入式系统中数据存储和管理的方法，该方法不仅适用于以文件系统文件为存储对象的嵌入式系统，对于直接以Flash存储器为存储对象的嵌入式系统也具有较高指导意义，只要将对文件读写操作更换为对Flash的读写操作。

参考文献

[1] 严蔚敏，吴伟民．数据结构（C语言版） [M]．清华大学出版社，2011．

[2] 杜春雷．ARM体系结构与编程[M]．清华大学出版社，2010．

[3] JEAN J.ABROSSE著，邵贝贝译．UC/OS-II源码公开的实时嵌入式操作系统[M]．中国电力出版社，2001．

[4]SST公司Nor Flash芯片手册．SST Nor Flash Datasheet．

[5]SUMSUNG公司Nand Flash芯片手册，Sumsung Nand Flash Datasheet．

作者简介：叶德焰，厦门雅迅网络股份有限公司中级工程师，研究方向：嵌入式文件系统。

（责任编辑：刘 艳）