基于NorFlash的环形队列式数据存储方法及装置

摘要

本发明提供了一种基于NorFlash的环形队列式数据存储方法及装置，包括：根据待存储数据对应的NorFlash环形队列内的一级索引的取值，确定所述待存储数据对应的二级索引的取值，并根据所述二级索引的取值确定所述待存储数据对应的三级索引的地址；根据所述三级索引的地址内存储的信息，将所述待存储数据存储至所述环形队列的记录区中的对应地址内。通过采用NorFlash环形队列对记录进行存储，在存储记录的过程中突然断电时仅会对当前存储的记录及对应的索引取值产生影响，并不会影响到所有已存储数据的索引取值，从而防止了数据混乱以及无法及时查找数据的现象。

权利要求

1.一种数据存储方法，其特征在于，包括：

根据待存储数据对应的NorFlash环形队列内的一级索引的取值，确定所述待存储数据对应的二级索引的取值，并根据所述二级索引的取值确定所述待存储数据对应的三级索引的地址；

根据所述三级索引的地址内存储的信息，将所述待存储数据存储至所述环形队列的记录区中的对应地址内，其中，所述信息包括所述环形队列的记录区中已存储数据的起始地址，以及所述环形队列的记录区中已存储数据的数量；

所述一级索引的取值由一8位十六进制数表示；

所述根据待存储数据对应的所述环形队列内的一级索引的取值，确定所述待存储数据对应的二级索引的取值，具体包括：将所述一级索引的取值由8位十六进制数转换为32位二进制数；

根据所述32位二进制数中值为0的位的个数，确定所述待存储数据对应的二级索引的地址，所述二级索引的地址内对应的二进制数为所述待存储数据对应的二级索引的取值。

2.根据权利要求1所述的方法，其特征在于，所述信息还包括：所述环形队列的记录区中已存储数据的结束地址。

3.根据权利要求1所述的方法，其特征在于，所述根据所述二级索引的取值确定所述待存储数据对应的三级索引的地址，具体包括：根据所述二级索引的取值，利用如下公式计算所述待存储数据对应的三级索引的地址：y＝(x-1)*8+z

其中，x为所述二级索引的地址，y为所述三级索引的地址，z为所述二级索引的取值中值为0的位的个数。

4.根据权利要求1-3中任一项所述的方法，其特征在于，所述环形队列中还包括索引区，所述索引区包括一级索引区、二级索引区和三级索引区，所述一级索引存储在所述一级索引区内，所述二级索引存储在所述二级索引区内，所述三级索引存储在所述三级索引区内。

5.根据权利要求4所述的方法，其特征在于，所述索引区还包括：版本信息区，所述版本信息区占用4个字节，所述版本信息区内的版本信息用于指示所述环形队列中的不同索引区结构。

6.一种数据存储装置，其特征在于，包括：

位置确定模块，用于根据待存储数据对应的NorFlash环形队列内的一级索引的取值，确定所述待存储数据对应的二级索引的取值，并根据所述二级索引的取值确定所述待存储数据对应的三级索引的地址；

存储模块，用于根据所述三级索引的地址内存储的信息，将所述待存储数据存储至所述环形队列的记录区中的对应地址内，其中，所述信息包括所述环形队列的记录区中已存储数据的起始地址，以及所述环形队列的记录区中已存储数据的数量；

所述一级索引的取值由一8位十六进制数表示；

所述位置确定模块，具体用于：

将所述一级索引的取值由8位十六进制数转换为32位二进制数；

根据所述32位二进制数中值为0的位的个数，确定所述待存储数据对应的二级索引的地址，所述二级索引的地址内对应的二进制数为所述待存储数据对应的二级索引的取值。

7.一种非暂态计算机可读存储介质，其特征在于，所述非暂态计算机可读存储介质存储计算机指令，所述计算机指令使所述计算机执行如权利要求1至5任一所述的方法。

说明书

基于NorFlash的环形队列式数据存储方法及装置

