CN111400320B - 用于生成信息的方法和装置 - Google Patents

Abstract

本申请实施例公开了用于生成信息的方法和装置。该方法的一具体实施方式包括：从键值数据库导出键元数据集合，其中，每条键元数据包括键和值占用容量；将键元数据集合写入统计树；基于统计树，生成键值数据库的存储分布信息。该实施方式提供了一种新的键值数据库的存储分布的分析方式。

Description

用于生成信息的方法和装置

技术领域

本申请实施例涉及计算机技术领域，具体涉及用于生成信息的方法和装置。

背景技术

键值数据库目前已经被业界广泛使用。同时，键值数据库因其灵活性和分布式的特点，能够承载大量数据而性能不会产生明显的下降。也正因其灵活性技术人员在使用时通常不会太关注存储的使用情况，往往直到集群存储空间即将达到极限才会去关注内部存储的数据情况，尝试进行一定优化提高集群利用率。

目前，键值数据库存储分析方法主要包括以下三种：其一，针对键值数据库中所有键容量进行倒排，分析出占用容量大的键。其二，根据已知的键模板或者前缀进行汇总该类键容量情况，进而分析容量使用情况。其三，抽样小部分键进行人工分析。

发明内容

本申请实施例提出了用于生成信息的方法和装置。

第一方面，本申请实施例提出了一种用于生成信息的方法，包括：从键值数据库导出键元数据集合，其中，每条键元数据包括键和值占用容量；将键元数据集合写入统计树；基于统计树，生成键值数据库的存储分布信息。

在一些实施例中，将键元数据集合写入统计树，包括：对键元数据集合中的键进行分割，生成元素序列集合；对于元素序列集合中的元素序列，将该元素序列的元素依次插入统计树，其中，元素在该元素序列中的位次与该元素在统计树中的层次对应；基于键元数据集合中的值占用容量，更新统计树中的节点中的键数目和值占用容量。

在一些实施例中，对键元数据集合中的键进行分割，生成元素序列集合，包括：对于键元数据集合中的键，确定该键中的目标分隔符；基于目标分隔符将该键拆分成元素序列。

在一些实施例中，确定该键中的目标分隔符，包括：统计预设分隔符集合中的预设分割符在该键中出现的频次；基于所统计出的频次，从预设分隔符集合中确定目标分隔符。

在一些实施例中，将该元素序列的元素依次插入统计树，包括：对于该元素序列的当前元素，确定当前元素在统计树中的位置，以及将当前元素插入位置处。

在一些实施例中，确定当前元素在统计树中的位置，以及将当前元素插入位置处，包括：执行以下插入步骤：将当前元素在统计树中的当前元素的上一元素对应的节点的子节点集合中进行匹配；若匹配成功，确定当前元素已被插入统计树中；确定当前元素是否是该元素序列中的最后元素；若是最后元素，确定该元素序列已被插入统计树。

在一些实施例中，确定当前元素在统计树中的位置，以及将当前元素插入位置处，还包括：响应于确定当前元素不是该元素序列中的最后元素，将该元素序列的下一元素作为当前元素，以及继续执行插入步骤。

在一些实施例中，确定当前元素在统计树中的位置，以及将当前元素插入位置处，还包括：若当前元素在统计树中的当前元素的上一元素对应的节点的子节点集合中匹配失败，为当前元素的上一元素对应的节点创建当前元素对应的子节点。

在一些实施例中，确定当前元素在统计树中的位置，以及将当前元素插入位置处，还包括：确定当前元素的上一元素对应的节点的子节点数目是否满足合并条件；若满足合并条件，将当前元素的上一元素对应的节点的至少部分子节点合并成通配符子节点。

在一些实施例中，合并条件包括以下至少一项：子节点数目超过预设子节点数目阈值、统计树的全局节点数目超过预设全局节点数据阈值。

在一些实施例中，确定当前元素在统计树中的位置，以及将当前元素插入位置处，还包括：将创建在统计树中的同一节点下的数字对应的叶子节点合并成通配符叶子节点。

在一些实施例中，基于统计树，生成键值数据库的存储分布信息，包括：遍历统计树，生成键值数据库的存储分布信息。

在一些实施例中，遍历统计树，生成键值数据库的存储分布信息，包括：对统计树进行前序遍历，输出匹配字符串集合以及每条匹配字符串的占用容量；根据所输出的占用容量对匹配字符串集合进行排序，以及基于排序结果，生成键值数据库的存储分布信息。

在一些实施例中，基于排序结果，生成键值数据库的存储分布信息，包括：基于排序结果，从匹配字符串集合中选取目标字符串；对目标字符串进行通配符展开，得到展开字符串集合以及每个展开字符串的占用容量。

第二方面，本申请实施例提出了一种用于生成信息的装置，包括：导出单元，被配置成从键值数据库导出键元数据集合，其中，每条键元数据包括键和值占用容量；写入单元，被配置成将键元数据集合写入统计树；生成单元，被配置成基于统计树，生成键值数据库的存储分布信息。

在一些实施例中，写入单元，包括：分割子单元，被配置成对键元数据集合中的键进行分割，生成元素序列集合；插入子单元，被配置成对于元素序列集合中的元素序列，将该元素序列的元素依次插入统计树，其中，元素在该元素序列中的位次与该元素在统计树中的层次对应；更新子单元，被配置成基于键元数据集合中的值占用容量，更新统计树中的节点中的键数目和值占用容量。

在一些实施例中，分割子单元包括：确定模块，被配置成对于键元数据集合中的键，确定该键中的目标分隔符；拆分模块，被配置成基于目标分隔符将该键拆分成元素序列。

在一些实施例中，确定模块包括：统计子模块，被配置成统计预设分隔符集合中的预设分割符在该键中出现的频次；第一确定子模块，被配置成基于所统计出的频次，从预设分隔符集合中确定目标分隔符。

