CN102024046A - 数据重复性校验方法和装置及系统 - Google Patents

Abstract

本发明实施例公开了一种数据重复性校验方法和装置及系统。该方法包括：将数据各字符的参数在并行索引树中分别与叶节点的参数进行匹配，并行索引树的每个叶节点分别与一个字符对应，且叶节点参数至少包括字符所在数据的字符串长度和字符在所述字符串中的位置；根据各字符的匹配结果判断所述数据是否与已存储的数据重复，若否，则将所述数据各字符的参数作为叶节点参数存储到所述并行索引树中。本发明实施例提供的数据重复性校验方法和装置，以并行索引树的形式对数据中各字符的参数值进行并行的匹配，并且该方案不依赖于存储数据的数据库，从而具有较小的索引量，能够显著提高数据重复性校验效率。

Description

数据重复性校验方法和装置及系统

技术领域

本发明实施例涉及数据处理技术，尤其涉及一种数据重复性校验方法和装置及系统。

背景技术

在数据操作的众多领域中，例如某软件系统中，经常要保证某数据项具备唯一性，此时需要针对该数据项，将新增加数据与已有数据进行重复性校验。例如，某Web应用论坛，在注册新用户的时候，需要对新增的用户名进行校验，检查是否已有重复的用户名，如果重复将告知用户重新输入一个用户名。

现有数据重复性校验方法实现方式主要分为两种：一种是在新增数据插入前进行重复性判断；另一种是在新增数据插入后进行重复性判断。这两种方式均需要依赖数据库进行数据逐一比对来校验重复性。然而，依赖数据库的校验模式，随着数据的增加，其判断速度和效率将显著下降。

发明内容

本发明实施例提供一种数据重复性校验方法和装置及系统，以提高数据重复性校验的效率。

本发明实施例提供一种数据重复性校验方法，包括：

将数据各字符的参数在并行索引树中分别与叶节点的参数进行匹配，所述并行索引树的每个叶节点分别与一个字符对应，且叶节点的参数至少包括字符所在数据的字符串长度和字符在所述字符串中的位置；

根据各字符的匹配结果判断所述数据是否与已存储的数据重复，若否，则将所述数据各字符的参数作为叶节点的参数存储到所述并行索引树中。

本发明实施例提供一种数据重复性校验装置，包括：

并行索引树存储模块，用于存储并行索引树中各叶节点的参数，所述并行索引树的每个叶节点分别与一个字符对应，且叶节点的参数至少包括字符所在数据的字符串长度和字符在所述字符串中的位置；

参数匹配模块，用于将数据各字符的参数在并行索引树中分别与叶节点的参数进行匹配；

并行重复性判断模块，用于根据各字符的匹配结果判断所述数据是否与已存储的数据重复，若否，则将所述数据各字符的参数作为叶节点的参数存储到所述并行索引树中。

本发明实施例还提供了一种数据应用系统，包括：

应用服务器，用于接收用户输入的数据，将数据提供给校验服务器进行重复性校验；

校验服务器，用于将接收到的数据各字符的参数在并行索引树中分别与叶节点的参数进行匹配，所述并行索引树的每个叶节点分别与一个字符对应，且叶节点的参数至少包括字符所在数据的字符串长度和字符在所述字符串中的位置；根据各字符的匹配结果判断所述数据是否与已存储的数据重复，若否，则将所述数据各字符的参数作为叶节点的参数存储到所述并行索引树中，同时将所述数据提供给数据库服务器进行存储；

数据库服务器，用于将所述数据进行存储。

本发明实施例提供的数据重复性校验方法和装置及系统，以并行索引树的形式对数据中各字符的参数值进行并行的匹配，并且该方案不依赖于存储数据的数据库，从而具有较小的索引量，能够显著提高数据重复性校验效率。

附图说明

图1为本发明实施例一提供的数据重复性校验方法的流程图；

图2为本发明实施例二提供的数据重复性校验方法的流程图；

图3为本发明实施例中所存储数据的树状结构示意图；

图4为本发明实施例三提供的数据重复性校验方法的流程图；

图5为本发明实施例六提供的数据重复性校验装置的结构示意图；

图6为本发明实施例七提供的数据重复性校验装置的结构示意图；

图7为本发明实施例八提供的数据重复性校验装置中参数匹配模块的结构示意图；

图8为本发明实施例九提供的数据重复性校验装置的结构示意图；

图9为本发明实施例十提供的数据应用系统的结构示意图。

具体实施方式