技术领域

[0001] 本发明涉及数据存储技术领域，更具体地，涉及基于NorFlash的环形队列式数据存储方法及装置。

背景技术

[0002] 目前，数据存储技术得到越来越广泛的关注，普遍的做法通常是在单片机上移植文件系统，通过文件系统来管理需要存储的数据。文件系统是操作系统用于明确存储设备或分区上的文件的方法和数据结构，常见的存储设备有磁盘，以及基于NandFlash的固态硬盘等。文件系统由三部分组成：文件系统的接口，对对象操纵和管理的软件集合，对象及属性。从系统角度来看，文件系统是对文件存储设备的空间进行组织和分配，负责文件存储并对存入的文件进行保护和检索的系统。具体地说，它负责为用户建立文件，存入、读出、修改、转储文件，控制文件的存取，当用户不再使用时撤销文件等。

[0003] 采用文件系统来存储数据并对数据进行管理，通用性较强，可以存储管理的数据类型广泛，但是对单片机的资源要求较高，包括对单片机内CPU和存储内存的要求都相对较高。而且文件系统的复杂度较高，不易查找到数据的对应存储位置，可靠性较差，当用户对文件系统内添加新的存储数据添加或对已存储的数据进行修改时，文件系统中对数据的索引(即文件系统内的关键数据)会自动进行修改，此时突然断电极有可能会导致文件系统关键数据的损坏，使整个文件系统发生瘫痪，从而可能导致在文件系统中无法获取到存储的数据。

发明内容

[0004] 为克服上述问题或者至少部分地解决上述问题，本发明提供了一种数据存储方法及装置。

[0005] 一方面，本发明提供了一种数据存储方法，包括：

[0006] 根据待存储数据对应的NorFlash环形队列内的一级索引的取值，确定所述待存储数据对应的二级索引的取值，并根据所述二级索引的取值确定所述待存储数据对应的三级索引的地址；

[0007] 根据所述三级索引的地址内存储的信息，将所述待存储数据存储至所述环形队列的记录区中的对应地址内，其中，所述信息包括所述环形队列的记录区中已存储数据的起始地址，以及所述环形队列的记录区中已存储数据的数量。

[0008] 优选地，所述信息还包括：所述环形队列的记录区中已存储数据的结束地址。

[0009] 优选地，所述一级索引的取值由一8位十六进制数表示。

[0010] 优选地，所述根据待存储数据对应的所述环形队列内的一级索引的取值，确定所述待存储数据对应的二级索引的取值，具体包括：

[0011] 将所述一级索引的取值由8位十六进制数转换为32位二进制数；

[0012] 根据所述32位二进制数中值为0的位的个数，确定所述待存储数据对应的二级索引的地址，所述二级索引的地址内对应的二进制数为所述待存储数据对应的二级索引的取值。

[0013] 优选地，所述根据所述二级索引的取值确定所述待存储数据对应的三级索引的地址，具体包括：

[0014] 根据所述二级索引的取值，利用如下公式计算所述待存储数据对应的三级索引的地址：

[0015] y＝(x-1)*8+z

[0016] 其中，x为所述二级索引的地址，y为所述三级索引的地址，z为所述二级索引的取值中值为0的位的个数。

[0017] 优选地，所述环形队列中还包括索引区，所述索引区包括一级索引区、二级索引区和三级索引区，所述一级索引存储在所述一级索引区内，所述二级索引存储在所述二级索引区内，所述三级索引存储在所述三级索引区内。

[0018] 优选地，所述索引区还包括：版本信息区，所述版本信息区占用4个字节，所述版本信息区内的版本信息用于指示所述环形队列中的不同索引区结构。

[0019] 另一方面，本发明还提供了一种数据存储装置，包括：

[0020] 位置确定模块，用于根据待存储数据对应的NorFlash环形队列内的一级索引的取值，确定所述待存储数据对应的二级索引的取值，并根据所述二级索引的取值确定所述待存储数据对应的三级索引的地址；