在一些实施例中，插入子单元包括：插入模块，被配置成对于该元素序列的当前元素，确定当前元素在统计树中的位置，以及将当前元素插入位置处。

在一些实施例中，插入模块包括：插入子模块，被配置成执行以下插入步骤：对于该元素序列的当前元素，将当前元素在统计树中的当前元素的上一元素对应的节点的子节点集合中进行匹配；若匹配成功，确定当前元素已被插入统计树中；确定当前元素是否是该元素序列中的最后元素；若是最后元素，确定该元素序列已被插入统计树。

在一些实施例中，插入模块还包括：循环子模块，被配置成响应于确定当前元素不是该元素序列中的最后元素，将该元素序列的下一元素作为当前元素，以及继续执行插入步骤。

在一些实施例中，插入模块还包括：创建子模块，被配置成若当前元素在统计树中的当前元素的上一元素对应的节点的子节点集合中匹配失败，为当前元素的上一元素对应的节点创建当前元素对应的子节点。

在一些实施例中，插入模块还包括：第二确定子模块，被配置成确定当前元素的上一元素对应的节点的子节点数目是否满足合并条件；第一合并子模块，被配置成若满足合并条件，将当前元素的上一元素对应的节点的至少部分子节点合并成通配符子节点。

在一些实施例中，合并条件包括以下至少一项：子节点数目超过预设子节点数目阈值、统计树的全局节点数目超过预设全局节点数据阈值。

在一些实施例中，插入模块还包括：第二合并子模块，被配置成将创建在统计树中的同一节点下的数字对应的叶子节点合并成通配符叶子节点。

在一些实施例中，生成单元包括：遍历子单元，被配置成遍历统计树，生成键值数据库的存储分布信息。

在一些实施例中，遍历子单元包括：遍历模块，被配置成对统计树进行前序遍历，输出匹配字符串集合以及每条匹配字符串的占用容量；生成模块，被配置成根据所输出的占用容量对匹配字符串集合进行排序，以及基于排序结果，生成键值数据库的存储分布信息。

在一些实施例中，生成模块包括：选取子模块，被配置成基于排序结果，从匹配字符串集合中选取目标字符串；展开子模块，被配置成对目标字符串进行通配符展开，得到展开字符串集合以及每个展开字符串的占用容量。

第三方面，本申请实施例提供了一种电子设备，该电子设备包括：一个或多个处理器；存储装置，其上存储有一个或多个程序；当一个或多个程序被一个或多个处理器执行，使得一个或多个处理器实现如第一方面中任一实现方式描述的方法。

第四方面，本申请实施例提供了一种计算机可读介质，其上存储有计算机程序，该计算机程序被处理器执行时实现如第一方面中任一实现方式描述的方法。

本申请实施例提供的用于生成信息的方法和装置，首先从键值数据库导出键元数据集合；然后将键元数据集合写入统计树；最后基于统计树，生成键值数据库的存储分布信息。提供了一种新的键值数据库的存储分布的分析方式。

附图说明

通过阅读参照以下附图所作的对非限制性实施例所作的详细描述，本申请的其它特征、目的和优点将会变得更明显：

图1是本申请可以应用于其中的示例性系统架构；

图2是根据本申请的用于生成信息的方法的一个实施例的流程图；

图3是根据本申请的用于生成信息的方法的又一个实施例的流程图；

图4是根据本申请的用于生成信息的方法的另一个实施例的流程图；

图5是根据本申请的用于生成信息的方法的一个应用场景的流程图；

图6A示出了入树过程的一个示意图；

图6B示出了合并过程的一个示意图；

图6C示出了入树过程的又一个示意图；

图6D示出了合并过程的又一个示意图；

图6E示出了合并过程的另一个示意图；

图7是根据本申请的用于生成信息的装置的一个实施例的结构示意图；

图8是适于用来实现本申请实施例的电子设备的计算机系统的结构示意图。

具体实施方式

下面结合附图和实施例对本申请作进一步的详细说明。可以理解的是，此处所描述的具体实施例仅仅用于解释相关发明，而非对该发明的限定。另外还需要说明的是，为了便于描述，附图中仅示出了与有关发明相关的部分。

需要说明的是，在不冲突的情况下，本申请中的实施例及实施例中的特征可以相互组合。下面将参考附图并结合实施例来详细说明本申请。

图1示出了可以应用本申请的用于生成信息的方法或用于生成信息的装置的实施例的示例性系统架构100。

如图1所示，系统架构100中可以包括键值数据库101、网络102和服务器103。网络102用以在键值数据库101和服务器103之间提供通信链路的介质。网络102可以包括各种连接类型，例如有线、无线通信链路或者光纤电缆等等。

键值数据库101可以用于以key-value键值对的形式存储数据。

服务器103可以提供各种服务。例如，服务器103可以对从键值数据库101导出的键元数据集合等数据进行分析等处理，并生成处理结果(例如键值数据库的存储分布信息)。

需要说明的是，服务器103可以是硬件，也可以是软件。当服务器103为硬件时，可以实现成多个服务器组成的分布式服务器集群，也可以实现成单个服务器。当服务器103为软件时，可以实现成多个软件或软件模块(例如用来提供分布式服务)，也可以实现成单个软件或软件模块。在此不做具体限定。

需要说明的是，本申请实施例所提供的用于生成信息的方法一般由服务器103执行，相应地，用于生成信息的装置一般设置于服务器103中。

继续参考图2，其示出了根据本申请的用于生成信息的方法的一个实施例的流程200。该用于生成信息的方法包括以下步骤：

步骤201，从键值数据库导出键元数据集合。

在本实施例中，用于生成信息的方法的执行主体(例如图1所示的服务器103)可以从键值数据库(例如图1所示的键值数据库101)导出键元数据集合。其中，键元数据集合中的每条键元数据可以包括键(key)，以及键所存储的值(value)的占用容量。