为使本发明实施例的目的、技术方案和优点更加清楚，下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有作出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。

实施例一

图1为本发明实施例一提供的数据重复性校验方法的流程图，该方法可适用于任何需要对数据进行重复性校验的情况，例如新增用户名是否与已存储用户名重复；文件系统中新增文件的文件名是否与已使用的文件名重复等各种情况。本实施例中的数据重复性校验方法具体可以由数据操作系统来执行，数据操作系统可以是软硬件结合来实现的装置。该方法具体包括如下步骤：

步骤110、将数据各字符的参数在并行索引树中分别与叶节点的参数进行匹配，该并行索引树的每个叶节点分别与一个字符对应，且叶节点的参数至少包括字符所在数据的字符串长度和字符在该字符串中的位置；

步骤120、根据各字符的匹配结果判断该数据是否与已存储的数据重复，若否，即该数据与已存储的数据不重复，则执行步骤130；若是，则视为该数据与已存储的数据重复，执行步骤140。

步骤130、将该数据各字符的参数作为叶节点的参数存储到并行索引树中，同时该数据可以被接受或进行存储、将数据持久化到数据库中，即将数据存储到该数据库中，流程结束。

步骤140、可以拒绝该数据或直接丢弃，若为文件路径重复则可以改写文件存储路径等。

在上述步骤120中，由于每次存储数据都会将该数据各字符的参数作为叶节点的参数存储到并行索引树中，所以通过将新增数据的字符参数在并行索引树中匹配就可以判断出该数据是否重复。

本实施例的技术方案采用了针对数据的各字符进行并行索引的方式来校验数据的重复性。并行索引树可以为B+树的形式，包括多个叶节点，可逐层设置，叶节点分别与一个字符对应。每个叶节点的参数至少包括对应字符所在数据的字符串长度和所对应字符在数据字符串中的位置。在字符与叶节点的参数匹配时，可以将数据的各个字符同时与对应的叶节点进行匹配，提高匹配的速度。当任意一个字符没有查找到对应的叶节点时，则说明该数据没有被存储，与已有数据不重复；当对每个字符都能查找到对应的叶节点时，说明该数据已经被存储的概率较高。此时的处理方式有多种，一种是默认该数据重复，则可以直接丢弃该数据，这种情况在数据字符串长度较小时具有较高的准确性，另一种是继续进行更精确的重复性校验，这种情况在数据字符串长度较长时更为必要。无论采用上述哪种处理方式，由于首先对数据各字符进行了并行校验，所以至少能够验证一部分数据的重复性，因而能够在一定程度上提高重复性校验的效率。在目前的数据重复性校验中，用户名和文件名等的字符串长度通常不太长，所以本实施例的技术方案可以在大部分的重复性校验中提高效率，且保证一定的准确性。

数据中的各字符与叶节点一一对应，可以是字符与叶节点直接对应，但是为提高计算速度和改善计算的通用性，在将数据各字符的参数在并行索引树中分别与已存储的叶节点的参数进行匹配之前，还可以首先将数据的各字符分别转换为数据标识，每个叶节点通过字符的数据标识与字符对应，例如字节(byte)形式。例如，以数字字节标识每个字符，如“0001”代表“上”，“0002”代表“z”等，只要满足数据标识能唯一标识字符即可。此处所谓的字符，可以是单个数字、标点符号、英文字母、汉字或数据中的某几位字节，也可以是上述元素的有机组合，例如文件名后缀“.PDF”可以定义为一个字符。

实施例二

图2为本发明实施例二提供的数据重复性校验方法的流程图。本实施例以实施例一为基础，进一步在并行索引的基础上增加了串行索引的手段。本实施例中，当根据各字符的匹配结果判断出数据与已存储的数据重复之后，还执行如下操作：

步骤210、将数据的索引在辅助索引表中进行匹配，该辅助索引表中包括已存储数据的索引，已存储数据的索引可以是数据字符串本身，也可以是数据标识组成的数字索引串；

上述步骤210中的匹配是数据索引的一一查找匹配，可以采用已有技术中的各种数据匹配方案，属于根据数据本身进行精确查找的手段。

步骤220、根据数据在辅助索引表中的匹配结果判断该数据是否与已存储的数据重复，若是，则执行步骤230，若否，则执行步骤240；

步骤230、产生数据重复结果，即数据与已存储的数据重复，流程结束；

步骤240、数据与已存储的数据不重复，则将数据各字符的参数作为叶节点的参数存储到并行索引树中，并将该数据的索引存储在辅助索引表中，以备新增其他数据时进行索引和匹配。