[0021] 存储模块，用于根据所述三级索引的地址内存储的信息，将所述待存储数据存储至所述环形队列的记录区中的对应地址内，其中，所述信息包括所述环形队列的记录区中已存储数据的起始地址，以及所述环形队列的记录区中已存储数据的数量。

[0022] 另一方面，本发明还提供了一种计算机程序产品，所述计算机程序产品包括存储在非暂态计算机可读存储介质上的计算机程序，所述计算机程序包括程序指令，当所述程序指令被计算机执行时，使所述计算机执行上述的方法。

[0023] 另一方面，本发明还提供了一种非暂态计算机可读存储介质，所述非暂态计算机可读存储介质存储计算机指令，所述计算机指令使所述计算机执行上述的方法。

[0024] 本发明提供的数据存储方法，通过采用NorFlash环形队列对记录进行存储，在存储记录的过程中突然断电时仅会对当前存储的记录及对应的索引取值产生影响，并不会影响到所有已存储数据的索引取值，从而防止了数据混乱以及无法及时查找数据的现象。并通过设置三个级别的索引区可以快速查找到记录存储的位置，提高了记录的查找效率。

附图说明

[0025] 图1为本发明一实施例提供的一种基于NorFlash的环形队列式数据存储方法的流程示意图；

[0026] 图2为本发明另一实施例提供的一种基于NorFlash的环形队列式数据存储方法中索引区的结构示意图；

[0027] 图3为本发明另一实施例提供的一种基于NorFlash的环形队列式数据存储装置的结构示意图。

具体实施方式

[0028] 下面结合附图和实施例，对本发明的具体实施方式作进一步详细描述。以下实施例用于说明本发明，但不用来限制本发明的范围。

[0029] 目前，NorFlash和NandFlash是市场上两种主要的基于非易失闪存的存储器，Nor Flash可以看做是同步动态随机存储器(Synchronous Dynamic RandomAccess Memory，SDRAM)与NandFlash的中间品，它能像SDRAM一样直接读，还可以像NandFlash一样编程擦写。因此程序可以直接在NorFlash内运行，运行速度要比SDRAM慢一些，向NorFlash内的某一地址内写数据之前必须先将该地址内的数据进行擦除，这是由于NorFlash中的每一比特位只能由1变为0。NorFlash可读但不可直接写的特性可以被用来判断系统中是NorFlash启动还是NandFlash启动，因为NandFlash启动时前4K字节是可写的，但NorFlash启动时前4K字节将不可直接写。

[0030] NorFlash存储器的特点是可以在芯片内执行存储操作，即就地执行(eXecute In Place，XIP)，这样可以使应用程序直接在Flash闪存内运行，不必再将代码读到系统的随机存取存储器(Random-Access Memory，RAM)中。NorFlash的传输效率很高，在1～4MB的小容量时具有很高的成本效益。本发明提供的数据存储方法就是基于NorFlash实现的数据存储方法，利用NorFlash可读不可直接写的特性，在NorFlash上构建环形队列，并利用环形队列上设置的一级索引区、二级索引区和三级索引区实现数据的快速查找。在本发明中，存储的数据主要是以记录的形式进行存储，这里的记录可包括：通话记录、行车记录等。以行车记录为例，一条记录中可以包括车辆行驶时间、在该时间段内的行驶速度等信息。但本发明中数据的存储形式并不限于记录的形式，也可以只是数据的形式或其他存储形式。以下仅以存储的数据为记录的形式为例。

[0031] 如图1所示，本发明一实施例提供了一种基于NorFlash的环形队列式数据存储方法，包括：

[0032] S1，根据待存储数据对应的所述环形队列内的一级索引的取值，确定所述待存储数据对应的二级索引的取值，并根据所述二级索引的取值确定所述待存储数据对应的三级索引的地址；