实践中，键值数据库又叫做KV数据库，其通常只能通过键进行资源分类。而在一般情况下会使用特定分隔符将键设计成多段，其中就包括固定字符段和数据段。固定字符段可以用来唯一描述一类数据，而数据段可以用来描述这类数据中的唯一一条记录。例如，在键值数据库中存储用户数据，键可以设计为：key：prefix_user_${uid}。其中，prefix_user_为固定字符段，表示这个固定字符段用来维护用户数据集合。${uid}为用户的唯一标识。因此，每个用户对应唯一一个键。需要说明的是，本申请在键值数据库中自动发现prefix_user_这个固定字符段，实现无人工干预自动分析键元数据的存储分布。本申请是建立在具备固定字符段描述唯一数据集合的基础下实现的。

步骤202，将键元数据集合写入统计树。

在本实施例中，上述执行主体可以将键元数据集合写入统计树。具体地，对于键元数据集合中的每条键元数据，上述执行主体可以先将该键元数据中的键写入统计树的路径上，再基于每条键元数据中的值占用容量更新该路径上的占用容量。

步骤203，基于统计树，生成键值数据库的存储分布信息。

在本实施例中，上述执行主体可以基于统计树，生成键值数据库的存储分布信息。例如，上述执行主体可以输出统计树中占用容量排名靠前(例如前10)的路径上的字符串以及对应的占用容量，作为键值数据库的存储分布信息。

本申请实施例提供的用于生成信息的方法，首先从键值数据库导出键元数据集合；然后将键元数据集合写入统计树；最后基于统计树，生成键值数据库的存储分布信息。提供了一种新的键值数据库的存储分布的分析方式。

进一步参考图3，其示出了根据本申请的用于生成信息的方法的又一个实施例的流程300。该用于生成信息的方法包括以下步骤：

步骤301，从键值数据库导出键元数据集合。

在本实施例中，步骤301具体操作已在图2所示的实施例中步骤201中进行了详细的介绍，在此不再赘述。

步骤302，对键元数据集合中的键进行分割，生成元素序列集合。

在本实施例中，对于键元数据集合中的键元数据，上述执行主体可以对该键元数据中的键进行分割，生成元素序列。具体地，上述执行主体可以将键分割成多个元素，并按照每个元素在键中出现的先后顺序进行排列，生成元素序列。例如，上述执行主体可以按照固定字符长度(例如1个字符、2个字符)对键进行分割，以得到元素序列。

在本实施例的一些可选的实现方式中，上述执行主体可以首先确定键中的目标分隔符；然后基于目标分隔符将键拆分成元素序列。其中，目标分割符可以是键中出现的分隔符中的一种或多种。例如，上述执行主体可以将键中经常出现的分隔符作为目标分割符。又例如，上述执行主体可以首先统计预设分隔符集合中的预设分割符在键中出现的频次；然后基于所统计出的频次，从预设分隔符集合中确定目标分隔符。通常，出现频次最高的预设分割符是键的目标分隔符。其中，预设分隔符集合中可以包括但不限于“_”、“：”、“{”、“}”等多种分隔符。

需要说明的是，若键中的目标分隔符确定失败，则不进行拆分而将整体的键作为一个元素。

步骤303，对于元素序列集合中的元素序列，将该元素序列的元素依次插入统计树。

在本实施例中，对于元素序列集合中的元素序列，上述执行主体可以将该元素序列中的元素依次插入统计树。其中，对于一个元素序列，该元素序列中的一个元素插入统计树中的一层的一个节点，且元素在该元素序列中的位次与该元素在统计树中的层次对应。

在本实施例的一些可选的实现方式中，对于该元素序列的当前元素，上述执行主体可以确定当前元素在统计树中的位置，以及将当前元素插入该位置处。

步骤304，基于键元数据集合中的值占用容量，更新统计树中的节点中的键数目和值占用容量。

在本实施例中，对于键元数据集合中的键元数据，上述执行主体可以对该键元数据中的值占用容量，更新统计树中的节点中的键数目和值占用容量。其中，统计树中一个节点插入的元素数目等于节点中的键数目，且插入的元素对应的所有键元数据中的值占用容量之和等于节点中的值占用容量。

步骤305，遍历统计树，生成键值数据库的存储分布信息。

在本实施例中，上述执行主体可以遍历统计树，生成键值数据库的存储分布信息。例如，上述执行主体可以对统计树进行前序遍历，输出匹配字符串集合以及每条匹配字符串的占用容量，作为键值数据库的存储分布信息。其中，匹配字符串集合中的一个匹配字符串可以由统计树中从根节点到叶子节点的一条路径上的所有节点插入的元素组成。进一步地，上述执行主体还可以根据所输出的占用容量对匹配字符串集合进行排序，以及基于排序结果，生成键值数据库的存储分布信息。例如，将排序后的匹配字符串集合以及每条匹配字符串的占用容量作为键值数据库的存储分布信息。又例如，从排序后的匹配字符串集合中选取出占用容量排名前10的匹配字符串，以及将选取出的匹配字符串以及每条匹配字符串的占用容量作为键值数据库的存储分布信息。

从图3中可以看出，与图2对应的实施例相比，本实施例中的用于生成信息的方法的流程300突出了写入步骤和生成步骤。由此，本实施例描述的方案首先对键元数据集合中的键进行分割，生成元素序列集合；之后对于元素序列集合中的元素序列，将该元素序列的元素依次插入统计树；然后基于键元数据集合中的值占用容量，更新统计树中的节点中的键数目和值占用容量；最后遍历统计树，生成键值数据库的存储分布信息。将键元数据集合中的键插入统计树，通过遍历统计树得到键值数据库的存储分布信息，提高对键值数据库的存储分布的分析准确度。此外，还提高对键值数据库的存储分布的分析效率。