本实施例的技术方案通过并行索引提高了数据重复性校验速度，并通过串行的精确索引保证了数据重复性校验的唯一性和准确性。虽然精确索引校验仍然要依赖于数据本身的索引，但由于首先经过了并行索引的排除，使得需要进行精确性校验的数据量显著减少，因此在一定程度上能够改善数据重复性校验效率，在数据字符串长度较小的情况下这种优势尤为明显，而通常用户名、文件名等字符串长度大都是不超过20个字符的短字符串。

在本实施例中，优选可以设定需要并行索引的字符数量，即在将数据各字符的参数在并行索引树中分别与叶节点的参数进行匹配之前，还包括：从数据中截取设定数量的字符作为在并行索引树中与叶节点的参数进行匹配的各字符，而后进行的并行索引仅限定截取的字符。具体设定的截取数量可以根据要保存的数据量、字符个数来设定。

例如，设定并行索引的字符数为7个，则每次进行索引均从数据中截取至多7个字符，余下的字符不进行并行索引，但应注意，在并行索引时，虽然截取的数量减少，但是数据字符串的长度并不引截取而减少。由于并行索引的方式在字符数较少的情况下优势明显，可靠性更高，所以截取有限数量的字符进行并行索引，既能够保留并行索引的效率和准确性优势，又能避免字符数过多时不必要的并行索引。

实施例三

并行索引树的组织形式可以有多种，例如，以数据的首字符为根节点组织的多个并行索引树，或者以数据的字符串长度、用户名类型、或者文件名类型等数据整体的其他参数作为根节点组织的多个并行索引树。使用各种并行索引树进行匹配的方式类似，本发明实施例三以数据的首字符为并行索引树根节点为例进行解释说明。为表述清楚而结合一简化的实例。假设数据库中已经存储了“a”、“ad”、“an”、“adm”、“adn”和“and”等数据时，如图3所示为所存储数据的树状结构示意图。需要新增的数据为“adi”。在为这些数据建立的并行索引树中，以首字母“a”作为根节点，以各字符作为叶节点，每个字符可能出现在不同的数据中，因此有不同的层数和位置，则可以将每一组层数和位置作为该字符对应的一个叶节点的参数，则一个字符可能对应多个叶节点。或者也可以将该字符的所有层数和位置组合存储为该字符的一个叶节点的参数，则一个字符对应一个叶节点。每个字符在各叶节点的参数值形式记录为“字符的数据标识”{层数1[位置1]，层数2[位置2]，......}。各字符下可挂载叶节点的参数，当各字符的数据标识具体设定为a＝97，d＝100，m＝109，i＝105，n＝110时，则上述实例的并行索引树叶节点的参数可表示为表1中的矩阵形式：

表1

97	{1[1]，2[1]，3[1]}
		100	{2[2]，3[2]，3[3]}
109	{3[3]}
		110	{2[2]，3[2]，3[3]}

图4为本发明实施例三提供的数据重复性校验方法的流程图，本实施例以上述各实施例为基础，且具体的，并行索引树的数量为多个，各并行索引树的根节点对应数据字符串的首字符，则将数据各字符的参数在并行索引树中分别与叶节点的参数进行匹配的操作具体包括：

步骤410、根据数据字符串的首字符选择对应的并行索引树，根据新增数据“adi”的首字母“a”选择了表1所示的并行索引树；

步骤420、针对数据中各字符并行地分别执行如下查找匹配操作，其中，分别对“a”、“d”和“i”同时进行查找匹配操作，下面以匹配“d”为例进行说明，具体操作如下：

步骤421、根据数据字符串的长度在选择的并行索引树查找叶节点所在层，“adi”的字符串长度为3，则在“d”所对应的各叶节点中查找第三层的参数，查找到两个值，3[2]，3[3]；

步骤422、根据字符在数据字符串中的位置，在查找到的叶节点所在层中查找匹配的叶节点，产生字符查找匹配结果；“d”在“adi”的第二个字符位置，据此匹配到3[2]。

对“i”字符进行类似的查找，但是查找结果为否，没有匹配的叶节点。

步骤430、当识别到一个字符的字符查找匹配结果为否时，产生数据查找匹配结果，并停止其他字符的查找匹配操作。若根据首字母选择并行索引树的结果即为空，也相当于一个字符的字符查找匹配结果为否。

在前述步骤中，当查找到没有“i”字符的叶节点时就可以停止查找“d”字符，任意一个字符没有匹配到就意味着该数据没有重复存在。