[0033] S2，根据所述三级索引的地址内存储的信息，将所述待存储数据存储至所述环形队列的记录区中的对应地址内，其中，所述信息包括所述环形队列的记录区中已存储数据的起始地址，以及所述环形队列的记录区中已存储数据的数量。

[0034] 具体地，本发明中采用的NorFlash环形队列由索引区和记录区构成，也就是说，环形队列的索引区和记录区均写在NorFlash上，环形队列的定义信息存储在NorFlash内的程序代码空间，定义信息包括：环形队列的索引区的起始地址(即索引区在NorFlash内的起始地址)、索引区所占的空间大小(即索引区包括的扇区的数量)、记录区的起始地址(即记录区在NorFlash内的起始地址)、记录区所占的空间大小(即记录区包括的扇区的数量)，以及记录区内存储的每条记录的最大长度。

[0035] 本发明中首先根据待存储数据对应的所述环形队列内的一级索引的取值，确定所述待存储数据对应的二级索引的取值，并根据所述二级索引的取值确定所述待存储数据对应的三级索引的地址。由于NorFlash环形队列内在没有存储记录时，环形队列中每一比特位的取值均为1，一般情况下，一级索引的取值为一8位十六进制数表示，所以在没有存储记录时，一级索引的取值(此时为初始值)为0xFFFFFFFF，用32位二进制数表示为11111111111111111111111111111111，当有待存储记录需要存储时，一级索引的32位二进制数取值的某一位上的“1”变为“0”，此时得到的一级索引的取值即为该带存储记录对应的NorFlash环形队列内的一级索引的取值。

[0036] 通过一级索引的取值，可以确定所述待存储数据对应的二级索引的取值，并根据所述二级索引的取值确定所述待存储数据对应的三级索引的地址。在三级索引的地址内存储有环形队列的记录区中已存储数据的起始地址，以及环形队列的记录区中已存储数据的数量。根据已存储数据的起始地址，以及环形队列的记录区中已存储数据的数量，即可计算出该待存储记录在记录区中的存储位置。这是由于，在记录区内存储记录时，存储的地址是连续的，环形队列的记录区通常为每条记录提供一个固定长度的存储空间，例如固定长度为128字节。当已知当前记录区中已存储数据的起始地址和已存储数据的数量，即可通过计算得到该待存储记录存储的地址，具体方法可以为：计算固定长度与已存储数据的数量的乘积，再与起始地址相加即可得到。

[0037] 计算得到该待存储记录存储的地址后，即可将其存储至所述环形队列的记录区中的对应地址内，这里的对应地址即是通过计算得到的待存储记录应该存储的位置。

[0038] 本实施例中，通过采用NorFlash环形队列对记录进行存储，在存储记录的过程中突然断电时仅会对当前存储的记录及对应的索引取值产生影响，并不会影响到所有已存储数据的索引取值，从而防止了数据混乱以及无法及时查找数据的现象。并通过设置三个级别的索引区可以快速查找到记录存储的位置，提高了记录的查找效率。

[0039] 在上述实施例的基础上，所述信息还包括：所述环形队列的记录区中已存储数据的结束地址。具体地，可直接从已存储数据的结束地址开始存储待存储记录，可以进一步加快记录的存储速度。

[0040] 在上述实施例的基础上，本发明中环形队列的索引区包括一级索引区、二级索引区和三级索引区，所述一级索引存储在所述一级索引区内，所述二级索引存储在所述二级索引区内，所述三级索引存储在所述三级索引区内。

[0041] 在上述实施例的基础上，本发明中环形队列的索引区由一定数量的连续索引扇区组成。每个索引扇区内包括至少一个一级索引区、一个二级索引区和一个三级索引区。索引区的索引扇区数量由环形队列定义时决定(即在程序编码时由环形队列使用者在代码空间定义)，可以通过实际需求计算权衡得出。计算的目标是：环形队列在报废前由于记录对应的索引的写入而导致的索引扇区的擦除次数应该小于NorFlash内扇区的擦除寿命(擦除寿命一般在10万次左右)。环形队列的记录区用于存储具体的记录，由一定数量的连续记录扇区组成。记录区的起始地址、占用空间、每条记录的最大长度都在程序代码中定义。记录区的扇区数量与索引区扇区数量类似，均由实际需求计算权衡得出，计算目标也是一致的，为：环形队列在报废前由于记录的写入而导致的记录扇区的擦除次数应该小于NorFlash内扇区的擦除寿命。