进一步参考图4，其示出了根据本申请的用于生成信息的方法的另一个实施例的流程400。该用于生成信息的方法包括以下步骤：

步骤401，从键值数据库导出键元数据集合。

步骤402，对键元数据集合中的键进行分割，生成元素序列集合。

在本实施例中，步骤401-402具体操作已在图3所示的实施例中步骤301-302中进行了详细的介绍，在此不再赘述。

步骤403，对于元素序列集合中的元素序列的当前元素，确定当前元素在统计树中的当前元素的上一元素对应的节点的子节点集合中是否匹配成功。

在本实施例中，对于元素序列集合中的元素序列，上述执行主体可以将该元素序列中的当前元素在统计树中的当前元素的上一元素对应的节点的子节点集合中匹配，确定当前元素在其上一元素对应的节点的子节点集合中是否匹配成功。通常，上述执行主体可以确定当前元素的上一元素对应的节点是否存在当前元素对应的子节点。若存在，则匹配成功，执行步骤404；若不存在，则匹配失败，执行步骤405。

步骤404，确定当前元素已被插入统计树中。

在本实施例中，若当前元素在其上一元素对应的节点的子节点集合中匹配成功，则确定当前元素已被插入统计树中。此时，上述执行主体可以直接执行步骤406。

步骤405，为当前元素的上一元素对应的节点创建当前元素对应的子节点。

在本实施例中，若当前元素在其上一元素对应的节点的子节点集合中匹配失败，则确定当前元素尚未被插入统计树中。此时，上述执行主体可以先为当前元素的上一元素对应的节点创建当前元素对应的子节点，再执行步骤406。

需要说明的是，在元素序列集合中的元素序列均未插入统计树时，统计树可以为空。若要将第一个元素序列中的第一个元素插入统计树，则可以在统计树中创建第一个元素对应的根节点。随后，对于除第一个元素之外的任意一个元素均执行步骤403-405。

步骤406，确定当前元素的上一元素对应的节点的子节点数目是否满足合并条件。

在本实施例中，上述执行主体可以确定当前元素的上一元素对应的节点的子节点数目是否满足合并条件。若满足合并条件，则先执行步骤407，再执行步骤408；若不满足合并条件，则直接执行步骤408。

在本实施例中，合并条件可以包括预先设置的一个或多个条件。通常，合并条件可以是用于描述同一节点的子节点数目过多和/或统计树的节点数目过多的条件。合并条件主要是阈值判断，例如，合并条件可以包括但不限于以下至少一项：子节点数目超过预设子节点数目阈值、统计树的全局节点数目超过预设全局节点数据阈值等等。其中，子节点数目超过预设子节点数目阈值可以是区分统计树深度的情况，不同深度的节点阈值可以不同。统计树的全局节点数目超过预设全局节点数据阈值可以是不区分统计树深度的情况，是全局统一的阈值。

步骤407，将当前元素的上一元素对应的节点的至少部分子节点合并成通配符子节点。

在本实施例中，若满足合并条件，上述执行主体可以将当前元素的上一元素对应的节点的至少部分子节点合并成通配符子节点。通常，上述执行主体可以根据预定义的变量筛选函数筛选至少部分子节点进行合并。例如，上述执行主体可以将当前元素的上一元素对应的节点的全部子节点合并成一个通配符子节点，后续所有该位置的元素统计都并入这个通配符子节点。又例如，上述执行主体可以仅将数字对应的子节点合并成一个通配符子节点，后续所有该位置的数字元素统计都并入这个通配符子节点。

步骤408，确定当前元素是否是该元素序列中的最后元素。

在本实施例中，上述执行主体可以确定当前元素是否是该元素序列中的最后元素。若是最后元素，则执行步骤409；若不是最后元素，则执行步骤410。

步骤409，确定该元素序列已被插入统计树。

在本实施例中，若当前元素是该元素序列中的最后元素，则确定该元素序列已被插入统计树。当元素序列集合中的所有元素序列均已被插入统计树时，执行步骤411。

步骤410，将该元素序列的下一元素作为当前元素。

在本实施例中，若当前元素不是该元素序列中的最后元素，则确定该元素序列存在尚未被插入统计树的元素。此时，上述执行主体可以将该元素序列的下一元素作为当前元素，以及继续执行步骤403。如此循环往复，直至元素序列集合中的所有元素序列均已被插入统计树。

在本实施例的一些可选的实现方式中，上述执行主体还可以将创建在统计树中的同一节点下的数字对应的叶子节点合并成通配符叶子节点。

步骤411，基于键元数据集合中的值占用容量，更新统计树中的节点中的键数目和值占用容量。

在本实施例中，步骤411具体操作已在图4所示的实施例中步骤404中进行了详细的介绍，在此不再赘述。

步骤412，对统计树进行前序遍历，输出匹配字符串集合以及每条匹配字符串的占用容量。

在本实施例中，上述执行主体可以对统计树进行前序遍历，输出匹配字符串集合以及每条匹配字符串的占用容量。其中，匹配字符串集合中的一个匹配字符串可以由统计树中从根节点到叶子节点的一条路径上的所有节点插入的元素组成。匹配字符串的占用容量可以等于其对应的所有键元数据中的值占用容量之和，也就是，该匹配字符串对应的路径上的叶子节点中的值占用容量。

步骤413，根据所输出的占用容量对匹配字符串集合进行排序。

在本实施例中，上述执行主体可以根据所输出的占用容量对匹配字符串集合进行排序。例如，上述执行主体可以按照占用容量从大到小的顺序对匹配字符串集合进行排序。

步骤414，基于排序结果，从匹配字符串集合中选取目标字符串。

在本实施例中，上述执行主体可以基于排序结果，从匹配字符串集合中选取目标字符串。例如，上述执行主体可以从匹配字符串集合中选取出排序在第一位的匹配字符串，作为目标字符串。