本实施例的技术方案给出了具体的利用并行索引树进行索引的优选方案之一。各字符并发地执行重复性校验，在一个字符未匹配到时即可判定不重复，从而终止其他字符的查找匹配操作，因此具有较高的校验效率。

实施例四

本实施例以前述实施例为基础，优选的是并行索引树的每个叶节点的参数还包括字符前坐标和/或后坐标，所谓前坐标是指该字符之前字符的参数，例如前一个字符的数据标识，或者前两个字符的数据标识；相应地，后坐标是指该字符之后字符的参数。当叶节点中包括字符前坐标和/或后坐标时，则根据字符在数据字符串中的位置，在查找到的叶节点所在层中查找匹配的叶节点之后，产生字符查找匹配结果之前，还执行如下操作：

将字符的前字符和/或后字符与匹配到的叶节点的参数中的前坐标和/或后坐标进行一致性匹配。

前字符的前坐标和后字符的后坐标可以只包括一个，或者前坐标和后坐标均包括，可以兼顾匹配操作的执行速度和精确性来选择。

设置前坐标和后坐标后的叶节点的参数形式为{层数1[位置1：{|后坐标1，|后坐标2......}]、层数2[位置2：{前坐标1|后坐标1，前坐标2|后坐标2}]，层数3[位置3：{前坐标1|，前坐标2|}]}。则图3所示数据的并行索引树对应的叶节点数值如表2所示：

表2

97	{1[1]，2[1：{|100，|110}]，3[1：{|100，|110}]}
		100	{2[2：{97|}]，3[2：{97|109，97|110}]，3[3：{110|}]}
109	{3[3：{100|}]}
		110	{2[2：{97|}]，3[2：{97|100}]，3[3：{100|}]}

仍以前述实施例三步骤422匹配到“d”字符为例，在查找到的叶节点所在层中查找匹配的叶节点之后，产生字符查找匹配结果之前，还将“d”字符的前字符和后字符与匹配到的叶节点的参数中的前坐标和后坐标进行一致性匹配。“d”的前字符是“a(97)”，后字符是“i(105)”，经匹配可知，在3[2：{97|109，97|110}]中不存在3[2：{97|105}]，因此，对“d”字符的匹配结果也为否。

上述匹配前坐标和后坐标的技术方案能够进一步提高重复性校验过程中并行匹配的准确性，减少需要进行串行匹配的情况，提高重复性校验效率。

在上述实例中，假设新增的字符串为“admin在喝酒”，在截取“admin”进行并行索引后发现“admin***”存在，则继续在辅助索引表中进行查找匹配。转换为数据标识形式的“admin在喝酒”字符串对应的数据索引为“/97/100/109/105/110/410，510，610”，其中“410，510，610”对应于“在喝酒”。

实施例五

本发明实施例五提供的数据重复性校验方法可以基于上述各实施例进行改进，并行索引树叶节点的参数还包括字符出现次数。仍沿用前述实施例，增加字符在某个叶节点同一层数同一位置的出现次数，例如，“a”字符在第二层第一字符的位置出现了两次，则将“2”作为叶节点的参数进行记录，叶节点的参数形式为{层数1[位置1：次数]，层数2[位置2：次数]，......}。则图3所示数据的并行索引树中包括出现次数的叶节点的参数如表3所示：

表3

97	{1[1:1]，2[1:2]，3[1:3]}
		100	{2[2:1]，3[2:2]，3[3:1]}
109	{3[3:1}
		110	{2[2:1}]，3[2:1]，3[3:1]}

则以前述实施例为基础，将数据各字符的参数作为叶节点的参数存储到并行索引树中之后，还包括：

将对应叶节点的参数中的字符出现次数加一；

当删除数据时，根据删除数据各字符查找并行索引树中的对应叶节点，并将查找到的叶节点的参数中字符出现次数减一。

对数据的增删步骤没有特定的时序关系。上述技术方案可满足数据删减的情况需求。当需要从数据库中删除数据时，将字符出现次数减一，则既能够避免数据删减时其叶节点仍然保留在并行索引树中，也能够保证数据删除时，不会将标识其他数据中相应字符的叶节点删除。

例如，“d”字符在第三层第二个出现了两次，记为3[2:2]，当将“adn”删除时，将3[2:2]修改为3[2:1]，既能表征“adm”中的“d”字符，又能表征减少了“adn”。

