技术领域Technical Field
本发明涉及数据库技术领域，尤其涉及一种键值对数据库的存储方法。The present invention relates to the technical field of databases, and in particular to a storage method for a key-value pair database.
背景技术Background technique
目前Flash（闪存）存储广泛应用于手机、平板电脑、SSD等电子设备之中，Flash数据库将日志存入闪存数据库中扇区中，以实现对日志的高效存储。现有的Flash存储方法对于参数、配置信息、动态数据等数据的存储主要采用结构体记录，首先需要对每个模块分配一个或者多个扇区，并在每个扇区中存储不同类型的数据；在运行期间，当扇区中的其中一个参数变化时，就需要先将该扇区的数据读到ram(随机存取存储器）中，并将该扇区的数据擦除，最后将ram内的参数进行变更后再全部写入该扇区。At present, Flash storage is widely used in electronic devices such as mobile phones, tablets, SSDs, etc. Flash database stores logs in sectors in the Flash database to achieve efficient storage of logs. The existing Flash storage method mainly uses structure records for the storage of parameters, configuration information, dynamic data and other data. First, one or more sectors need to be allocated to each module, and different types of data need to be stored in each sector; during operation, when one of the parameters in the sector changes, the data of the sector needs to be read into the RAM (random access memory) first, and the data of the sector needs to be erased, and finally the parameters in the RAM need to be changed and then all written to the sector.
当应用现有的Flash存储方法的数据库的扇区中的参数数据会经常变动时，该扇区需要反复擦写，其不仅会导致Flash存储用时过长，还会降低扇区的使用寿命；另外，现有的Flash存储方法在改变参数的顺序或者增加参数的数量时，需要考虑对之前已经存入的参数数据是否产生影响；此外，现有的Flash存储方法需要分扇区存储，以对不同项目或者参数类型的数据进行分区存储，降低擦写扇区的时间，因此技术人员需要编写代码对各个扇区进行规划分配，其导致数据库维护困难。When the parameter data in the sector of the database using the existing Flash storage method changes frequently, the sector needs to be repeatedly erased and written, which not only causes the Flash storage to take too long, but also reduces the service life of the sector; in addition, when the existing Flash storage method changes the order of parameters or increases the number of parameters, it is necessary to consider whether the previously stored parameter data will be affected; in addition, the existing Flash storage method requires sector storage to partition and store data of different projects or parameter types to reduce the time for erasing sectors. Therefore, technicians need to write code to plan and allocate each sector, which makes database maintenance difficult.
发明内容Summary of the invention
本发明所要解决的技术问题是：提供一种键值对数据库的存储方法，以解决现有的Flash存储方法擦写时间长、维护困难与影响Flash寿命的问题。The technical problem to be solved by the present invention is to provide a storage method for a key-value pair database to solve the problems of long erasing time, difficult maintenance and affecting the life of the Flash in the existing Flash storage method.
为了解决上述技术问题，本发明采用的技术方案为：一种键值对数据库的存储方法，包括步骤：In order to solve the above technical problems, the technical solution adopted by the present invention is: a storage method of a key-value pair database, comprising the steps of:
S1：构建字典树，遍历键值对条目，根据各个所述键值对条目的键名分别构建索引字符串，所述索引字符串插入所述字典树中，并在所述索引字符串的叶子节点写入指向对应所述键值对条目的存储地址的地址字段；S1: construct a dictionary tree, traverse the key-value pair entries, construct index strings according to the key names of the key-value pair entries, insert the index strings into the dictionary tree, and write an address field pointing to the storage address corresponding to the key-value pair entry in the leaf node of the index string;
S2：根据待写入键值对的键名查询所述字典树中是否存在相匹配的所述索引字符串；若是，则进入步骤S3；若否，则进入步骤S4;S2: query the dictionary tree according to the key name of the key-value pair to be written whether there is a matching index string; if so, proceed to step S3; if not, proceed to step S4;
S3：根据所述待写入键值对创建新的键值对条目，根据待写入键值对的键名查询所得的索引字符串的所述叶子节点的地址字段更新为指向所述新的键值对条目的存储地址；S3: creating a new key-value pair entry according to the key-value pair to be written, and updating the address field of the leaf node of the index string obtained by querying the key name of the key-value pair to be written to point to the storage address of the new key-value pair entry;
S4：根据所述待写入键值对的键名构建新的索引字符串，所述新的索引字符串插入所述字典树中，根据所述待写入键值对创建新的键值对条目，所述新的索引字符串的叶子节点写入指向所述新的键值对条目的存储地址的地址字段。S4: construct a new index string according to the key name of the key-value pair to be written, insert the new index string into the dictionary tree, create a new key-value pair entry according to the key-value pair to be written, and write the address field pointing to the storage address of the new key-value pair entry into the leaf node of the new index string.
进一步的，所述字典树的节点存储于可变数组中，以使所述字典树根据所述节点的子节点的数量动态调整所述可变数组的长度。Furthermore, the nodes of the dictionary tree are stored in a variable array, so that the dictionary tree dynamically adjusts the length of the variable array according to the number of child nodes of the node.
进一步的，所述步骤S3包括步骤：Furthermore, the step S3 comprises the steps of:
所述待写入键值对的键值的数据与相匹配的所述键值对条目的键值的数据进行对比，判断两者的长度与内容是否一致；若是，根据待写入键值对的键名查询所得的索引字符串的所述叶子节点不更新；若否，根据所述待写入键值对创建新的键值对条目，根据待写入键值对的键名查询所得的索引字符串的所述叶子节点的地址字段更新为指向所述新的键值对条目的存储地址，并且相匹配的所述键值对条目的状态标记为删除状态。The data of the key value of the key-value pair to be written is compared with the data of the key value of the matching key-value pair entry to determine whether the length and content of the two are consistent; if so, the leaf node of the index string obtained by querying the key name of the key-value pair to be written is not updated; if not, a new key-value pair entry is created based on the key-value pair to be written, and the address field of the leaf node of the index string obtained by querying the key name of the key-value pair to be written is updated to point to the storage address of the new key-value pair entry, and the status of the matching key-value pair entry is marked as deleted.
进一步的，所述步骤S1包括步骤：Furthermore, the step S1 comprises the steps of:
S101：判断第一扇区是否格式化；若否，进入步骤S102；若是，进入步骤S103；S101: Determine whether the first sector is formatted; if not, proceed to step S102; if yes, proceed to step S103;
S102：将所有扇区格式化；S102: Format all sectors;
S103：构建字典树；S103: Construct a dictionary tree;
S104：从第一扇区的第一条键值对条目开始，依次遍历所有扇区的所有键值对条目；S104: starting from the first key-value pair entry of the first sector, traverse all key-value pair entries of all sectors in sequence;
S105：判断所述键值对条目是否有效；若是，进入步骤S106；若否，进入步骤S107；S105: Determine whether the key-value pair entry is valid; if so, proceed to step S106; if not, proceed to step S107;
S106：根据所述键值对条目的键名构建索引字符串，所述索引字符串插入所述字典树中，并在所述索引字符串的叶子节点写入指向所述键值对条目的存储地址的地址字段；S106: construct an index string according to the key name of the key-value pair entry, insert the index string into the dictionary tree, and write an address field pointing to the storage address of the key-value pair entry into the leaf node of the index string;
S107：判断是否所有扇区的所有键值对条目遍历完成；若是，开始遍历下一条未遍历的键值对条目；若否，完成初始化。S107: Determine whether the traversal of all key-value pair entries of all sectors is complete; if so, start traversing the next untraversed key-value pair entry; if not, complete the initialization.
进一步的，将所有扇区格式化包括：在所有扇区的头部分别写入相应的扇区信息，并且获取起始扇区；其中，所述扇区信息包括用于检查扇区是否格式化的第一魔数信息与用于检查扇区的状态的第一标志位。Further, formatting all sectors includes: writing corresponding sector information in the headers of all sectors respectively, and obtaining the starting sector; wherein the sector information includes first magic number information for checking whether the sector is formatted and a first flag bit for checking the status of the sector.
进一步的，还包括步骤S5：判断剩余空间是否小于预设阈值；若是，回收起始扇区；若否，不回收起始扇区。Furthermore, the method further includes step S5: determining whether the remaining space is less than a preset threshold; if so, reclaiming the starting sector; if not, not reclaiming the starting sector.
进一步的，回收起始扇区包括步骤：Furthermore, reclaiming the starting sector includes the steps of:
S501：遍历起始扇区中的所有键值对条目；S501: traverse all key-value pair entries in the starting sector;
S502：判断所述键值对条目是否有效；若是，进入步骤S503；若否，进入步骤S504；S502: Determine whether the key-value pair entry is valid; if so, proceed to step S503; if not, proceed to step S504;
S503：在起始扇区之外的其他扇区中创建迁移键值对条目，所述键值对条目的数据拷贝至所述迁移键值对条目中，与所述键值对条目相匹配的索引字符串的叶子节点的地址字段更新为指向所述迁移键值对条目的存储地址，所述键值对条目的状态标记为删除状态；S503: creating a migration key-value pair entry in other sectors other than the starting sector, copying the data of the key-value pair entry to the migration key-value pair entry, updating the address field of the leaf node of the index string matching the key-value pair entry to point to the storage address of the migration key-value pair entry, and marking the status of the key-value pair entry as a deleted status;
S504：判断是否所述起始扇区的所述键值对条目遍历完成；若否，开始遍历所述起始扇区中的下一条所述键值对条目；若是，擦除起始扇区，并以所述起始扇区的下一个扇区作为新的起始扇区。S504: Determine whether the traversal of the key-value pair entries in the starting sector is completed; if not, start traversing the next key-value pair entry in the starting sector; if so, erase the starting sector and use the next sector of the starting sector as a new starting sector.
进一步的，所述预设阈值包括第一预设阈值和第二预设阈值，第一预设阈值小于第二预设阈；其中，第一预设阈值用于创建新的键值对条目时判断是否触发回收起始扇区，第二预设阈值用于空闲时判断是否触发回收起始扇区值。Furthermore, the preset threshold includes a first preset threshold and a second preset threshold, and the first preset threshold is smaller than the second preset threshold; wherein the first preset threshold is used to determine whether to trigger the recovery of the starting sector when creating a new key-value pair entry, and the second preset threshold is used to determine whether to trigger the recovery of the starting sector value when idle.
进一步的，所述键值对条目包括：第二标志位、第二魔数信息、数据总长度信息、循环冗余校验码、字符串长度、数据长度、键名和键值数据。Furthermore, the key-value pair entry includes: a second flag bit, a second magic number information, total data length information, a cyclic redundancy check code, a string length, a data length, a key name and a key value data.
进一步的，还包括步骤S6：Furthermore, the method further comprises step S6:
根据应用层请求的待读键值对键名，查找所述字典树中是否存在相匹配的所述索引字符串；若是，根据待读键值对键名查询所得的索引字符串的叶子节点存储的地址字段读取相匹配的键值对条目，并将相匹配的键值对条目发送至所述应用层；若否，返回无键值对条目信息至所述应用层。According to the key name of the key-value pair to be read requested by the application layer, check whether there is a matching index string in the dictionary tree; if so, read the matching key-value pair entry from the address field stored in the leaf node of the index string obtained by querying the key name of the key-value pair to be read, and send the matching key-value pair entry to the application layer; if not, return the information that there is no key-value pair entry to the application layer.
本发明的有益效果在于：本发明所述的这种存储方法利用字典树对数据库中的键值对条目起到索引作用，在实际应用时仅需尽可能分配较多的扇区给数据库，以使数据库具有较大的存储区域，并且在使用Flash的过程中，仅需对键值对条目进行增加或者删除，而无需对整个扇区进行擦写，该存储方法不仅有益于降低数据库维护的难度，还可以避免数据库反复擦写扇区而降低扇区的使用寿命。The beneficial effects of the present invention are as follows: the storage method described in the present invention utilizes a dictionary tree to index key-value pair entries in a database. In actual application, it is only necessary to allocate as many sectors as possible to the database so that the database has a larger storage area. In the process of using Flash, it is only necessary to add or delete key-value pair entries without erasing the entire sector. This storage method is not only beneficial in reducing the difficulty of database maintenance, but also can avoid repeatedly erasing sectors in the database and reducing the service life of the sectors.
附图说明BRIEF DESCRIPTION OF THE DRAWINGS
图1为本发明所述的键值对数据库的存储方法在一种实施方式中的流程示意图；FIG1 is a schematic diagram of a flow chart of a storage method for a key-value pair database according to an embodiment of the present invention;
图2为本发明所述的键值对数据库的存储方法在一种实施方式中步骤S1的流程示意图；FIG2 is a schematic flow chart of step S1 of the key-value pair database storage method according to one embodiment of the present invention;
图3为本发明所述的键值对数据库的存储方法在一种实施方式中步骤S2的流程示意图；FIG3 is a schematic flow chart of step S2 of the key-value pair database storage method according to one embodiment of the present invention;
图4为本发明所述的键值对数据库的存储方法在一种实施方式中步骤S3的流程示意图；FIG4 is a schematic flow chart of step S3 of the key-value pair database storage method according to one embodiment of the present invention;
图5为本发明所述的键值对数据库的存储方法在一种实施方式中步骤S4的流程示意图；FIG5 is a schematic flow chart of step S4 of the key-value pair database storage method according to one embodiment of the present invention;
图6为示意性地展示了本发明所述的存储方法中字典树的结构图；FIG6 is a diagram schematically showing the structure of a dictionary tree in the storage method of the present invention;
图7为示意性地展示了本发明所述的存储方法中字典树插入新增的索引字符串的原理图。FIG. 7 is a schematic diagram showing the principle of inserting a newly added index string into a dictionary tree in the storage method of the present invention.
具体实施方式Detailed ways
为详细说明本发明的技术内容、所实现目的及效果，以下结合实施方式并配合附图予以说明。In order to explain the technical content, achieved objectives and effects of the present invention in detail, the following is an explanation in conjunction with the implementation modes and the accompanying drawings.
本发明提供一种键值对数据库的存储方法，包括步骤：The present invention provides a storage method for a key-value pair database, comprising the steps of:
S1：构建字典树，遍历键值对条目，根据各个所述键值对条目的键名分别构建索引字符串，所述索引字符串插入所述字典树中，并在所述索引字符串的叶子节点写入指向对应所述键值对条目的存储地址的地址字段；S1: construct a dictionary tree, traverse the key-value pair entries, construct index strings according to the key names of the key-value pair entries, insert the index strings into the dictionary tree, and write an address field pointing to the storage address corresponding to the key-value pair entry in the leaf node of the index string;
S2：根据待写入键值对的键名查询所述字典树中是否存在相匹配的所述索引字符串；若是，则进入步骤S3；若否，则进入步骤S4;S2: query the dictionary tree according to the key name of the key-value pair to be written whether there is a matching index string; if so, proceed to step S3; if not, proceed to step S4;
S3：根据所述待写入键值对创建新的键值对条目，根据待写入键值对的键名查询所得的索引字符串的所述叶子节点的地址字段更新为指向所述新的键值对条目的存储地址；S3: creating a new key-value pair entry according to the key-value pair to be written, and updating the address field of the leaf node of the index string obtained by querying the key name of the key-value pair to be written to point to the storage address of the new key-value pair entry;
S4：根据所述待写入键值对的键名构建新的索引字符串，所述新的索引字符串插入所述字典树中，根据所述待写入键值对创建新的键值对条目，所述新的索引字符串的叶子节点写入指向所述新的键值对条目的存储地址的地址字段。S4: construct a new index string according to the key name of the key-value pair to be written, insert the new index string into the dictionary tree, create a new key-value pair entry according to the key-value pair to be written, and write the address field pointing to the storage address of the new key-value pair entry into the leaf node of the new index string.
本发明的工作原理简述如下：应用本发明提供的这种键值对数据库的存储方法，其无需根据键值对数据库的所属项目或者参数类型来规划分配扇区，仅需统一分配多个扇区给键值对数据库，以使多个扇区共同形成键值对数据库一块完整的并且具有较大存储空间的存储区域，键值对条目中包括键名和键值，其中键值可以存储有任意项目、任意参数类型的数据。The working principle of the present invention is briefly described as follows: by applying the storage method of the key-value pair database provided by the present invention, it is not necessary to plan and allocate sectors according to the project or parameter type to which the key-value pair database belongs. It is only necessary to uniformly allocate multiple sectors to the key-value pair database so that the multiple sectors together form a complete storage area of the key-value pair database with a larger storage space. The key-value pair entry includes a key name and a key value, wherein the key value can store data of any project and any parameter type.
在设备初次上电或者复位时，所有扇区均进行格式化处理，以清除各个扇区中的无效数据，并且将键值对数据写入数据库中，构建字典树，并依次遍历键值对数据库中所有键值对条目，根据所有键值对条目的键名构建索引字符串，索引字符串插入字典树中，并且索引字符串的叶子节点写入指向对应的键值对条目的存储地址的地址字段；键值对数据库可以根据字典树的索引字符串来查询对应的键值对条目的存储地址，再读取对应的键值对条目的存储地址中存储的数据。When the device is powered on or reset for the first time, all sectors are formatted to clear invalid data in each sector, and the key-value pair data is written into the database, a dictionary tree is constructed, and all key-value pair entries in the key-value pair database are traversed in turn, and an index string is constructed according to the key names of all key-value pair entries. The index string is inserted into the dictionary tree, and the leaf node of the index string is written to the address field pointing to the storage address of the corresponding key-value pair entry; the key-value pair database can query the storage address of the corresponding key-value pair entry according to the index string of the dictionary tree, and then read the data stored in the storage address of the corresponding key-value pair entry.
应用该存储方法的键值对数据库在更改键值对条目的键值中存储的数据时，仅需创建新的键值对条目，并且修改与其相匹配的索引字符串的叶子节点的地址字段，其仅需在键值对数据库中写入新的键值对条目，而无需对整个扇区进行擦写，该存储方法可以有效提高键值对数据库更改参数数据的效率。When changing the data stored in the key value of a key-value pair entry, the key-value pair database that applies this storage method only needs to create a new key-value pair entry and modify the address field of the leaf node of the index string that matches it. It only needs to write the new key-value pair entry in the key-value pair database without erasing the entire sector. This storage method can effectively improve the efficiency of changing parameter data in the key-value pair database.
由上述描述可知，本发明的有益效果在于：本发明所述的这种存储方法利用字典树对键值对数据库中的键值对条目起到索引作用，在实际应用时仅需尽可能分配较多的扇区给键值对数据库，以使键值对数据库具有较大的存储区域，并且在使用Flash的过程中，仅需对键值对条目进行增加或者删除，而无需对整个扇区进行擦写，该存储方法不仅有益于降低键值对数据库维护的难度，还可以避免键值对数据库反复擦写扇区而降低扇区的使用寿命。From the above description, it can be seen that the beneficial effect of the present invention is that: the storage method described in the present invention uses a dictionary tree to index the key-value pair entries in the key-value pair database. In actual application, it is only necessary to allocate as many sectors as possible to the key-value pair database so that the key-value pair database has a larger storage area, and in the process of using Flash, it is only necessary to add or delete the key-value pair entries without erasing the entire sector. This storage method is not only beneficial to reducing the difficulty of maintaining the key-value pair database, but also can avoid the key-value pair database from repeatedly erasing sectors and reducing the service life of the sectors.
进一步的，所述字典树的节点存储于可变数组中，以使所述字典树根据所述节点的子节点的数量动态调整所述可变数组的长度。Furthermore, the nodes of the dictionary tree are stored in a variable array, so that the dictionary tree dynamically adjusts the length of the variable array according to the number of child nodes of the node.
由上述描述可知，当所述字典树的其中一个节点增加子节点时，字典树对该节点重新动态分配，其可以有效减小字典树的ram内存占用空间。It can be seen from the above description that when a child node is added to one of the nodes of the dictionary tree, the dictionary tree dynamically reallocates the node, which can effectively reduce the RAM memory space occupied by the dictionary tree.
进一步的，所述步骤S3包括步骤：Furthermore, the step S3 comprises the steps of:
所述待写入键值对的键值的数据与相匹配的所述键值对条目的键值的数据进行对比，判断两者的长度与内容是否一致；若是，根据待写入键值对的键名查询所得的索引字符串的所述叶子节点不更新；若否，根据所述待写入键值对创建新的键值对条目，根据待写入键值对的键名查询所得的索引字符串的所述叶子节点的地址字段更新为指向所述新的键值对条目的存储地址，并相匹配的键值对条目的状态标记为删除状态。The data of the key value of the key-value pair to be written is compared with the data of the key value of the matching key-value pair entry to determine whether the length and content of the two are consistent; if so, the leaf node of the index string obtained by querying the key name of the key-value pair to be written is not updated; if not, a new key-value pair entry is created based on the key-value pair to be written, and the address field of the leaf node of the index string obtained by querying the key name of the key-value pair to be written is updated to point to the storage address of the new key-value pair entry, and the status of the matching key-value pair entry is marked as deleted.
由上述描述可知，当待写入键值对的键值数据与键值对数据库中现存的键值对条目的键值数据一致时，则可以不对键值对数据库与字典树做修改，可以节省数据库的无效写入时间、节省存储空间，并且减少Flash擦写次数，以延长Flash使用寿命。From the above description, it can be seen that when the key-value data of the key-value pair to be written is consistent with the key-value data of the existing key-value pair entry in the key-value pair database, the key-value pair database and the dictionary tree do not need to be modified, which can save invalid writing time of the database, save storage space, and reduce the number of Flash erases to extend the service life of the Flash.
进一步的，所述步骤S1包括步骤：Furthermore, the step S1 comprises the steps of:
S101：判断第一扇区是否格式化；若否，进入步骤S102；若是，进入步骤S103；S101: Determine whether the first sector is formatted; if not, proceed to step S102; if yes, proceed to step S103;
S102：将所有扇区格式化；S102: Format all sectors;
S103：构建字典树；S103: Construct a dictionary tree;
S104：从第一扇区的第一条键值对条目开始，依次遍历所有扇区的所有键值对条目；S104: starting from the first key-value pair entry of the first sector, traverse all key-value pair entries of all sectors in sequence;
S105：判断所述键值对条目是否有效；若是，进入步骤S106；若否，进入步骤S107；S105: Determine whether the key-value pair entry is valid; if so, proceed to step S106; if not, proceed to step S107;
S106：根据所述键值对条目的键名构建索引字符串，所述索引字符串插入所述字典树中，并在所述索引字符串的叶子节点写入指向所述键值对条目的存储地址的地址字段；S106: construct an index string according to the key name of the key-value pair entry, insert the index string into the dictionary tree, and write an address field pointing to the storage address of the key-value pair entry into the leaf node of the index string;
S107：判断是否所有扇区的所有键值对条目遍历完成；若是，开始遍历下一条未遍历的键值对条目；若否，完成初始化。S107: Determine whether the traversal of all key-value pair entries of all sectors is complete; if so, start traversing the next untraversed key-value pair entry; if not, complete the initialization.
由上述描述可知，步骤S1是对键值对数据库进行初始化，以根据键值对数据库内现有的数据创建出一个字典树。该存储方法在初始化过程中，遍历键值对数据库中所有的键值对条目，根据键值对条目的键名构建索引字符串，并将索引字符串插入字典树中，因此字典树内的节点个数与现有的键值对个数和键值对中名称的长度有关。As can be seen from the above description, step S1 is to initialize the key-value database to create a dictionary tree based on the existing data in the key-value database. During the initialization process, the storage method traverses all key-value pair entries in the key-value database, builds an index string based on the key name of the key-value pair entry, and inserts the index string into the dictionary tree. Therefore, the number of nodes in the dictionary tree is related to the number of existing key-value pairs and the length of the name in the key-value pair.
另外，该存储方法通过创建字典树对所有扇区的所有键值对条目进行索引，以使得键值对数据库可以无需对根据项目或者参数类型来划分扇区，所有扇区组合形成一块较大的存储空间给键值对数据库驱动，并且在该存储空间中可以随意增加和删减参数，其使得技术人员不需要规划存储扇区的分配，其可以降低技术人员编写代码的难度，减少技术人员工作量。In addition, the storage method indexes all key-value pair entries of all sectors by creating a dictionary tree, so that the key-value pair database does not need to be divided into sectors according to project or parameter type. All sectors are combined to form a larger storage space for the key-value pair database driver, and parameters can be added and deleted in the storage space at will, which makes it unnecessary for technicians to plan the allocation of storage sectors, which can reduce the difficulty of technicians in writing code and reduce the workload of technicians.
进一步的，将所有扇区格式化包括：在所有扇区的头部分别写入相应的扇区信息，并且获取起始扇区；其中，所述扇区信息包括用于检查扇区是否格式化的第一魔数信息与用于检查扇区的状态的第一标志位。Further, formatting all sectors includes: writing corresponding sector information in the headers of all sectors respectively, and obtaining the starting sector; wherein the sector information includes first magic number information for checking whether the sector is formatted and a first flag bit for checking the status of the sector.
由上述描述可知，在扇区的头部写入扇区信息，可以根据扇区信息检查扇区的状态，具体的，识别第一魔数信息可以检查该扇区是否已格式化；扇区信息还根据扇区擦写时每个字节可以独立写一次的特点设置了第一标志位，以第一标志位判断扇区的当前状态，例如：判断扇区中是否存在空余空间写入新的键值对条目、扇区中是否存在无效数据。起始扇区就是第一个不为空的扇区，因为Flash是循环使用的，易于理解的：当Flash中共有10个扇区并且各个扇区依次顺序编号时，可能会出现以下情况，第一扇区和第二扇区为空，第三至第九扇区写满，第十扇区写入部分空间，则此时，第三扇区就是起始扇区。From the above description, it can be known that the sector information is written in the header of the sector, and the status of the sector can be checked according to the sector information. Specifically, the identification of the first magic number information can check whether the sector has been formatted; the sector information also sets the first flag bit according to the characteristic that each byte can be written independently once when the sector is erased, and the current status of the sector is judged by the first flag bit, for example: judging whether there is free space in the sector to write a new key-value pair entry, and whether there is invalid data in the sector. The starting sector is the first non-empty sector, because Flash is used cyclically, which is easy to understand: when there are 10 sectors in Flash and each sector is numbered in sequence, the following situation may occur: the first and second sectors are empty, the third to ninth sectors are full, and the tenth sector is written to part of the space. In this case, the third sector is the starting sector.
进一步的，还包括步骤S5：判断剩余空间是否小于预设阈值；若是，回收起始扇区；若否，不回收起始扇区。Furthermore, the method further includes step S5: determining whether the remaining space is less than a preset threshold; if so, reclaiming the starting sector; if not, not reclaiming the starting sector.
由上述描述可知，当键值对数据库的剩余空间不足时，该存储方法可以自动回收起始扇区的空间，将起始扇区中有效的键值对条目进行迁移，以及将标记为删除的键值对条目从Flash中擦除。From the above description, it can be seen that when the remaining space of the key-value database is insufficient, the storage method can automatically reclaim the space of the starting sector, migrate the valid key-value entries in the starting sector, and erase the key-value entries marked for deletion from the Flash.
进一步的，回收起始扇区包括步骤：Furthermore, reclaiming the starting sector includes the steps of:
S501：遍历起始扇区中的所有键值对条目；S501: traverse all key-value pair entries in the starting sector;
S502：判断所述键值对条目是否有效；若是，进入步骤S503；若否，进入步骤S504；S502: Determine whether the key-value pair entry is valid; if so, proceed to step S503; if not, proceed to step S504;
S503：在起始扇区之外的其他扇区中创建迁移键值对条目，所述键值对条目的数据拷贝至所述迁移键值对条目中，与所述键值对条目相匹配的索引字符串的叶子节点的地址字段更新为指向所述迁移键值对条目的存储地址，所述键值对条目的状态标记为删除状态；S503: creating a migration key-value pair entry in other sectors other than the starting sector, copying the data of the key-value pair entry to the migration key-value pair entry, updating the address field of the leaf node of the index string matching the key-value pair entry to point to the storage address of the migration key-value pair entry, and marking the status of the key-value pair entry as a deleted status;
S504：判断是否所述起始扇区的所述键值对条目遍历完成；若否，开始遍历所述起始扇区中的下一条所述键值对条目；若是，擦除起始扇区，并以所述起始扇区的下一个扇区作为新的起始扇区。S504: Determine whether the traversal of the key-value pair entries in the starting sector is completed; if not, start traversing the next key-value pair entry in the starting sector; if so, erase the starting sector and use the next sector of the starting sector as a new starting sector.
由上述描述可知，该存储方法可以回收初始扇区中所有无效的键值对条目的空间。It can be seen from the above description that the storage method can reclaim the space of all invalid key-value pair entries in the initial sector.
进一步的，所述预设阈值包括第一预设阈值和第二预设阈值，第一预设阈值小于第二预设阈；其中，第一预设阈值用于创建新的键值对条目时判断是否触发回收起始扇区，第二预设阈值用于空闲时判断是否触发回收起始扇区值。Furthermore, the preset threshold includes a first preset threshold and a second preset threshold, and the first preset threshold is smaller than the second preset threshold; wherein the first preset threshold is used to determine whether to trigger the recovery of the starting sector when creating a new key-value pair entry, and the second preset threshold is used to determine whether to trigger the recovery of the starting sector value when idle.
由上述描述可知，该存储方法包括两种情况可以触发回收起始扇区：第一种情况是在写入新的键值对条目时，判断剩余空间是否低于第一预设阈值，其可以保障键值对数据库写入数据时的可靠性，避免Flash因键值对数据库的剩余空间不足而导致写入数据失败；第二种情况是作为用户可选的空间回收功能，当用户有多余的资源，并且对写键值对条目的时效性要求高时，可以使用空闲回收空间功能，通过调用用户的空闲线程回收起始扇区，其不会影响其他模块任务。From the above description, it can be seen that the storage method includes two situations that can trigger the recovery of the starting sector: the first situation is to determine whether the remaining space is lower than the first preset threshold when writing a new key-value pair entry, which can ensure the reliability of the key-value pair database when writing data and avoid the failure of Flash to write data due to insufficient remaining space in the key-value pair database; the second situation is as a user-optional space recovery function. When the user has excess resources and has high requirements on the timeliness of writing key-value pair entries, the idle space recovery function can be used to reclaim the starting sector by calling the user's idle thread, which will not affect other module tasks.
进一步的，第二标志位、第二魔数信息、数据总长度信息、循环冗余校验码、字符串长度、数据长度、键名和键值数据。Furthermore, the second flag bit, the second magic number information, the total length of the data, the cyclic redundancy check code, the string length, the data length, the key name and the key value data.
由上述描述可知，第二魔数信息用于判断该键值对条目是否有效；第二标志位用于判断该键值对条目的状态；数据总长度信息包括键值对条目中的总数据长度；循环冗余校验码用于对键值对条目进行校验，确保数据准确性；字符串长度用于记录键值对条目的键名的字符串长度；数据长度用于记录键值对条目的键值数据的数据长度；键名为键值对对应存储的名称；键值数据为键值对对应存储的参数数据。From the above description, it can be seen that the second magic number information is used to determine whether the key-value pair entry is valid; the second flag is used to determine the status of the key-value pair entry; the total data length information includes the total data length in the key-value pair entry; the cyclic redundancy check code is used to check the key-value pair entry to ensure data accuracy; the string length is used to record the string length of the key name of the key-value pair entry; the data length is used to record the data length of the key value data of the key-value pair entry; the key name is the name of the key-value pair corresponding to the storage; the key-value data is the parameter data corresponding to the key-value pair.
进一步的，还包括步骤S6：Furthermore, the method further comprises step S6:
根据应用层请求的待读键值对键名，查找所述字典树中是否存在相匹配的所述索引字符串；若是，根据待读键值对键名查询所得的索引字符串的叶子节点存储的地址字段读取相匹配的键值对条目，并将相匹配的键值对条目发送至所述应用层；若否，返回无键值对条目信息至所述应用层。According to the key name of the key-value pair to be read requested by the application layer, check whether there is a matching index string in the dictionary tree; if so, read the matching key-value pair entry from the address field stored in the leaf node of the index string obtained by querying the key name of the key-value pair to be read, and send the matching key-value pair entry to the application layer; if not, return the information that there is no key-value pair entry to the application layer.
实施例一Embodiment 1
请参照图1至图7，在本发明的实施例一为：一种键值对数据库的存储方法，其包括步骤：Referring to FIGS. 1 to 7 , the first embodiment of the present invention is a method for storing a key-value pair database, which includes the following steps:
S1：构建字典树，遍历键值对条目，根据各个所述键值对条目的键名分别构建索引字符串，所述索引字符串插入所述字典树中，并在所述索引字符串的叶子节点写入指向对应所述键值对条目的存储地址的地址字段；S1: construct a dictionary tree, traverse the key-value pair entries, construct index strings according to the key names of the key-value pair entries, insert the index strings into the dictionary tree, and write an address field pointing to the storage address corresponding to the key-value pair entry in the leaf node of the index string;
S2：根据待写入键值对的键名查询所述字典树中是否存在相匹配的所述索引字符串；若是，则进入步骤S3；若否，则进入步骤S4;S2: query the dictionary tree according to the key name of the key-value pair to be written whether there is a matching index string; if so, proceed to step S3; if not, proceed to step S4;
S3：根据所述待写入键值对创建新的键值对条目，根据待写入键值对的键名查询所得的索引字符串的所述叶子节点的地址字段更新为指向所述新的键值对条目的存储地址；S3: creating a new key-value pair entry according to the key-value pair to be written, and updating the address field of the leaf node of the index string obtained by querying the key name of the key-value pair to be written to point to the storage address of the new key-value pair entry;
S4：根据所述待写入键值对的键名构建新的索引字符串，所述新的索引字符串插入所述字典树中，根据所述待写入键值对创建新的键值对条目，所述新的索引字符串的叶子节点写入指向所述新的键值对条目的存储地址的地址字段。S4: construct a new index string according to the key name of the key-value pair to be written, insert the new index string into the dictionary tree, create a new key-value pair entry according to the key-value pair to be written, and write the address field pointing to the storage address of the new key-value pair entry into the leaf node of the new index string.
在本实施例一中，字典树的根节点不存放任何字符，除根节点以外，每个节点只存放一个字符，其中，从根节点到某一叶子节点路径上组成的字符串即为对应的索引字符串，并且叶子节点中写入指向与索引字符串相对应的键值对条目的存储地址的地址字段。In the first embodiment of the present invention, the root node of the dictionary tree does not store any characters. Except for the root node, each node only stores one character, wherein the character string formed on the path from the root node to a leaf node is the corresponding index string, and the address field pointing to the storage address of the key-value pair entry corresponding to the index string is written in the leaf node.
具体的，在本实施例一中构建字典树的代码说明如下：Specifically, the code for constructing the dictionary tree in the first embodiment is described as follows:
typedef struct TrieNodetypedef struct TrieNode
{{
bool isEnd;//标记为单词的最后一个字符bool isEnd; //marked as the last character of the word
Char c;//本节点存储的字符Char c; //Character stored in this node
char cnt;//本节点后面存在几个子节点char cnt; //There are several child nodes after this node
uint32_t addr;//本节点携带相匹配的键值对条目的flash地址(首地址），如果为0x00000000则表示未携带uint32_t addr; //This node carries the flash address (first address) of the matching key-value pair entry. If it is 0x00000000, it means that it does not carry
struct TrieNode *next[];//本节点后指向的子节点指针struct TrieNode *next[]; //The child node pointer after this node
}*Trie,TrieNode;}*Trie,TrieNode;
本实施例一中，构建字典树，根据键值对条目的键名构建插入字典树中的索引字符串，并且还对字典树进行变形；具体的，在本实施例一构建的这种字典树中，索引字符串的叶子节点的“uint32_t addr”参数中写入指向与其相匹配的键值对条目的存储地址的地址字段。In this first embodiment, a dictionary tree is constructed, an index string inserted into the dictionary tree is constructed according to the key name of the key-value pair entry, and the dictionary tree is also transformed; specifically, in the dictionary tree constructed in this first embodiment, the address field pointing to the storage address of the key-value pair entry that matches it is written in the "uint32_t addr" parameter of the leaf node of the index string.
另外，在本实施例一中，字典树的节点存储于可变数组中，即：参数structTrieNode *next[]为可变数组，以使字典树根据节点的子节点的数量动态调整可变数组的长度。In addition, in the first embodiment, the nodes of the dictionary tree are stored in a variable array, that is, the parameter structTrieNode *next[] is a variable array, so that the dictionary tree dynamically adjusts the length of the variable array according to the number of child nodes of the node.
传统字典树的节点存储于不可变数组中，其需要预先分配好可能指针会应用到的字母与数字的存储空间。其中，传统字典树的子节点结构如下：The nodes of a traditional dictionary tree are stored in an immutable array, which requires pre-allocation of storage space for letters and numbers that the pointer may apply to. The sub-node structure of a traditional dictionary tree is as follows:
typedef struct TrieNodetypedef struct TrieNode
{{
bool isEnd;//标记为单词的最后一个字符bool isEnd; //marked as the last character of the word
char cnt;//本节点后面存在几个子节点char cnt; //There are several child nodes after this node
struct TrieNode *next[62]//本节点后指向的子节点指针struct TrieNode *next[62]//The child node pointer after this node
}*Trie,TrieNode,}*Trie,TrieNode,
易于理解的，以图6所示的字典树结构以传统字典树存储节点的方式举例说明：可能会应用到26个大写字母、26个小写字母和“0~9”10个数字，即需要对一个子节点的存储的62种字符指针分别需要占用4字节，路径最后一个字符的参数需要占用4字节和本节点后存在子节点个数的参数需要占用4字节，因此一个子节点需要占用（62+1+1）*4=256字节，因此传统字典树存储如图6所示的字典树结构共需占用11*256=2816字节。It is easy to understand. Take the dictionary tree structure shown in Figure 6 as an example to explain the traditional dictionary tree storage node method: 26 uppercase letters, 26 lowercase letters and 10 numbers "0~9" may be applied, that is, the 62 character pointers required to store a child node each need to occupy 4 bytes, the parameter of the last character of the path needs to occupy 4 bytes and the parameter of the number of child nodes after this node needs to occupy 4 bytes, so a child node needs to occupy (62+1+1)*4=256 bytes, so the traditional dictionary tree storage dictionary tree structure shown in Figure 6 needs to occupy a total of 11*256=2816 bytes.
而在本实施例一提供的这种存储方法中字典树的节点存储于可变数组中，其中共有3个节点携带2个子节点，8个节点携带1个子节点，其中，该存储方法的字典树的节点定义中：路径最后一个字符参数占用1字节、本节点存储的字符参数占用1字节、本节点后存在子节点个数参数占用1字节、地址字段参数占用4字节、本节点的一个子节点指针参数占用4字节，因此，携带有两个子节点的节点占用1+1+1+4+4*2=16字节，携带有一个子节点的节点占用1+1+1+4+4*1=11字节；在本实施例一提供的这种存储方法中利用可变数组存储如图6所示的字典树共需占用16*3+11*8=136字节，其相对于传统的字典树可以节省95%的存储空间。In the storage method provided in the first embodiment, the nodes of the dictionary tree are stored in a variable array, wherein 3 nodes carry 2 child nodes, and 8 nodes carry 1 child node. In the node definition of the dictionary tree of the storage method: the last character parameter of the path occupies 1 byte, the character parameter stored in this node occupies 1 byte, the number of child nodes after this node occupies 1 byte, the address field parameter occupies 4 bytes, and a child node pointer parameter of this node occupies 4 bytes. Therefore, a node carrying two child nodes occupies 1+1+1+4+4*2=16 bytes, and a node carrying one child node occupies 1+1+1+4+4*1=11 bytes. In the storage method provided in the first embodiment, using a variable array to store the dictionary tree shown in Figure 6 requires a total of 16*3+11*8=136 bytes, which can save 95% of storage space compared to the traditional dictionary tree.
由于本实施例一中所述的这种存储方法的字典树的节点存储于可变数组中，因此在将新增的索引字符串插入字典树时，需要对已有的节点进行重新分配。Since the nodes of the dictionary tree of the storage method described in the first embodiment are stored in a variable array, when a new index string is inserted into the dictionary tree, the existing nodes need to be reallocated.
易于理解的，图7示意了在字典树存储有索引字符串hell的情况下在字典树中插入索引字符串hi的原理，如图7（a）所示，在字典树中已经存储有索引字符串“hell”。索引字符串“hell”与“hi”均以“h”字符为起始字符，但是如图7（a）存储有“h”字符的节点仅包括一个子节点指针。因此，如图7（b）所示，在插入索引字符串“hi”之前，需创建包括两个子节点指针的新的“h”字符的节点。如图7（c）所示，将包括两个子节点指针的新的“h”字符的节点替换包括一个子节点指针的原有的“h”字符的节点，其中，新的“h”字符的节点的其中一个节点指针指向与原有的“h”字符的子节点，并且原有的“h”字符的节点被替换后删除释放空间。如图7（d）所示，在新的“h”字符的节点的另一个节点指针中加入子节点，即：加入“i”字符的节点，以完成创建索引字符串“hi”。It is easy to understand that FIG7 illustrates the principle of inserting the index string hi in the dictionary tree when the index string hell is stored in the dictionary tree. As shown in FIG7 (a), the index string "hell" has been stored in the dictionary tree. The index strings "hell" and "hi" both start with the character "h", but the node storing the character "h" in FIG7 (a) only includes one child node pointer. Therefore, as shown in FIG7 (b), before inserting the index string "hi", a new node of the character "h" including two child node pointers needs to be created. As shown in FIG7 (c), the node of the character "h" including two child node pointers replaces the original node of the character "h" including one child node pointer, wherein one of the node pointers of the node of the character "h" points to the child node of the original character "h", and the original node of the character "h" is deleted after being replaced to release space. As shown in FIG7 (d), a child node is added to another node pointer of the node of the character "h", that is, a node of the character "i" is added to complete the creation of the index string "hi".
在嵌入式场景下，因为Flash中所存储的参数、配置信息、动态数据的类型相对固定，而各个参数、配置信息、动态数据等数据分别存储于键值对条目中，并通过键值对条目的键名对参数、配置信息、动态数据等数据的类型进行区分，键值对条目及其键名也相对固定，所以主要在初始化过程中需要创建字典树，并在字典树中插入索引字符串，在运行过程中极少会新增键值对条目并创建新的索引字符串插入字典树中。In embedded scenarios, because the types of parameters, configuration information, and dynamic data stored in Flash are relatively fixed, and each parameter, configuration information, dynamic data, and other data are stored in a key-value pair entry, and the types of parameters, configuration information, dynamic data, and other data are distinguished by the key name of the key-value pair entry, and the key-value pair entry and its key name are also relatively fixed, so it is mainly necessary to create a dictionary tree during the initialization process and insert an index string into the dictionary tree. During the operation process, new key-value pair entries are rarely added and new index strings are rarely created and inserted into the dictionary tree.
因此，应用本实施例一所述的这种存储方法，在运行过程中，在读取时需要比较字符花费时间，而在插入新的索引字符串上花费的时间很少，该存储方法的查找效率不会降低太多，但是却可以有效减少ram内存开销。Therefore, by applying the storage method described in the first embodiment, during operation, it takes time to compare characters when reading, but very little time is spent on inserting new index strings. The search efficiency of this storage method will not be reduced too much, but it can effectively reduce RAM memory overhead.
如图2所示，在本实施例一中，步骤S1对键值对数据库初始化，具体的，步骤S1包括步骤：As shown in FIG. 2 , in the first embodiment, step S1 initializes the key-value pair database. Specifically, step S1 includes the following steps:
S101：判断第一扇区是否格式化；若否，进入步骤S102；若是，进入步骤S103；S101: Determine whether the first sector is formatted; if not, proceed to step S102; if yes, proceed to step S103;
S102：将所有扇区格式化；S102: Format all sectors;
S103：构建字典树；S103: Construct a dictionary tree;
S104：从第一扇区的第一条键值对条目开始，依次遍历所有扇区的所有键值对条目；S104: starting from the first key-value pair entry of the first sector, traverse all key-value pair entries of all sectors in sequence;
S105：判断所述键值对条目是否有效；若是，进入步骤S106；若否，进入步骤S107；S105: Determine whether the key-value pair entry is valid; if so, proceed to step S106; if not, proceed to step S107;
S106：根据所述键值对条目的键名构建索引字符串，所述索引字符串插入所述字典树中，并在所述索引字符串的叶子节点写入指向所述键值对条目的存储地址的地址字段；S106: construct an index string according to the key name of the key-value pair entry, insert the index string into the dictionary tree, and write an address field pointing to the storage address of the key-value pair entry into the leaf node of the index string;
S107：判断是否所有扇区的所有键值对条目遍历完成；若是，开始遍历下一条未遍历的键值对条目；若否，完成初始化。S107: Determine whether the traversal of all key-value pair entries of all sectors is complete; if so, start traversing the next untraversed key-value pair entry; if not, complete the initialization.
具体的，在本实施例一中，将所有扇区格式化包括：在所有扇区的头部分别写入相应的扇区信息，并且获取起始扇区；其中，所述扇区信息包括用于检查扇区是否格式化的第一魔数信息与用于检查扇区的状态的第一标志位。Specifically, in the first embodiment, formatting all sectors includes: writing corresponding sector information at the headers of all sectors respectively, and obtaining the starting sector; wherein the sector information includes first magic number information for checking whether the sector is formatted and a first flag bit for checking the status of the sector.
易于理解的，步骤S1的初始化流程主要目的是将Flash中现存的数据读取出来，以构建字典树，字典树内节点个数与现有的键值对条目的数量和键值对中名称的长度有关，在初始化过程中会顺便记录起始扇区，起始扇区就是Flash中第一个有记录数据、不为空的扇区。例如，共划分有十个依次顺序编号的扇区供Flash的键值对数据库驱动，其中，第一扇区至第二扇区为空，第三扇区至第九扇区写满，第十扇区写了部分空间，此时，第三扇区即为起始扇区。其中，在设备初次上电时或者第一个扇区的状态没有被格式化过时，则会触发扇区格式化，并将第一扇区作为起始扇区。It is easy to understand that the main purpose of the initialization process of step S1 is to read the existing data in Flash to build a dictionary tree. The number of nodes in the dictionary tree is related to the number of existing key-value pair entries and the length of the name in the key-value pair. The starting sector will be recorded in the initialization process. The starting sector is the first sector in Flash that has recorded data and is not empty. For example, there are ten sectors numbered in sequence for the key-value pair database driver of Flash, among which the first sector to the second sector are empty, the third sector to the ninth sector are full, and the tenth sector has part of the space written. At this time, the third sector is the starting sector. Among them, when the device is powered on for the first time or the status of the first sector has not been formatted, the sector formatting will be triggered, and the first sector will be used as the starting sector.
本实施例一中扇区信息可以具体如下：In the first embodiment, the sector information may be specifically as follows:
typedef structtypedef struct
{{
uint8_t status_flag[MYFLASH_SECTOR_FLAG_MAX];//扇区信息第一标志位信息uint8_t status_flag[MYFLASH_SECTOR_FLAG_MAX]; //Sector information first flag bit information
uint32_t magic;//用于检查扇区是否已格式化的第一魔数信息('M'，'Y'，'F'，'S'）uint32_t magic; //First magic number information ('M', 'Y', 'F', 'S') used to check whether the sector has been formatted
}myflash_sectorInfoType;}myflash_sectorInfoType;
详细的，本实施例一根据扇区整块擦除写过程中每个字节可独立写一次的特点定义了第一标志位，键值对数据库可以根据读取第一标志位来判断扇区的当前状态（例如：判断扇区存在空余空间写入，是否存在无效数据），从而做出相应处理。具体的，因为Flash不擦写的话，每个字节空间只能写入一次，因此扇区预留有第一标志位的空间，当扇区其当前描述的状态时，则在第一标志位的空间上写入0x00；具体的，扇区可以至少包括以下几种状态：In detail, the first embodiment of the present invention defines the first flag bit according to the characteristic that each byte can be written once independently during the whole block erasing and writing process of the sector. The key-value pair database can judge the current state of the sector (for example, judging whether there is free space to write in the sector or whether there is invalid data) by reading the first flag bit, so as to make corresponding processing. Specifically, because each byte space can only be written once if the Flash is not erased, the sector reserves space for the first flag bit. When the sector is in the state currently described, 0x00 is written in the space of the first flag bit. Specifically, the sector can include at least the following states:
typedef enum{typedef enum{
MYFLASH_SECTOR_FLAG_FORMAL = 0;//已经格式化，但未被使用MYFLASH_SECTOR_FLAG_FORMAL = 0; // Formatted but not used
MYFLASH_SECTOR_FLAG_USING;//已经被使用，但未被写满MYFLASH_SECTOR_FLAG_USING; //Already used, but not fully written
MYFLASH_SECTOR_FLAG_FULL;//写满MYFLASH_SECTOR_FLAG_FULL; //Full
MYFLASH_SECTOR_FLAG_INVALID_DATA;//扇区存在无效数据MYFLASH_SECTOR_FLAG_INVALID_DATA; //The sector contains invalid data
MYFLASH_SECTOR_FLAG_MAX;MYFLASH_SECTOR_FLAG_MAX;
}myflash_sectorStatusFlagEnum;}myflash_sectorStatusFlagEnum;
该存储方法通过在扇区中设置第一标志位，其可以方便查看判断扇区处于什么状态，第一标志位可以作为每次设备重启后作为扇区状态的判断依据。The storage method sets a first flag bit in the sector, which can facilitate checking and determining the state of the sector. The first flag bit can be used as a basis for determining the state of the sector after each device restart.
详细的，数据库在初始化、上电重启、回收存储空间等情况下均会判断扇区状态，数据库根据第一魔数信息可以很快识别出扇区是否已被初始化，并且判断扇区是否有效，因此该数据库的效率高。In detail, the database will determine the sector status in initialization, power-on restart, storage space recovery, etc. The database can quickly identify whether the sector has been initialized and determine whether the sector is valid based on the first magic number information, so the database is highly efficient.
相应的，在本实施例一中，键值对条目包括：第二标志位、第二魔数信息、数据总长度信息、循环冗余校验码、字符串长度、数据长度、键名和键值数据。Correspondingly, in the first embodiment, the key-value pair entry includes: a second flag bit, second magic number information, total data length information, a cyclic redundancy check code, a string length, a data length, a key name, and key value data.
具体的，在本实施例一中，键值对条目可以具体采用如下的结构体：Specifically, in the first embodiment, the key-value pair entry may specifically adopt the following structure:
typedef structtypedef struct
{{
uint8_t status_flag[MYFLASH ITEM_FLAG MAX];//键值对条目的第二标志位uint8_t status_flag[MYFLASH ITEM_FLAG MAX]; //The second flag of the key-value pair entry
uint32_t magic;//用于判断键值对条目是否有效的第二魔数信息（‘M’，‘Y’，‘F’，‘I’）uint32_t magic; //The second magic number information (‘M’, ‘Y’, ‘F’, ‘I’) used to determine whether the key-value pair entry is valid
uint16_t len;//数据总长(header + name +'value)uint16_t len; //Total length of data (header + name + 'value)
uint16_t crc16;//crc16(key_len+ data_len+ name + value)*/uint16_t crc16; //crc16(key_len+ data_len+ name + value)*/
uint16_t key_len;//key lengthuint16_t key_len; //key length
uint16_t value_len;//value lengthuint16_t value_len; //value length
}myflash itemInfoType;}myflash itemInfoType;
详细的，第二魔数信息用于判断键值对条目是否有效，具体的，数据库在初始化、上电重启、回收空间、读写时候等情况下，可以根据第二魔数信息查阅条目状态，以确认所定位的键值对条目是否有效，然后再执行后续操作；数据总长度信息用于表示键值对条目的总长度；循环冗余校验码可以具体采用16位的CRC校验算法，以对键值对条目进行校验，避免数据被异常篡改，确保数据准确性、可靠性；另外，键值对条目中还包括结构体中未显示但实际存在的键名（key）和键值（value），其中，键名是键值对条目对应存储的名称，键值是键值对条目对应存储的数据。In detail, the second magic number information is used to determine whether the key-value pair entry is valid. Specifically, when the database is initialized, powered on and restarted, space is recovered, read and written, etc., the entry status can be checked according to the second magic number information to confirm whether the located key-value pair entry is valid, and then subsequent operations are performed; the total data length information is used to indicate the total length of the key-value pair entry; the cyclic redundancy check code can specifically adopt a 16-bit CRC check algorithm to check the key-value pair entry to prevent data from being abnormally tampered with and ensure data accuracy and reliability; in addition, the key-value pair entry also includes a key name (key) and a key value (value) that are not displayed in the structure but actually exist, wherein the key name is the name of the storage corresponding to the key-value pair entry, and the key value is the data stored corresponding to the key-value pair entry.
上述的键值对条目的第二标志位用于判断键值对条目的状态，当键值对条目满足当前描述的状态时，第二标志位后写入0x00，以便于后续增、删、改、清除；具体的，键值对条目可以至少包括以下几种状态：The second flag bit of the key-value pair entry is used to determine the state of the key-value pair entry. When the key-value pair entry meets the current described state, 0x00 is written after the second flag bit to facilitate subsequent addition, deletion, modification, and deletion. Specifically, the key-value pair entry can include at least the following states:
typedef enum{typedef enum{
MYFLASH_ITEM_FLAG_PRE_WRITE= 0;//条目已部分写入MYFLASH_ITEM_FLAG_PRE_WRITE = 0; //Entry has been partially written
MYFLASH_ITEM_FLAG_WRITE;//条目完全写入MYFLASH_ITEM_FLAG_WRITE; //Entry is completely written
MYFLASH_ITEM_FLAG_PRE_DELETE;//条目准备删除MYFLASH_ITEM_FLAG_PRE_DELETE; //Entry is ready to be deleted
MYFLASH_ITEM_FLAG_DELETED;//条目完成删除MYFLASH_ITEM_FLAG_DELETED; //Entry is deleted
MYFLASH_ITEM_FLAG ERROR;//条目异常(校验失败）MYFLASH_ITEM_FLAG ERROR; //Entry abnormality (verification failed)
MYFLASH_ITEM_FLAG MAX;MYFLASH_ITEM_FLAG MAX;
}myflash_itemStatusFlagEnum;}myflash_itemStatusFlagEnum;
其中，键值对条目的“条目己部分写入”状态以及“条目完全写入”状态是为了避免多线程访问同一数据时，避免出现冲突；键值对条目的“条目准备删除”状态是为了避免更新数据时其他线程抢占读取，以使在新的的键值对条目未完成创建之前，旧的键值对条目还保持为可访问状态，直至新的键值对条目完成创建，并且新的键值对条目变为“条目完全写入”状态后，旧的键值对条目才设置为“条目完成删除”状态。Among them, the "entry has been partially written" state and the "entry is completely written" state of the key-value pair entry are to avoid conflicts when multiple threads access the same data; the "entry is ready to be deleted" state of the key-value pair entry is to avoid other threads preempting reading when updating data, so that before the new key-value pair entry is created, the old key-value pair entry remains accessible. Until the new key-value pair entry is created and the new key-value pair entry becomes the "entry is completely written" state, the old key-value pair entry is set to the "entry is deleted" state.
请参照图3中所示的本实施例一提供的这种存储方法在键值对数据库执行写键值对条目操作过程中流程示意图不难看出，步骤S3包括步骤：Please refer to the flowchart of the storage method provided in the first embodiment of the present invention shown in FIG. 3 . It is not difficult to see that step S3 includes the following steps:
所述待写入键值对的键值的数据与相匹配的所述键值对条目的键值的数据进行对比，判断两者的长度与内容是否一致；若是，根据待写入键值对的键名查询所得的索引字符串的所述叶子节点不更新；若否，根据所述待写入键值对创建新的键值对条目，根据待写入键值对的键名查询所得的索引字符串的所述叶子节点的地址字段更新为指向所述新的键值对条目的存储地址，并相匹配的键值对条目的状态标记为删除状态。The data of the key value of the key-value pair to be written is compared with the data of the key value of the matching key-value pair entry to determine whether the length and content of the two are consistent; if so, the leaf node of the index string obtained by querying the key name of the key-value pair to be written is not updated; if not, a new key-value pair entry is created according to the key-value pair to be written, and the address field of the leaf node of the index string obtained by querying the key name of the key-value pair to be written is updated to point to the storage address of the new key-value pair entry, and the status of the matching key-value pair entry is marked as deleted.
在嵌入式场景下，在更新Flash中所存储的参数、配置信息、动态数据时，仅需在键值对数据库中创建新的键值对条目，其中新的键值对条目的键名和相匹配的键值对条目的键名相同，新的键值对条目的键值数据和相匹配的键值对条目的键值数据不同，并且将字典树中索引字符串的叶子字节所携带的地址字段更新为指向新的键值对条目的存储地址，即可完成键值对数据库中的数据更新。In an embedded scenario, when updating the parameters, configuration information, and dynamic data stored in the Flash, you only need to create a new key-value pair entry in the key-value pair database, where the key name of the new key-value pair entry is the same as the key name of the matching key-value pair entry, the key value data of the new key-value pair entry is different from the key value data of the matching key-value pair entry, and the address field carried by the leaf bytes of the index string in the dictionary tree is updated to point to the storage address of the new key-value pair entry, and the data update in the key-value pair database can be completed.
因此，本实施例一提供的这种存储方法在更新数据时可以无需对整个扇区进行擦除，而是直接创建新的键值对条目并更新字典树中索引字符串的叶子节点中的地址字段，以使键值对数据库读取数据时，通过索引字符串直接读取新的键值对条目，该存储方法可以有效减少扇区的擦写次数，从而达到延长扇区的使用寿命的目的。Therefore, the storage method provided in the first embodiment does not need to erase the entire sector when updating data. Instead, a new key-value pair entry is directly created and the address field in the leaf node of the index string in the dictionary tree is updated, so that when the key-value pair database reads data, the new key-value pair entry is directly read through the index string. This storage method can effectively reduce the number of times the sector is erased and written, thereby achieving the purpose of extending the service life of the sector.
详细的，在步骤S3中，上述的相匹配的键值对条目的状态标记包括步骤：当新的键值对条目未完成创建时，将相匹配的键值对条目的状态标记为“条目准备删除”状态；当新的键值对条目完成创建时，将相匹配的键值对条目的状态标记为“条目完全删除”状态。In detail, in step S3, the status marking of the above-mentioned matching key-value pair entries includes the steps of: when the new key-value pair entry has not been completed, marking the status of the matching key-value pair entry as the "entry ready to be deleted" status; when the new key-value pair entry has been completed, marking the status of the matching key-value pair entry as the "entry completely deleted" status.
在本实施例一提供的这种存储方法中，为了进一步提高写入速度，以使键值对数据库更加适用于周期性动态数据存储，键值对数据库还可以自动回收存储空间。如图4所示，该存储方法还包括步骤S5：判断剩余空间是否小于预设阈值；若是，回收起始扇区；若否，不回收起始扇区。In the storage method provided in the first embodiment, in order to further improve the writing speed and make the key-value pair database more suitable for periodic dynamic data storage, the key-value pair database can also automatically recycle the storage space. As shown in FIG4 , the storage method also includes step S5: determining whether the remaining space is less than a preset threshold; if so, reclaiming the starting sector; if not, not reclaiming the starting sector.
其中，回收起始扇区包括步骤：Wherein, reclaiming the starting sector comprises the steps of:
S501：遍历起始扇区中的所有键值对条目；S501: traverse all key-value pair entries in the starting sector;
S502：判断所述键值对条目是否有效；若是，进入步骤S503；若否，进入步骤S504；S502: Determine whether the key-value pair entry is valid; if so, proceed to step S503; if not, proceed to step S504;
S503：在起始扇区之外的其他扇区中创建迁移键值对条目，所述键值对条目的数据拷贝至所述迁移键值对条目中，与所述键值对条目相匹配的索引字符串的叶子节点的地址字段更新为指向所述迁移键值对条目的存储地址，所述键值对条目的状态标记为删除状态；S503: creating a migration key-value pair entry in other sectors other than the starting sector, copying the data of the key-value pair entry to the migration key-value pair entry, updating the address field of the leaf node of the index string matching the key-value pair entry to point to the storage address of the migration key-value pair entry, and marking the status of the key-value pair entry as a deleted status;
S504：判断是否所述起始扇区的所述键值对条目遍历完成；若否，开始遍历所述起始扇区中的下一条所述键值对条目；若是，擦除起始扇区，并以所述起始扇区的下一个扇区作为新的起始扇区。S504: Determine whether the traversal of the key-value pair entries in the starting sector is completed; if not, start traversing the next key-value pair entry in the starting sector; if so, erase the starting sector and use the next sector of the starting sector as a new starting sector.
其中，所述键值对条目的状态标记为删除状态包括：当迁移键值对条目未完成创建时，将键值对条目的状态标记为“条目准备删除”状态；当迁移键值对条目完成创建时，将键值对条目的状态标记为“条目完全删除”状态。Among them, marking the status of the key-value pair entry as a deleted status includes: when the migration key-value pair entry has not been created, marking the status of the key-value pair entry as an "entry ready to be deleted" status; when the migration key-value pair entry has been created, marking the status of the key-value pair entry as an "entry completely deleted" status.
在本实施例一中，上述预设阈值包括第一预设阈值和第二预设阈值，第一预设阈值小于第二预设阈；其中，第一预设阈值用于创建新的键值对条目时判断是否触发回收起始扇区，第二预设阈值用于空闲时判断是否触发回收起始扇区值。In the first embodiment of the present invention, the above-mentioned preset threshold includes a first preset threshold and a second preset threshold, and the first preset threshold is less than the second preset threshold; wherein the first preset threshold is used to determine whether to trigger the recovery of the starting sector when creating a new key-value pair entry, and the second preset threshold is used to determine whether to trigger the recovery of the starting sector value when idle.
因此，本实施例一提供的这种存储方法可以至少包括两种触发空间回收的情况：Therefore, the storage method provided in the first embodiment may include at least two situations in which space reclamation is triggered:
第一种情况是创建新的键值对条目时触发空间回收，具体的，每次创建新的键值对条目时，判断键值对数据库的剩余空间是否小于第一预设阈值；若是，回收起始扇区；若否，不回收起始扇区；The first case is that space recycling is triggered when a new key-value pair entry is created. Specifically, each time a new key-value pair entry is created, it is determined whether the remaining space of the key-value pair database is less than a first preset threshold; if so, the starting sector is recycled; if not, the starting sector is not recycled;
第二种情况是在键值对数据库空闲时触发空间回收，上述的第二预设阈值大于第一预设阈值，以实现在键值对数据库空闲时自动回收空间。具体的，在键值对数据库进入空闲线程时，判断键值对数据库的剩余空间是否低于第二预设阈值；若是，回收起始扇区；若否，不回收起始扇区。The second situation is that space recovery is triggered when the key-value database is idle, and the second preset threshold is greater than the first preset threshold, so as to realize automatic space recovery when the key-value database is idle. Specifically, when the key-value database enters the idle thread, it is determined whether the remaining space of the key-value database is lower than the second preset threshold; if so, the starting sector is recovered; if not, the starting sector is not recovered.
其中，在键值对数据库空闲时触发空间回收作为用户可选的空间回收方法，在键值对数据库对时效性要求高并且键值对数据库有空闲的线程资源的情况下，可以利用空闲线程对键值对数据库的空间资源进行回收，由于该回收功能在用户的空闲的线程中进行，其不会影响其他模块任务。另外，因为可能会存在多线程同时创建新的键值对条目的情况，在这种情况下，如果前一个线程已触发回收机制，下一个线程就单纯写入键值对即可，避免同时触发空间回收功能。Among them, triggering space recycling when the key-value database is idle is a space recycling method that users can choose. When the key-value database has high timeliness requirements and the key-value database has idle thread resources, the idle thread can be used to recycle the space resources of the key-value database. Since the recycling function is performed in the user's idle thread, it will not affect other module tasks. In addition, because there may be a situation where multiple threads create new key-value entries at the same time, in this case, if the previous thread has triggered the recycling mechanism, the next thread can simply write the key-value pair to avoid triggering the space recycling function at the same time.
在本实施例一中，当键值对数据库需要执行读键值对条目操作时，可以执行以下步骤S6：In the first embodiment, when the key-value pair database needs to perform a key-value pair entry read operation, the following steps S6 may be performed:
根据应用层请求的待读键值对键名，查找所述字典树中是否存在相匹配的所述索引字符串；若是，根据待读键值对键名查询所得的索引字符串的叶子节点存储的地址字段读取相匹配的键值对条目，并将相匹配的键值对条目发送至所述应用层；若否，返回无键值对条目信息至所述应用层。According to the key name of the key-value pair to be read requested by the application layer, check whether there is a matching index string in the dictionary tree; if so, read the matching key-value pair entry from the address field stored in the leaf node of the index string obtained by querying the key name of the key-value pair to be read, and send the matching key-value pair entry to the application layer; if not, return the information that there is no key-value pair entry to the application layer.
综上所述，本发明所述的这种存储方法利用字典树对键值对数据库中的键值对条目起到索引作用，在实际应用时仅需尽可能分配较多的扇区给键值对数据库，以使键值对数据库具有较大的存储区域，并且在使用Flash的过程中，仅需对键值对条目进行增加或者删除，而无需对整个扇区进行擦写，该存储方法不仅有益于降低键值对数据库维护的难度，还可以避免键值对数据库反复擦写扇区而降低扇区的使用寿命。To sum up, the storage method described in the present invention uses a dictionary tree to index the key-value pair entries in the key-value pair database. In actual application, it is only necessary to allocate as many sectors as possible to the key-value pair database so that the key-value pair database has a larger storage area. In the process of using Flash, it is only necessary to add or delete the key-value pair entries without erasing the entire sector. This storage method is not only beneficial to reducing the difficulty of maintaining the key-value pair database, but also can avoid the key-value pair database from repeatedly erasing sectors and reducing the service life of the sectors.
以上所述仅为本发明的实施例，并非因此限制本发明的专利范围，凡是利用本发明说明书及附图内容所作的等同变换，或直接或间接运用在相关的技术领域，均同理包括在本发明的专利保护范围内。The above descriptions are merely embodiments of the present invention and are not intended to limit the patent scope of the present invention. Any equivalent transformations made using the contents of the present invention's specification and drawings, or directly or indirectly applied in related technical fields, are also included in the patent protection scope of the present invention.
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202410432123.6ACN118035503B (en) | 2024-04-11 | 2024-04-11 | A storage method for key-value database |
| CN202410892138.0ACN118964675B (en) | 2024-04-11 | A space recovery method for key-value database |
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202410432123.6ACN118035503B (en) | 2024-04-11 | 2024-04-11 | A storage method for key-value database |
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN202410892138.0ADivisionCN118964675B (en) | 2024-04-11 | A space recovery method for key-value database |
| Publication Number | Publication Date |
|---|---|
| CN118035503Atrue CN118035503A (en) | 2024-05-14 |
| CN118035503B CN118035503B (en) | 2024-06-28 |
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN202410432123.6AActiveCN118035503B (en) | 2024-04-11 | 2024-04-11 | A storage method for key-value database |
| Country | Link |
|---|---|
| CN (1) | CN118035503B (en) |
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN118760399A (en)* | 2024-07-03 | 2024-10-11 | 长沙理工大学 | A layer-based oblivious batch data insertion method and system |
| CN119441207A (en)* | 2024-11-08 | 2025-02-14 | 湖北华中电力科技开发有限责任公司 | A database storage method |
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US20170212680A1 (en)* | 2016-01-22 | 2017-07-27 | Suraj Prabhakar WAGHULDE | Adaptive prefix tree based order partitioned data storage system |
| CN107229718A (en)* | 2017-05-31 | 2017-10-03 | 北京京东尚科信息技术有限公司 | The method and apparatus for handling report data |
| US20190179948A1 (en)* | 2017-12-12 | 2019-06-13 | International Business Machines Corporation | Storing unstructured data in a structured framework |
| CN110347685A (en)* | 2019-06-28 | 2019-10-18 | 华中科技大学 | Index structure, data query optimization method, main memory management device based on dictionary tree |
| US20200364207A1 (en)* | 2019-05-14 | 2020-11-19 | Alibaba Group Holding Limited | Methods and devices for data traversal |
| CN114153848A (en)* | 2021-05-07 | 2022-03-08 | 支付宝(杭州)信息技术有限公司 | Block chain data storage method and device and electronic equipment |
| CN114398187A (en)* | 2021-12-24 | 2022-04-26 | 新浪网技术(中国)有限公司 | Data storage method and device |
| CN115221176A (en)* | 2022-07-29 | 2022-10-21 | 蚂蚁区块链科技(上海)有限公司 | Blockchain data storage method and device, electronic device |
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US20170212680A1 (en)* | 2016-01-22 | 2017-07-27 | Suraj Prabhakar WAGHULDE | Adaptive prefix tree based order partitioned data storage system |
| CN107229718A (en)* | 2017-05-31 | 2017-10-03 | 北京京东尚科信息技术有限公司 | The method and apparatus for handling report data |
| US20190179948A1 (en)* | 2017-12-12 | 2019-06-13 | International Business Machines Corporation | Storing unstructured data in a structured framework |
| US20200364207A1 (en)* | 2019-05-14 | 2020-11-19 | Alibaba Group Holding Limited | Methods and devices for data traversal |
| CN110347685A (en)* | 2019-06-28 | 2019-10-18 | 华中科技大学 | Index structure, data query optimization method, main memory management device based on dictionary tree |
| CN114153848A (en)* | 2021-05-07 | 2022-03-08 | 支付宝(杭州)信息技术有限公司 | Block chain data storage method and device and electronic equipment |
| CN114398187A (en)* | 2021-12-24 | 2022-04-26 | 新浪网技术(中国)有限公司 | Data storage method and device |
| CN115221176A (en)* | 2022-07-29 | 2022-10-21 | 蚂蚁区块链科技(上海)有限公司 | Blockchain data storage method and device, electronic device |
| Title |
|---|
| 英昌甜;王维庆;于炯;卞琛;国冰磊;祁雷;: "内存计算环境下基于索引结构的内存优化策略", 新疆大学学报(自然科学版), no. 01, 29 January 2018 (2018-01-29)* |
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN118760399A (en)* | 2024-07-03 | 2024-10-11 | 长沙理工大学 | A layer-based oblivious batch data insertion method and system |
| CN119441207A (en)* | 2024-11-08 | 2025-02-14 | 湖北华中电力科技开发有限责任公司 | A database storage method |
| Publication number | Publication date |
|---|---|
| CN118035503B (en) | 2024-06-28 |
| CN118964675A (en) | 2024-11-15 |
| Publication | Publication Date | Title |
|---|---|---|
| CN118035503A (en) | Method for storing key value pair database | |
| US11392314B2 (en) | Sequentially writing metadata into a solid state disk by redirect-on-write | |
| JP5603997B2 (en) | Storage apparatus and data control method | |
| CN105975399B (en) | Method for managing a memory device and related memory device | |
| US8046523B2 (en) | Flash memory management system and apparatus | |
| US20020112116A1 (en) | Methods, systems, and computer program products for storing data in collections of tagged data pieces | |
| CN108228479B (en) | Embedded FLASH data storage method and system | |
| CN100407336C (en) | A data access method of non-volatile memory in embedded system | |
| US20100131700A1 (en) | Memory indexing system and process | |
| JP2000194590A (en) | Extension card file system | |
| KR20080063466A (en) | Flash memory management | |
| CN111241090B (en) | Method and device for managing data index in storage system | |
| WO2019091085A1 (en) | Snapshot comparison method and apparatus | |
| CN114780500B (en) | Data storage method, device and equipment based on log merging tree and storage medium | |
| CN105159616A (en) | Disk space management method and device | |
| CN111159114A (en) | File storage method, device and server | |
| CN110764704A (en) | Environment variable writing method, storage medium and electronic device | |
| CN111104377A (en) | File management method, electronic device and computer-readable storage medium | |
| CN102567415A (en) | Database control method and device | |
| CN119441207B (en) | Database storage method | |
| CN118964675B (en) | A space recovery method for key-value database | |
| CN112346771B (en) | Upgrade file generation method and device | |
| JP6050794B2 (en) | FLASH MEMORY MODULE, NONVOLATILE SEMICONDUCTOR MEMORY MODULE, AND STORAGE DEVICE | |
| CN111694806A (en) | Transaction log caching method, device, equipment and storage medium | |
| CN116303242A (en) | Embedded lightweight database system |
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| GR01 | Patent grant | ||
| GR01 | Patent grant |