步骤415，对目标字符串进行通配符展开，得到展开字符串集合以及每个展开字符串的占用容量。

在本实施例中，上述执行主体可以对目标字符串进行通配符展开，得到展开字符串集合以及每个展开字符串的占用容量。

通常，若目标字符串中仅包含一个通配符，上述执行主体可以将该通配符展开，得到该通配符覆盖的所有展开字符串以及每个展开字符串的占用容量。随后，上述执行主体可以基于占用容量对所有展开字符串进行排序，并选取排序在前10位的展开字符串以及每个展开字符串的占用容量，作为键值数据库的存储分布信息。若目标字符串中包含至少两个通配符，上述执行主体可以首先将第一个通配符展开，得到第一个通配符覆盖的所有展开字符串以及每个展开字符串的占用容量；然后基于占用容量对所有展开字符串进行排序，并选取排序在前10位的展开字符串；最后将所选取的展开字符串的第二个通配符展开，得到第二个通配符覆盖的所有展开字符串以及每个展开字符串的占用容量，循环选取和展开，直至展开字符串的占用容量低于50％为止。

为了便于理解，下面提供本申请实施例的用于生成信息的方法的一个应用场景。该应用场景的流程图如图5所示，包括如下步骤：

步骤501，键值数据库键元数据集合提取。

步骤502，提取一条键元数据。

步骤503，分隔符分析。

步骤504，元素拆分。

步骤505，取第一个元素开始建树。

步骤506，是否没有元素。

步骤507，寻找子节点。

步骤508，创建子节点。

步骤509，子节点元素过多。

步骤510，合并当前节点下多个子节点生成聚合节点。

步骤511，取下一个元素，以及基于子节点继续建树。

步骤512，更新节点键的数量和占用量容量。

步骤513，是否没有键元数据。

步骤514，排序输出统计树。

步骤515，展开第一个通配符，统计展开字符串。

步骤516，查找占用容量大于50％的展开字符串。

步骤517，输出通配符展开结果。

此外，以从键值数据库导出的键元数据集合包括如下8个键：a_b_c_1、a_b_c_2、a_b_c_3、a_1_b_2、a_2_b_3、a_3_b_4、a_4_b_5和a_1_b_6为例继续说明。首先，将a_b_c_1、a_b_c_2和a_b_c_3入树。具体参见图6A，其示出了该入树过程的示意图。在建立3个叶子节点后发现c节点下存在大量数字节点，自动化合并成通配符*节点。具体参见图6B，其示出了该合并过程的示意图。之后，将a_1_b_2、a_2_b_3、a_3_b_4继续入树。具体参见图6C，其示出了该入树过程的示意图。由于a节点下存在较多二级节点，其中的数字节点自动化合并成通配符*节点。具体参见图6D，其示出了该合并过程的示意图。而合并过程中发现合并后的b节点下同样存在大量节点，递归合并成通配符*节点。具体参见图6E，其示出了该合并过程的示意图。而后，a_4_b_5和a_1_b_6继续入树，因为与a_*_b_*匹配不变更树结构，只更新统计信息，最终建树结束，输出第一阶段结果：a_*_b_*62.5％和a_b_c_*37.5％。然后，通过第一阶段结果的分析发现核心容量主要集中在a_*_b_*这个模式中，第二阶段对两个通配符展开得到：a_1_b_*25％、a_2_b_*12.5％、a_3_b_*12.5％、a_4_b_*12.5％、a_*_b_2 12.5％、a_*_b_3 12.5％、a_*_b_4 12.5％、a_*_b_5 12.5％和a_*_b_6 12.5％。最后，进一步定位主要问题集中在a_1_b_*这个模式中，针对这个模式继续深入分析，给出对应的解决方案。

从图4中可以看出，与图3对应的实施例相比，本实施例中的用于生成信息的方法的流程400突出了插入步骤和遍历步骤。由此，本实施例描述的方案基于元素匹配方式在统计树中插入元素，避免了统计树中的路径重复。此外，通过节点合并方式将键值数据库的存储内容合并成有限的几个合并结果，通过分析有限的几个合并结果，能够提高存储分布的分析效率，进而缩短了键值数据库存储瓶颈的定位时间，有利于快速给出对应的解决方案。

进一步参考图7，作为对上述各图所示方法的实现，本申请提供了一种用于生成信息的装置的一个实施例，该装置实施例与图2所示的方法实施例相对应，该装置具体可以应用于各种电子设备中。

如图7所示，本实施例的用于生成信息的装置700可以包括：导出单元701、写入单元702和生成单元703。其中，导出单元701，被配置成从键值数据库导出键元数据集合，其中，每条键元数据包括键和值占用容量；写入单元702，被配置成将键元数据集合写入统计树；生成单元703，被配置成基于统计树，生成键值数据库的存储分布信息。

在本实施例中，用于生成信息的装置700中：导出单元701、写入单元702和生成单元703的具体处理及其所带来的技术效果可分别参考图2对应实施例中的步骤201-203的相关说明，在此不再赘述。

在本实施例的一些可选的实现方式中，写入单元702，包括：分割子单元(图中未示出)，被配置成对键元数据集合中的键进行分割，生成元素序列集合；插入子单元(图中未示出)，被配置成对于元素序列集合中的元素序列，将该元素序列的元素依次插入统计树，其中，元素在该元素序列中的位次与该元素在统计树中的层次对应；更新子单元(图中未示出)，被配置成基于键元数据集合中的值占用容量，更新统计树中的节点中的键数目和值占用容量。

在本实施例的一些可选的实现方式中，分割子单元包括：确定模块(图中未示出)，被配置成对于键元数据集合中的键，确定该键中的目标分隔符；拆分模块(图中未示出)，被配置成基于目标分隔符将该键拆分成元素序列。