按照上述技术方案执行查找匹配操作之后确定“adi”字符不重复，则将数据“adi”在数据库中持久化存储。并且，将并行索引树的叶节点索引表修改为表4：

表4

97	{1[1:1]，2[1:2{|100，|110}]，3[1:4{|100，|110}]}
		100	{2[2:1{97|}]，3[2:3{97|109，97|110，97|105}]，3[3:1{110|}]}
109	{3[3:1{100|}]}
		110	{2[2:1{97|}]，3[2:1{97|100}]，3[3:1{100|}]}
105	3[3:1{100|}]

其中，修改了字符“a”和“d”的出现次数、前坐标和后坐标，还增加了字符“i”的索引。

本发明各实施例的技术方案优势在数据量增大的情况下尤为显著。当数据量达到海量时，例如论坛的注册用户名或文件系统中的文件名增加达到海量时，现有技术单纯依赖数据库的重复校验方式的速率将显著降低，若出现需要将数据库分库的情况下，就不能依赖数据库来进行判断了，代价高昂，不能接受。现有技术采用单纯依赖数据库的方式时，当并发访问压力比较大的时候，如果发生很多的重复，则数据库报异常非常多，将会影响数据库本身的性能和稳定性。

本发明各实施例的技术方案克服了现有技术的缺陷，不依赖数据库实现了某些单独数据项的唯一性校验；校验的效率不受需要存储的数据量的影响，即使数据量达到海量也不影响校验逻辑和效率；由于并行索引树所占用的存储空间小，所以能够支持数据海量时的系统分库变化，适用性很广，普通系统和分布式系统都可以通用。无论数据库的数量有多少，也无论数据库是否为分布式系统，由于并行索引树和辅助索引表所占用存储空间小，可以集中存储，所以重复性校验不会受数据库形式的影响，无需额外的工作来适应数据库形式的改变。

由于采用了本发明实施例的技术方案，减小了需要索引匹配的存储量，例如，所有汉字、英文字母和数字等字符的数量大概为6000。本发明实施例的技术方案中，并行索引树的划分是虚拟的结构，实际需要物理存储的是并行索引树各叶节点的参数和辅助索引表，这些字符所占据的索引存储量可以完全存储于内存中，有利于进一步提高匹配速度。

实施例六

图5为本发明实施例六提供的数据重复性校验装置的结构示意图，该装置包括：并行索引树存储模块510、参数匹配模块520和并行重复性判断模块530。其中，并行索引树存储模块510用于存储并行索引树中各叶节点的参数，并行索引树的每个叶节点分别与一个字符对应，且叶节点的参数至少包括字符所在数据的字符串长度和字符在所述字符串中的位置；参数匹配模块520用于将数据各字符的参数在并行索引树中分别与叶节点的参数进行匹配；并行重复性判断模块530用于根据各字符的匹配结果判断所述数据是否与已存储的数据重复，若否，则将数据各字符的参数作为叶节点的参数存储到并行索引树中。

本实施例的技术方案采用了针对数据的各字符进行并行索引的方式来校验数据的重复性，能够提高重复性校验的效率。

实施例七

图6为本发明实施例七提供的数据重复性校验装置的结构示意图，本实施例以实施例六为基础，还包括：辅助索引表存储模块540、索引匹配模块550和串行重复性判断模块560。其中，辅助索引表存储模块540用于存储辅助索引表，该辅助索引表中包括已存储数据的索引；索引匹配模块550用于当并行重复性判断模块530根据各字符的匹配结果判断出数据与已存储的数据重复之后，将数据的索引在辅助索引表中进行匹配；串行重复性判断模块560用于根据数据在辅助索引表中的匹配结果判断数据是否与已存储的数据重复，若是，则产生数据重复结果，若否，则指示并行重复性判断模块530将数据各字符的参数作为叶节点的参数存储到并行索引树中，并将数据的索引存储在辅助索引表中。

本实施例的技术方案通过并行索引提高了数据重复性校验速度，并通过串行的精确索引保证了数据重复性校验的唯一性和准确性。

在上述技术方案的基础上，进一步还可以包括：字符截取模块570，与参数匹配模块520相连，用于在将数据各字符的参数在并行索引树中分别与叶节点的参数进行匹配之前，从数据中截取设定数量的字符作为在并行索引树中与叶节点的参数进行匹配的各字符。优选是通过截取设定数量字符来控制进行并行索引的工作量。