[0042] 在上述实施例的基础上，索引扇区的主要作用是保存环形队列的当前索引信息项。当前索引信息项包括：当前记录数量、当前首记录地址和当前尾记录地址。通过当前索引信息项可以直接在记录区找到对应的地址对记录进行读取或者添加、删除。每次对环形队列记录的添加和删除都会使当前记录数量、当前首记录地址或当前尾记录地址发生变化，即当前索引信息项发生变化。变化的信息需要保存到NorFlash中，由于NorFlash在不进行擦除的情况下只由1写成0而不能由0写成1。所以，变化的信息在不擦除索引扇区的情况下不能保存到记录区的原有地址内，需要另寻地址保存。

[0043] 在上述实施例的基础上，由于采用了环形队列，当需要对已存储记录进行修改时，可以不用对已存储在记录区内对应地址内的原始记录进行擦除并写入修改后的记录，可以直接为修改后的记录赋予一个新的一级索引值和二级索引值，根据二级索引值确定对应的三级索引的地址，并根据三级索引的地址内存储的信息，将修改后的记录存储至所述环形队列的记录区中的对应地址内。

[0044] 当需要向环形队列的记录区内添加新的记录时，直接为新的记录赋予一个一级索引值和二级索引值，根据二级索引值确定对应的三级索引的地址，并根据三级索引的地址内存储的信息，将新的记录存储至所述环形队列的记录区中的对应地址内。

[0045] 当需要对已存储记录进行删除时，可以不用对已存储在记录区内对应地址内的记录内容进行擦除，而是可以直接将待删除的记录对应的三级索引的地址内存储的信息进行修改即可。

[0046] 本实施例中，由于采用环形队列，存储的首记录和尾记录相邻，可以充分利用环形队列的索引扇区和记录区，当当前索引扇区的索引区被完整利用，需要更换到下一个索引扇区，才能保存新的索引信息项。在切换到新的索引扇区时要先对新的索引扇区进行擦除以确保整个索引扇区可正常写入，当切换到本环形队列的最后一个索引扇区并且也已完整利用后就需要回到本环形队列的第一个索引扇区，擦除后开始使用，如此循环往复。

[0047] 在上述实施例的基础上，为了加快查找记录的速度，索引区采用了三个级别的索引设计。为了减少对索引扇区的擦除次数，每一索引区充分利用了NorFlash可以将单个比特位由1写为0的特性，利用值为0的位的数量来进行二级索引和三级索引。

[0048] 在上述实施例的基础上，当前索引信息项保存在三级索引区，三级索引区共有256块，每次索引信息项的变更依次保存在三级索引区的不同块中。如原本索引信息项保存在块1中，当添加一条记录后当前索引信息项的值将保存在块2中，再添加一条记录后当前索引信息项的值将保存在块3中。如此依次进行存储。

[0049] 在上述实施例的基础上，本发明中的一级索引区占用4字节共32位，二级索引区占用32字节共256位，三级索引区共256块，每块12字节共3072字节，其中，每块中的12个字节中4个字节用于存储当前索引信息项的当前记录数量，4个字节用于存储当前首记录地址，最后4个字节用于存储当前尾记录地址。

[0050] 在上述实施例的基础上，索引区还包括：保留区，所示保留区占用984个字节。

[0051] 在上述实施例的基础上，索引区还包括：版本信息区，所述版本信息区占用4个字节，所述版本信息区内的版本信息用于指示所述环形队列中的不同索引区结构；相应地，环形队列的定义信息还包括：索引区的版本信息。