在本实施例的一些可选的实现方式中，确定模块包括：统计子模块(图中未示出)，被配置成统计预设分隔符集合中的预设分割符在该键中出现的频次；第一确定子模块(图中未示出)，被配置成基于所统计出的频次，从预设分隔符集合中确定目标分隔符。

在本实施例的一些可选的实现方式中，插入子单元包括：插入模块(图中未示出)，被配置成对于该元素序列的当前元素，确定当前元素在统计树中的位置，以及将当前元素插入位置处。

在本实施例的一些可选的实现方式中，插入模块包括：插入子模块(图中未示出)，被配置成执行以下插入步骤：对于该元素序列的当前元素，将当前元素在统计树中的当前元素的上一元素对应的节点的子节点集合中进行匹配；若匹配成功，确定当前元素已被插入统计树中；确定当前元素是否是该元素序列中的最后元素；若是最后元素，确定该元素序列已被插入统计树。

在本实施例的一些可选的实现方式中，插入模块还包括：循环子模块(图中未示出)，被配置成响应于确定当前元素不是该元素序列中的最后元素，将该元素序列的下一元素作为当前元素，以及继续执行插入步骤。

在本实施例的一些可选的实现方式中，插入模块还包括：创建子模块(图中未示出)，被配置成若当前元素在统计树中的当前元素的上一元素对应的节点的子节点集合中匹配失败，为当前元素的上一元素对应的节点创建当前元素对应的子节点。

在本实施例的一些可选的实现方式中，插入模块还包括：第二确定子模块(图中未示出)，被配置成确定当前元素的上一元素对应的节点的子节点数目是否满足合并条件；第一合并子模块(图中未示出)，被配置成若满足合并条件，将当前元素的上一元素对应的节点的至少部分子节点合并成通配符子节点。

在本实施例的一些可选的实现方式中，合并条件包括以下至少一项：子节点数目超过预设子节点数目阈值、统计树的全局节点数目超过预设全局节点数据阈值。

在本实施例的一些可选的实现方式中，插入模块还包括：第二合并子模块(图中未示出)，被配置成将创建在统计树中的同一节点下的数字对应的叶子节点合并成通配符叶子节点。

在本实施例的一些可选的实现方式中，生成单元703包括：遍历子单元(图中未示出)，被配置成遍历统计树，生成键值数据库的存储分布信息。

在本实施例的一些可选的实现方式中，遍历子单元包括：遍历模块(图中未示出)，被配置成对统计树进行前序遍历，输出匹配字符串集合以及每条匹配字符串的占用容量；生成模块(图中未示出)，被配置成根据所输出的占用容量对匹配字符串集合进行排序，以及基于排序结果，生成键值数据库的存储分布信息。

在本实施例的一些可选的实现方式中，生成模块包括：选取子模块(图中未示出)，被配置成基于排序结果，从匹配字符串集合中选取目标字符串；展开子模块(图中未示出)，被配置成对目标字符串进行通配符展开，得到展开字符串集合以及每个展开字符串的占用容量。

下面参考图8，其示出了适于用来实现本申请实施例的电子设备(例如图1所示的服务器103)的计算机系统800的结构示意图。图8示出的电子设备仅仅是一个示例，不应对本申请实施例的功能和使用范围带来任何限制。

如图8所示，计算机系统800包括中央处理单元(CPU)801，其可以根据存储在只读存储器(ROM)802中的程序或者从存储部分808加载到随机访问存储器(RAM)803中的程序而执行各种适当的动作和处理。在RAM 803中，还存储有系统800操作所需的各种程序和数据。CPU 801、ROM 802以及RAM 803通过总线804彼此相连。输入/输出(I/O)接口805也连接至总线804。

以下部件连接至I/O接口805：包括键盘、鼠标等的输入部分806；包括诸如阴极射线管(CRT)、液晶显示器(LCD)等以及扬声器等的输出部分807；包括硬盘等的存储部分808；以及包括诸如LAN卡、调制解调器等的网络接口卡的通信部分809。通信部分809经由诸如因特网的网络执行通信处理。驱动器810也根据需要连接至I/O接口805。可拆卸介质811，诸如磁盘、光盘、磁光盘、半导体存储器等等，根据需要安装在驱动器810上，以便于从其上读出的计算机程序根据需要被安装入存储部分808。

特别地，根据本公开的实施例，上文参考流程图描述的过程可以被实现为计算机软件程序。例如，本公开的实施例包括一种计算机程序产品，其包括承载在计算机可读介质上的计算机程序，该计算机程序包含用于执行流程图所示的方法的程序代码。在这样的实施例中，该计算机程序可以通过通信部分809从网络上被下载和安装，和/或从可拆卸介质811被安装。在该计算机程序被中央处理单元(CPU)801执行时，执行本申请的方法中限定的上述功能。

需要说明的是，本申请所述的计算机可读介质可以是计算机可读信号介质或者计算机可读存储介质或者是上述两者的任意组合。计算机可读存储介质例如可以是——但不限于——电、磁、光、电磁、红外线、或半导体的系统、装置或器件，或者任意以上的组合。计算机可读存储介质的更具体的例子可以包括但不限于：具有一个或多个导线的电连接、便携式计算机磁盘、硬盘、随机访问存储器(RAM)、只读存储器(ROM)、可擦式可编程只读存储器(EPROM或闪存)、光纤、便携式紧凑磁盘只读存储器(CD-ROM)、光存储器件、磁存储器件、或者上述的任意合适的组合。在本申请中，计算机可读存储介质可以是任何包含或存储程序的有形介质，该程序可以被指令执行系统、装置或者器件使用或者与其结合使用。而在本申请中，计算机可读的信号介质可以包括在基带中或者作为载波一部分传播的数据信号，其中承载了计算机可读的程序代码。这种传播的数据信号可以采用多种形式，包括但不限于电磁信号、光信号或上述的任意合适的组合。计算机可读的信号介质还可以是计算机可读存储介质以外的任何计算机可读介质，该计算机可读介质可以发送、传播或者传输用于由指令执行系统、装置或者器件使用或者与其结合使用的程序。计算机可读介质上包含的程序代码可以用任何适当的介质传输，包括但不限于：无线、电线、光缆、RF等等，或者上述的任意合适的组合。