该装置中优选是还包括：数据转换模块580，与参数匹配模块520相连，用于在将数据各字符的参数在并行索引树中分别与已存储的叶节点的参数进行匹配之前，将数据的各字符分别转换为数据标识，其中，每个叶节点通过字符的数据标识与字符对应，数据的索引为数据标识组成的数字索引串。

通过数据标识来表示数据，能够减少匹配和索引的计算量，还能够使数据索引独立于数据库存储。

实施例八

图7为本发明实施例八提供的数据重复性校验装置中参数匹配模块的结构示意图，本实施例可以以上述实施例六或七为基础，本实施例中，并行索引树的数量为多个，各并行索引树的根节点对应数据字符串的首字符，则参数匹配模块520具体包括：索引树选择单元521、一个或一个以上查找匹配单元522，以及结果产生单元523。其中，索引树选择单元521用于根据数据字符串的首字符选择对应的并行索引树；查找匹配单元522用于针对数据中各字符并行地分别执行查找匹配操作，每个查找匹配单元522包括：层选子单元5221和节点匹配子单元5222。其中，层选子单元5221用于根据数据字符串的长度在选择的并行索引树查找叶节点所在层；节点匹配子单元5222用于根据字符在数据字符串中的位置，在查找到的叶节点所在层中查找匹配的叶节点，产生字符查找匹配结果。结果产生单元523用于当识别到一个字符的字符查找匹配结果为否时，产生数据查找匹配结果，并停止其他字符的查找匹配操作。

在上述方案的基础上，并行索引树的每个叶节点的参数还可以包括字符前坐标和/或后坐标，则每个查找匹配单元522还包括：坐标匹配子单元5223，用于根据字符在数据字符串中的位置，在查找到的叶节点所在层中查找匹配的叶节点之后，产生字符查找匹配结果之前，将字符的前字符和/或后字符与匹配到的叶节点的参数中的前坐标和/或后坐标进行一致性匹配。

实施例九

图8为本发明实施例九提供的数据重复性校验装置的结构示意图，本实施例可以以上述各装置实施例为基础，本实施例中，并行索引树叶节点的参数还可以进一步包括字符出现次数，则该装置还可以包括：次数增加模块590和次数减少模块5100。其中，次数增加模块590用于在将数据各字符的参数作为叶节点的参数存储到并行索引树中之后，将对应叶节点的参数中的字符出现次数加一；次数减少模块5100与并行索引树存储模块510相连，用于当删除数据时，根据删除数据各字符查找并行索引树中的对应叶节点，并将查找到的叶节点的参数中字符出现次数减一。

本发明各实施例的所提供的数据重复性校验装置能够执行本发明数据重复性校验方法任意实施例的技术方案，包括相应的功能模块，有效提高重复性校验效率。

实施例十

图9为本发明实施例十提供的数据应用系统的结构示意图，该系统包括：应用服务器910、校验服务器920和数据库服务器930。其中，应用服务器910用于接收用户输入的数据，将数据提供给校验服务器920进行重复性校验；校验服务器920用于将接收到的数据各字符的参数在并行索引树中分别与叶节点的参数进行匹配，所述并行索引树的每个叶节点分别与一个字符对应，且叶节点的参数至少包括字符所在数据的字符串长度和字符在所述字符串中的位置；根据各字符的匹配结果判断所述数据是否与已存储的数据重复，若否，则将所述数据各字符的参数作为叶节点的参数存储到所述并行索引树中，同时将所述数据提供给数据库服务器930进行存储；数据库服务器930用于将数据进行存储。所谓数据库服务器930，应作广义理解，既可以是存储介质构成的数据库，又可以是文件系统，如内容管理系统(Content Management System，简称CMS)。

本发明实施例所提供的数据应用系统中的校验服务器可以采用本发明实施例提供的数据重复性校验装置，校验服务器可以独立于应用服务器设置，也可以集成在应用服务器之中。应用服务器可以为具备任意应用业务功能的服务器，例如为论坛WEB网页发布服务器，处理用户的登录、注册和论坛访问的业务，应用服务器除了将需要进行重复性校验的数据提供给校验服务器之外，还具有其他响应具体业务的功能。