[0052] 具体地，版本信息可用于后续对索引区结构的升级，版本信息为占用4个字节的版本号，当索引区的结构有所调整时可以修改这4个字节的内容，程序可以通过这4字节的内容来采用不同的构造方法。如第一版本时V＝1，那么索引结构如图2所示。图中A代表一级索引，B代表二级索引，其中Bx代表二级索引的地址为第x个字节，Cx代表三级索引的地址为第x项。当发现二级索引的位置不够用需要增加时，可以将版本V修改为2，程序需要通过V的值来确定采用哪种方式来访问索引，使新程序能够同时兼容不同版本的索引结构。

[0053] 在上述实施例的基础上，所述根据待存储数据对应的所述环形队列内的一级索引的取值，确定所述待存储数据对应的二级索引的取值，具体包括：

[0054] 将所述一级索引的取值由8位十六进制数转换为32位二进制数；

[0055] 根据所述32位二进制数中值为0的位的个数，确定所述待存储数据对应的二级索引的地址，所述二级索引的地址内对应的二进制数为所述待存储数据对应的二级索引的取值。

[0056] 具体地，例如某一记录的一级索引的取值为0xFFFFFFFC，转换为32位二进制数为11111111111111111111111111111100，其中值为0的位的个数为2，则该记录对应的二级索引的地址为B2，B2内存储的二进制数即为该记录对应的二级索引的取值；如果某一记录的一级索引的取值值为0xFFFFFFF8，转换为32位二进制数为111111111111111111111111111
11000，其中值为0的位的个数为3，则该记录对应的二级索引的地址为B3，B3内存储的二进制数即为该记录对应的二级索引的取值。

[0057] 在上述实施例的基础上，所述根据所述二级索引的取值确定所述待存储数据对应的三级索引的地址，具体包括：

[0058] 根据所述二级索引的取值，利用如下公式计算所述待存储数据对应的三级索引的地址：

[0059] y＝(x-1)*8+z

[0060] 其中，x为所述二级索引的地址，y为所述三级索引的地址，z为所述二级索引的取值中值为0的位的个数。

[0061] 例如，如果某一记录对应的一级索引的取值为0xFFFFFFFC，二进制数中值为0的位的个数为2，则该记录对应的二级索引的地址为B2，若B2内存储的十六进制数为0xF8，对应的二进制数中值为0的位的个数等于3，则该记录对应的三级索引的地址为C11，最后通过C11内存储的信息可以直接确定该记录应该存储在环形队列中记录区的哪一地址。

[0062] 如图3所示，在上述实施例的基础上，本发明还提供了一种基于NorFlash的环形队列式数据存储装置，包括：位置确定模块31和存储模块32。其中，

[0063] 位置确定模块31用于根据待存储数据对应的所述环形队列内的一级索引的取值，确定所述待存储数据对应的二级索引的取值，并根据所述二级索引的取值确定所述待存储数据对应的三级索引的地址；

[0064] 存储模块32用于根据所述三级索引的地址内存储的信息，将所述待存储数据存储至所述环形队列的记录区中的对应地址内，其中，所述信息包括所述环形队列的记录区中已存储数据的起始地址，以及所述环形队列的记录区中已存储数据的数量。

[0065] 本实施例中提供的数据存储装置与上述数据存储方法类实施例是一一对应的，本实施例在此不再赘述。

[0066] 在上述实施例的基础上，本发明还提供了一种计算机程序产品，所述计算机程序产品包括存储在非暂态计算机可读存储介质上的计算机程序，所述计算机程序包括程序指令，当所述程序指令被计算机执行时，使所述计算机执行上述的方法。

[0067] 在上述实施例的基础上，本发明还提供了一种非暂态计算机可读存储介质，所述非暂态计算机可读存储介质存储计算机指令，所述计算机指令使所述计算机执行上述的方法。

[0068] 最后，本发明的方法仅为较佳的实施方案，并非用于限定本发明的保护范围。凡在本发明的精神和原则之内，所作的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。