可以以一种或多种程序设计语言或其组合来编写用于执行本申请的操作的计算机程序代码，所述程序设计语言包括面向目标的程序设计语言—诸如Java、Smalltalk、C++，还包括常规的过程式程序设计语言—诸如”C”语言或类似的程序设计语言。程序代码可以完全地在用户计算机上执行、部分地在用户计算机上执行、作为一个独立的软件包执行、部分在用户计算机上部分在远程计算机上执行、或者完全在远程计算机或电子设备上执行。在涉及远程计算机的情形中，远程计算机可以通过任意种类的网络——包括局域网(LAN)或广域网(WAN)—连接到用户计算机，或者，可以连接到外部计算机(例如利用因特网服务提供商来通过因特网连接)。

附图中的流程图和框图，图示了按照本申请各种实施例的系统、方法和计算机程序产品的可能实现的体系架构、功能和操作。在这点上，流程图或框图中的每个方框可以代表一个模块、程序段、或代码的一部分，该模块、程序段、或代码的一部分包含一个或多个用于实现规定的逻辑功能的可执行指令。也应当注意，在有些作为替换的实现中，方框中所标注的功能也可以以不同于附图中所标注的顺序发生。例如，两个接连地表示的方框实际上可以基本并行地执行，它们有时也可以按相反的顺序执行，这依所涉及的功能而定。也要注意的是，框图和/或流程图中的每个方框、以及框图和/或流程图中的方框的组合，可以用执行规定的功能或操作的专用的基于硬件的系统来实现，或者可以用专用硬件与计算机指令的组合来实现。

描述于本申请实施例中所涉及到的单元可以通过软件的方式实现，也可以通过硬件的方式来实现。所描述的单元也可以设置在处理器中，例如，可以描述为：一种处理器包括导出单元、写入单元和生成单元。其中，这些单元的名称在种情况下并不构成对该单元本身的限定，例如，导出单元还可以被描述为“从键值数据库导出键元数据集合的单元”。

作为另一方面，本申请还提供了一种计算机可读介质，该计算机可读介质可以是上述实施例中描述的电子设备中所包含的；也可以是单独存在，而未装配入该电子设备中。上述计算机可读介质承载有一个或者多个程序，当上述一个或者多个程序被该电子设备执行时，使得该电子设备：从键值数据库导出键元数据集合，其中，每条键元数据包括键和值占用容量；将键元数据集合写入统计树；基于统计树，生成键值数据库的存储分布信息。

以上描述仅为本申请的较佳实施例以及对所运用技术原理的说明。本领域技术人员应当理解，本申请中所涉及的发明范围，并不限于上述技术特征的特定组合而成的技术方案，同时也应涵盖在不脱离上述发明构思的情况下，由上述技术特征或其等同特征进行任意组合而形成的其它技术方案。例如上述特征与本申请中公开的(但不限于)具有类似功能的技术特征进行互相替换而形成的技术方案。

Claims (28)

1.一种用于生成信息的方法，包括：

从键值数据库导出键元数据集合，其中，每条键元数据包括键和值占用容量；

将所述键元数据集合写入统计树；

基于所述统计树，生成所述键值数据库的存储分布信息；

其中，所述将所述键元数据集合写入统计树，包括：

对所述键元数据集合中的键进行分割，生成元素序列集合；

对于所述元素序列集合中的元素序列，将该元素序列的元素依次插入统计树，其中，元素在该元素序列中的位次与该元素在所述统计树中的层次对应；

基于所述键元数据集合中的值占用容量，更新所述统计树中的节点中的键数目和值占用容量。

2.根据权利要求1所述的方法，其中，所述对所述键元数据集合中的键进行分割，生成元素序列集合，包括：

对于所述键元数据集合中的键，确定该键中的目标分隔符；

基于所述目标分隔符将该键拆分成元素序列。

3.根据权利要求2所述的方法，其中，所述确定该键中的目标分隔符，包括：

统计预设分隔符集合中的预设分割符在该键中出现的频次；

基于所统计出的频次，从所述预设分隔符集合中确定目标分隔符。

4.根据权利要求1所述的方法，其中，所述将该元素序列的元素依次插入统计树，包括：

对于该元素序列的当前元素，确定当前元素在所述统计树中的位置，以及将当前元素插入所述位置处。

5.根据权利要求4所述的方法，其中，所述确定当前元素在所述统计树中的位置，以及将当前元素插入所述位置处，包括：

执行以下插入步骤：将当前元素在所述统计树中的当前元素的上一元素对应的节点的子节点集合中进行匹配；若匹配成功，确定当前元素已被插入所述统计树中；确定当前元素是否是该元素序列中的最后元素；若是最后元素，确定该元素序列已被插入所述统计树。

6.根据权利要求5所述的方法，其中，所述确定当前元素在所述统计树中的位置，以及将当前元素插入所述位置处，还包括：

响应于确定当前元素不是该元素序列中的最后元素，将该元素序列的下一元素作为当前元素，以及继续执行所述插入步骤。

7.根据权利要求5所述的方法，其中，所述确定当前元素在所述统计树中的位置，以及将当前元素插入所述位置处，还包括：

若当前元素在所述统计树中的当前元素的上一元素对应的节点的子节点集合中匹配失败，为当前元素的上一元素对应的节点创建当前元素对应的子节点。

8.根据权利要求5-7之一所述的方法，其中，所述确定当前元素在所述统计树中的位置，以及将当前元素插入所述位置处，还包括：