本发明各实施例的技术方案，以并行索引的深度优先方式提高了重复性校验速率，又能够以先并行再串行的先深度优先再广度优先的方式保证重复性校验的唯一性。现有技术的重复性校验实现方式，数据量增大后对校验效率有很大影响。本发明实施例的技术方案不依赖持久化的应用数据，与使用到的字符有直接关系，校验效率与组成数据的字符个数有直接关系，辅助索引与数据量有间接关系，但是可以按需加载相关数据索引，并且使用“深度优先、广度优先”策略可以极大提高效率，所以数据量即使达到海量对校验效率影响比较小。在需要自动支持系统演变的时候，如从普通的系统变成分布式系统，数据量巨大，需要进行分库。此情况下，现有校验方式不能满足要求，甚至根本不可用，本发明实施例的技术方案只与使用到的字符有直接关系，不管系统是否是分布式，都能使用集中式的校验方式；不管数据量怎么变化，数据都是由字符组成的字符串，校验方式不用变化。本发明实施例的技术方案由于不依赖硬件，所以实现方式性价比很高，尤其是数据量巨大的情况下该优势尤为显著。

本领域普通技术人员可以理解：实现上述方法实施例的全部或部分步骤可以通过程序指令相关的硬件来完成，前述的程序可以存储于一计算机可读取存储介质中，该程序在执行时，执行包括上述方法实施例的步骤；而前述的存储介质包括：ROM、RAM、磁碟或者光盘等各种可以存储程序代码的介质。

最后应说明的是：以上实施例仅用以说明本发明的技术方案，而非对其限制；尽管参照前述实施例对本发明进行了详细的说明，本领域的普通技术人员应当理解：其依然可以对前述各实施例所记载的技术方案进行修改，或者对其中部分技术特征进行等同替换；而这些修改或者替换，并不使相应技术方案的本质脱离本发明各实施例技术方案的精神和范围。

Claims (13)

1.一种数据重复性校验方法，其特征在于，包括：

将数据各字符的参数在并行索引树中分别与叶节点的参数进行匹配，所述并行索引树的每个叶节点分别与一个字符对应，且叶节点的参数至少包括字符所在数据的字符串长度和字符在所述字符串中的位置；

根据各字符的匹配结果判断所述数据是否与已存储的数据重复，若否，则将所述数据各字符的参数作为叶节点的参数存储到所述并行索引树中。

2.根据权利要求1所述的数据重复性校验方法，其特征在于，当根据各字符的匹配结果判断出所述数据与已存储的数据重复之后，还包括：

将所述数据的索引在辅助索引表中进行匹配，所述辅助索引表中包括已存储数据的索引；

根据所述数据在辅助索引表中的匹配结果判断所述数据是否与已存储的数据重复，若是，则产生数据重复结果，若否，则将所述数据各字符的参数作为叶节点的参数存储到所述并行索引树中，并将所述数据的索引存储在辅助索引表中。

3.根据权利要求2所述的数据重复性校验方法，其特征在于，在将数据各字符的参数在并行索引树中分别与叶节点的参数进行匹配之前，还包括：

从所述数据中截取设定数量的字符作为在并行索引树中与叶节点的参数进行匹配的各字符。

4.根据权利要求2所述的数据重复性校验方法，其特征在于，在将数据各字符的参数在并行索引树中分别与已存储的叶节点的参数进行匹配之前，还包括：将所述数据的各字符分别转换为数据标识，其中，每个所述叶节点通过字符的数据标识与所述字符对应，所述数据的索引为数据标识组成的数字索引串。

5.根据权利要求1～4任一所述的数据重复性校验方法，其特征在于，所述并行索引树的数量为多个，各并行索引树的根节点对应数据字符串的首字符，则将数据各字符的参数在并行索引树中分别与叶节点的参数进行匹配包括：

根据所述数据字符串的首字符选择对应的并行索引树；

针对所述数据中各字符分别执行如下查找匹配操作：

根据所述数据字符串的长度在选择的并行索引树查找叶节点所在层；

根据字符在数据字符串中的位置，在查找到的叶节点所在层中查找匹

配的叶节点，产生字符查找匹配结果；

当识别到一个字符的字符查找匹配结果为否时，产生数据查找匹配结果，并停止其他字符的查找匹配操作。

6.根据权利要求5所述的数据重复性校验方法，其特征在于，并行索引树的每个叶节点的参数还包括字符前坐标和/或后坐标，则根据字符在数据字符串中的位置，在查找到的叶节点所在层中查找匹配的叶节点之后，产生字符查找匹配结果之前，所述步骤还包括：

将字符的前字符和/或后字符与匹配到的叶节点的参数中的前坐标和/或后坐标进行一致性匹配。

7.根据权利要求1～4任一所述的数据重复性校验方法，其特征在于，叶节点的参数还包括字符出现次数，则将所述数据各字符的参数作为叶节点的参数存储到所述并行索引树中之后，还包括：

将对应叶节点的参数中的字符出现次数加一；

当删除数据时，根据删除数据各字符查找并行索引树中的对应叶节点，并将查找到的叶节点的参数中字符出现次数减一。

8.一种数据重复性校验装置，其特征在于，包括：

并行索引树存储模块，用于存储并行索引树中各叶节点的参数，所述并行索引树的每个叶节点分别与一个字符对应，且叶节点的参数至少包括字符所在数据的字符串长度和字符在所述字符串中的位置；

参数匹配模块，用于将数据各字符的参数在并行索引树中分别与叶节点的参数进行匹配；

并行重复性判断模块，用于根据各字符的匹配结果判断所述数据是否与已存储的数据重复，若否，则将所述数据各字符的参数作为叶节点的参数存储到所述并行索引树中。

9.根据权利要求8所述的数据重复性校验装置，其特征在于，还包括：

辅助索引表存储模块，用于存储辅助索引表，所述辅助索引表中包括已存储数据的索引；

索引匹配模块，用于当所述并行重复性判断模块根据各字符的匹配结果判断出所述数据与已存储的数据重复之后，将所述数据的索引在辅助索引表中进行匹配；

串行重复性判断模块，用于根据所述数据在辅助索引表中的匹配结果判断所述数据是否与已存储的数据重复，若是，则产生数据重复结果，若否，则指示并行重复性判断模块将所述数据各字符的参数作为叶节点的参数存储到所述并行索引树中，并将所述数据的索引存储在辅助索引表中；

字符截取模块，用于在将数据各字符的参数在并行索引树中分别与叶节点的参数进行匹配之前，从所述数据中截取设定数量的字符作为在并行索引树中与叶节点的参数进行匹配的各字符；

数据转换模块，用于在将数据各字符的参数在并行索引树中分别与已存储的叶节点的参数进行匹配之前，将所述数据的各字符分别转换为数据标识，其中，每个所述叶节点通过字符的数据标识与所述字符对应，所述数据的索引为数据标识组成的数字索引串。

10.根据权利要求8所述的数据重复性校验装置，其特征在于，所述并行索引树的数量为多个，各并行索引树的根节点对应数据字符串的首字符，则参数匹配模块包括：

索引树选择单元，用于根据所述数据字符串的首字符选择对应的并行索引树；

一个或一个以上查找匹配单元，用于针对所述数据中各字符并行地分别执行查找匹配操作，每个所述查找匹配单元包括：

层选子单元，用于根据所述数据字符串的长度在选择的并行索引树查

找叶节点所在层；

节点匹配子单元，用于根据字符在数据字符串中的位置，在查找到的

叶节点所在层中查找匹配的叶节点，产生字符查找匹配结果；

结果产生单元，用于当识别到一个字符的字符查找匹配结果为否时，产生数据查找匹配结果，并停止其他字符的查找匹配操作。

11.根据权利要求10所述的数据重复性校验装置，其特征在于，每个叶节点的参数还包括字符前坐标和/或后坐标，每个所述查找匹配单元还包括：

坐标匹配子单元，用于根据字符在数据字符串中的位置，在查找到的叶节点所在层中查找匹配的叶节点之后，产生字符查找匹配结果之前，将字符的前字符和/或后字符与匹配到的叶节点的参数中的前坐标和/或后坐标进行一致性匹配。

12.根据权利要求8所述的数据重复性校验装置，其特征在于，并行索引树叶节点的参数还包括字符出现次数，所述装置还包括：

次数增加模块，用于在将所述数据各字符的参数作为叶节点的参数存储到所述并行索引树中之后，将对应叶节点的参数中的字符出现次数加一；

次数减少模块，用于当删除数据时，根据删除数据各字符查找并行索引树中的对应叶节点，并将查找到的叶节点的参数中字符出现次数减一。

13.一种数据应用系统，其特征在于，包括：

应用服务器，用于接收用户输入的数据，将数据提供给校验服务器进行重复性校验；

校验服务器，用于将接收到的数据各字符的参数在并行索引树中分别与叶节点的参数进行匹配，所述并行索引树的每个叶节点分别与一个字符对应，且叶节点的参数至少包括字符所在数据的字符串长度和字符在所述字符串中的位置；根据各字符的匹配结果判断所述数据是否与已存储的数据重复，若否，则将所述数据各字符的参数作为叶节点的参数存储到所述并行索引树中，同时将所述数据提供给数据库服务器进行存储；

数据库服务器，用于将所述数据进行存储。

Images