确定当前元素的上一元素对应的节点的子节点数目是否满足合并条件；

若满足所述合并条件，将当前元素的上一元素对应的节点的至少部分子节点合并成通配符子节点。

9.根据权利要求8所述的方法，其中，所述合并条件包括以下至少一项：子节点数目超过预设子节点数目阈值、所述统计树的全局节点数目超过预设全局节点数据阈值。

10.根据权利要求8所述的方法，其中，所述确定当前元素在所述统计树中的位置，以及将当前元素插入所述位置处，还包括：

将创建在所述统计树中的同一节点下的数字对应的叶子节点合并成通配符叶子节点。

11.根据权利要求1所述的方法，其中，所述基于所述统计树，生成所述键值数据库的存储分布信息，包括：

遍历所述统计树，生成所述键值数据库的存储分布信息。

12.根据权利要求11所述的方法，其中，所述遍历所述统计树，生成所述键值数据库的存储分布信息，包括：

对所述统计树进行前序遍历，输出匹配字符串集合以及每条匹配字符串的占用容量；

根据所输出的占用容量对所述匹配字符串集合进行排序，以及基于排序结果，生成所述键值数据库的存储分布信息。

13.根据权利要求12所述的方法，其中，所述基于排序结果，生成所述键值数据库的存储分布信息，包括：

基于排序结果，从所述匹配字符串集合中选取目标字符串；

对所述目标字符串进行通配符展开，得到展开字符串集合以及每个展开字符串的占用容量。

14.一种用于生成信息的装置，包括：

导出单元，被配置成从键值数据库导出键元数据集合，其中，每条键元数据包括键和值占用容量；

写入单元，被配置成将所述键元数据集合写入统计树；

生成单元，被配置成基于所述统计树，生成所述键值数据库的存储分布信息；

其中，所述写入单元，包括：

分割子单元，被配置成对所述键元数据集合中的键进行分割，生成元素序列集合；

插入子单元，被配置成对于所述元素序列集合中的元素序列，将该元素序列的元素依次插入统计树，其中，元素在该元素序列中的位次与该元素在所述统计树中的层次对应；

更新子单元，被配置成基于所述键元数据集合中的值占用容量，更新所述统计树中的节点中的键数目和值占用容量。

15.根据权利要求14所述的装置，其中，所述分割子单元包括：

确定模块，被配置成对于所述键元数据集合中的键，确定该键中的目标分隔符；

拆分模块，被配置成基于所述目标分隔符将该键拆分成元素序列。

16.根据权利要求15所述的装置，其中，所述确定模块包括：

统计子模块，被配置成统计预设分隔符集合中的预设分割符在该键中出现的频次；

第一确定子模块，被配置成基于所统计出的频次，从所述预设分隔符集合中确定目标分隔符。

17.根据权利要求14所述的装置，其中，所述插入子单元包括：

插入模块，被配置成对于该元素序列的当前元素，确定当前元素在所述统计树中的位置，以及将当前元素插入所述位置处。

18.根据权利要求17所述的装置，其中，所述插入模块包括：

插入子模块，被配置成执行以下插入步骤：对于该元素序列的当前元素，将当前元素在所述统计树中的当前元素的上一元素对应的节点的子节点集合中进行匹配；若匹配成功，确定当前元素已被插入所述统计树中；确定当前元素是否是该元素序列中的最后元素；若是最后元素，确定该元素序列已被插入所述统计树。

19.根据权利要求18所述的装置，其中，所述插入模块还包括：

循环子模块，被配置成响应于确定当前元素不是该元素序列中的最后元素，将该元素序列的下一元素作为当前元素，以及继续执行所述插入步骤。

20.根据权利要求18所述的装置，其中，所述插入模块还包括：

创建子模块，被配置成若当前元素在所述统计树中的当前元素的上一元素对应的节点的子节点集合中匹配失败，为当前元素的上一元素对应的节点创建当前元素对应的子节点。

21.根据权利要求18-20之一所述的装置，其中，所述插入模块还包括：

第二确定子模块，被配置成确定当前元素的上一元素对应的节点的子节点数目是否满足合并条件；

第一合并子模块，被配置成若满足所述合并条件，将当前元素的上一元素对应的节点的至少部分子节点合并成通配符子节点。

22.根据权利要求21所述的装置，其中，所述合并条件包括以下至少一项：子节点数目超过预设子节点数目阈值、所述统计树的全局节点数目超过预设全局节点数据阈值。

23.根据权利要求21所述的装置，其中，所述插入模块还包括：

第二合并子模块，被配置成将创建在所述统计树中的同一节点下的数字对应的叶子节点合并成通配符叶子节点。

24.根据权利要求14所述的装置，其中，所述生成单元包括：

遍历子单元，被配置成遍历所述统计树，生成所述键值数据库的存储分布信息。

25.根据权利要求24所述的装置，其中，所述遍历子单元包括：

遍历模块，被配置成对所述统计树进行前序遍历，输出匹配字符串集合以及每条匹配字符串的占用容量；

生成模块，被配置成根据所输出的占用容量对所述匹配字符串集合进行排序，以及基于排序结果，生成所述键值数据库的存储分布信息。

26.根据权利要求25所述的装置，其中，所述生成模块包括：

选取子模块，被配置成基于排序结果，从所述匹配字符串集合中选取目标字符串；

展开子模块，被配置成对所述目标字符串进行通配符展开，得到展开字符串集合以及每个展开字符串的占用容量。

27.一种电子设备，包括：

一个或多个处理器；

存储装置，其上存储有一个或多个程序，

当所述一个或多个程序被所述一个或多个处理器执行，使得所述一个或多个处理器实现如权利要求1-13中任一所述的方法。

28.一种计算机可读介质，其上存储有计算机程序，其中，所述计算机程序被处理器执行时实现如权利要求1-13中任一所述的方法。

Images