基于多层服务器间数据传输合并的数据存储方法与流程

1.本发明属于数据存储领域，更具体的，涉及一种基于多层服务器间数据传输合并的数据存储方法。


背景技术：

2.在一些应用场景下，数据通常会通过多层服务器最终保存至总服务器，如图1所示。由于这种场景下数据的存储方式多数使用二项堆，这就使得最终保存在总服务器的数据无法快速获取某一个子区域即子服务器的全部数据。
3.事实上，一旦多层服务器采用二项堆的存储方式，就意味着该场景下的数据量极为庞大。通常数据量至少在1亿以上。这是因为二项堆的时间复杂度的常数项很大，如果数据量太小，例如只是百万级别的，其时间复杂度本质上是亏损的。因此，在二项堆为存储数据结构的使用场景下，如果要访问某一个底层的子服务器的全部数据，对数据逐一进行访问无疑是低效的。


技术实现要素：

4.为解决现有技术中存在的不足，本发明的目的在于解决上述缺陷，进而提出一种基于二项堆的数据存储方法与一种基于多层服务器间数据传输合并的数据存储方法。
5.本发明采用如下的技术方案。
6.本发明第一方面公开了一种基于二项堆的数据存储方法，包括：将待合并的二项堆改造成非满幂二项树，再参与合并；其中，非满幂二项树的改造方法包括：重复执行降根操作直至二项堆中只有一个根节点，并将所述二项堆视为非满幂二项树，其中，降根操作具体包括：选取二项堆中幂数最小的2颗二项树按照幂数从小到大分别是第一二项树与第二二项树，令第一二项树的幂数等于第二二项树的幂数后，对二者进行合并。
7.本发明第二方面公开了一种基于多层服务器间数据传输合并的数据存储方法，多层服务器至少包括：父服务器与多个子服务器，多个子服务器的数据需要合并传输至父服务器，子服务器的数据合并至父服务器时采用第一方面所述的基于二项堆的数据存储方法，且合并前的子服务器的非满幂二项树的根节点与根节点的嫡节点均携带子服务器的地址信息，合并后的父服务器的非满幂二项树的根节点与根节点的嫡节点均附加携带父服务器的地址信息；其中，根节点的嫡节点指的是根节点幂数最大的子节点。
8.本发明第三方面公开了一种终端，包括处理器及存储介质；其特征在于：所述存储介质用于存储指令；所述处理器用于根据所述指令进行操作以执行第一方面所述方法的步骤。
9.本发明第四方面公开了一种计算机可读存储介质，其上存储有计算机程序，其特征在于，该程序被处理器执行时实现第一方面所述方法的步骤。
10.本发明的有益效果在于，与现有技术相比，本发明具有以下优点：本发明通过改造二项堆，以牺牲一定的时间复杂度的条件下，极大的加快了对子
服务器全部节点搜寻的效率。
附图说明
11.图1是服务器架构的示意图。
12.图2a是父服务器b1的子节点的二项堆的示意图。
13.图2b是根据图2a中父服务器b1的子节点的二项堆，进行合并后得到父服务器b1的二项堆的示意图。
14.图2c是临时二项堆b1和临时二项堆b2的示意图。
15.图3a是将图2a中二项堆改造成非满幂二项树的示意图。
16.图3b是临时的非满幂二项树c1的示意图。
17.图3c是根据图3a的非满幂二项树重新生成父服务器b1的二项堆的示意图。
18.图3d是根据图3c的二项堆改造成非满幂二项树的示意图。
19.图4是将二项堆改造成非满幂二项树的流程图。
具体实施方式
20.为了使本技术的目的、技术方案及优点更加清楚明白，以下结合附图及实施例，对本技术进行进一步详细说明。应当理解，此处描述的具体实施例仅仅用以解释本技术，并不用于限定本技术。
21.用于存储数据的数据结构有：数组、链表、二项树、散列表、二项堆（binomial heap）等等，每一种数据结构均有自身的特性。通常，当数据平台的关系如图1所示时，即数据需要层层合并，最终汇总至总服务器。为了满足快速合并的需求，优选的数据结构几乎只能是二项堆。顾名思义，二项堆也叫做可合并堆。
22.在一些使用场景下，例如国家安全信息的搜寻系统中，往往会将每个公民的身份信息以区级单位进行搜集，采用二项堆进行存储以及合并至市级单位进行汇总，待市级单位的汇总了所有来自区级单位的信息后，再统一合并汇总至省级单位，待全部汇集后再统一汇集至国家机关。不难看出图1中的总服务器、服务器a、服务器a1与服务器a11即可分别对应国家机关的服务器，省级单位的服务器，市级单位的服务器与区级单位的服务器。
23.在图1中，如果把每一个服务器看成一个节点，连线体现了节点间的父子关系。例如在图1中，限于篇幅所限，父服务器a只连接了子服务器a1与服务器a2，但读者应当理解为，父服务器a还可以连接子服务器a3、子服务器a4等等。
24.二项堆的坏处在于，数据是分散而不可控的。在上述示例中，例如国家机关想要快速获取来自于某一区域（例如：某省或某市或某区）的所有数据时，一定要遍历所有的元素才行。
25.为了方便起见，在图1的基础上，我们以服务器b1、服务器b11、服务器b12、服务器b13与服务器b14作为观察窗口，给出一些示例性的数据，如图2a所示。
26.值得注意的是：由于二项树的合并规则是确定的，因而，当图2a中服务器b11、服务器b12、服务器b13与服务器b14的数据确定且合并顺序也确定时，则合并后存储在服务器b1的数据必然是唯一且确定的，如图2b所示。
27.图2a中的合并顺序为：先合并服务器b11与服务器b12得到临时二项堆b1，然后用
临时二项堆b1与服务器b13进行合并得到临时二项堆b2，再用临时二项堆b2与服务器b14进行合并，最后得到服务器b1的二项堆。
28.其中，临时二项堆b1与临时二项堆b2如图2c所示。
29.需要说明的是：在图2a、图2b或图2c中，一个圆圈代表一个数据，此处的一个数据可以泛指任何数据，通常是一个元组数据，该元组数据中可以包含一个人的身份证信息、年龄、工作单位等等，而圆圈中的数字则表示该数据的索引，索引用于执行二项堆的合并操作。不难看出图2a中所有的二项堆均为最小二项堆，即父节点的索引均小于子节点的索引。例如，父节点“21”小于子节点“23”，父节点“22”小于子节点“24”，注意的是：节点“24”与“26”尽管在图中的上下位置颠倒，但由于二者不存在父子关系（即图中的连线关系），因而不必遵循最小二项堆的规律。
30.上述内容均为公知常识，读者可翻阅《算法导论》第19章的内容自验之。
31.上文提到，这种方法的缺陷在于数据是分散而不可控的。例如：来自服务器b12的数据，其节点“41”在节点“25”在根部，而其他节点则在父节点“31”的下方。随着层层的合并，这些数据会分散到二项堆的各个角落。这非常不适合未来通过总服务器快速遍历来自某一个区域（例如服务器“b12”）的数据。
32.基于此，本发明首先提出一种基于二项堆的数据存储方法，可以让子区域的数据能够快速的遍历，该方法包括：将数据以二项堆存储，并将二项堆改造成非满幂二项树。
33.为了方便描述，上述非满幂二项树为自定义词，其改造方法如图4所示，具体包括步骤1~步骤2。
34.步骤1，选取幂数最小的2颗二项树按照幂数从小到大分别是第一二项树与第二二项树，令第一二项树的幂数等于第二二项树的幂数后，对二者进行合并。
35.步骤2，重复执行步骤1直至二项堆中只有一个根节点，将所述二项堆视为非满幂二项树。
36.步骤1与步骤2可以概括为：重复执行降根操作直至二项堆中只有一个根节点，并将所述二项堆视为非满幂二项树，其中，降根操作具体包括：选取二项堆中幂数最小的2颗二项树按照幂数从小到大分别是第一二项树与第二二项树，令第一二项树的幂数等于第二二项树的幂数后，对二者进行合并。
37.本段中对一些通用术语作进一步解释。以图2a为例，顾名思义，所谓根节点即为一个二项堆“最上方”的节点，也就是图中虚线连接的节点。例如，在服务器b14的二项堆中，“21”与“25”均为根节点，在服务器b12的二项堆中，“42”、“44”与“41”均为根节点。所谓幂数代表的是某颗二项树的全部节点的数量。例如在图2a中，根节点“21”的二项树上一共有8个节点，分别是“21”、“23”、“26”、“28”、“22”、“24”、“27”、“29”。因此根节点“21”的二项树的幂数就是3=ln8。所谓合并就是指将多个二项堆合并成一个二项堆。
38.图3a示出了将图2a中二项堆改造成非满幂二项树的示意图。以图2a中服务器b12的二项堆为例，先获取根节点为“42”的第一二项树与根节点为“44”的第二二项树，其幂数分别是0与1。首先令根节点为“42”的第一二项树的幂数为1，在根据公知常识的方法与根节点为“44”的第二二项树进行合并；由于42小于44，根节点为“44”的第二二项树挂在根节点为“42”的第一二项树的下方，形成了一颗以根节点为“42”的幂数为2的临时的非满幂二项树c1，如图3b所示。此时，该二项堆的根节点的数量由3变成了2，因此还需要再次执行步骤
1，将该临时的非满幂二项树c1与根节点为“41”的二项树进行合并，最终得到图3a中服务器b12的非满幂二项树。
39.可理解的，上述幂数为2的“临时”的非满幂二项树一共由3个节点构成，分别是节点“42”、“44”与“45”。由于其节点的数量为3，而幂数为2，也就是节点的数量不满幂，因此本发明将其自定义为非满幂二项树。与之类似的是，上述“令第一二项树的幂数等于第二二项树的幂数”本质上也是将第一二项树直接作为非满幂二项树进而参与合并。
40.注：从图2a、图2b或图2c中不难看出，公知的二项树（binomial tree）均是满幂的，例如上文中指出：根节点“21”的二项树的幂数就是3=ln8。在下文的有益效果说明中，为了方便起见，将非满幂二项树也简称为二项树。
41.不难理解，在二项堆中，每一个节点必然附带了其幂数信息，因为在二项堆的设计思想中，不可能为了获取一个待测的节点的幂数而亲自去遍历其所有子节点的个数，这显然是不科学的。所以本发明中所有涉及“合并”的操作，均属于公知常识。
42.图3c又示出了根据图3a中的非满幂二项树参与合并得到的服务器b1的二项堆。需要强调的是，非满幂二项树本质上就是幂数与实际节点数不一致的二项树。因而，其后续参与合并的操作与公知的二项树参与合并的操作是一致的。此外，公知的二项树或非满幂二项树的本质就是根节点数量为1的二项堆，因而二项树或非满幂二项树实际上是二项堆的下位概念。基于此，图3c合并的过程为公知常识，此处不再赘述。
43.在分析本发明实施例的有益效果前，本段先指出图3a中所有非满幂二项树的幂数。表1示出了图3a中所有的非满幂二项树的幂数，也包括了临时的非满幂二项树。
44.表1二项树的根节点幂数513422413342313253214
45.表2进一步示出了图3c中所有的非满幂二项树的幂数。
46.表2二项树的根节点幂数513422414253215342313
47.不难看出，非满幂二项树与公知的二项树的区别仅仅是幂数的设定变化，而其他
属性是不变的。例如在根节点为“21”的幂数为5的二项树中，其子节点的幂数从左至右依次是4、3、2、1、0，分别为根节点为“41”的二项树，根节点为“25”的二项树，根节点为“22”的二项树，根节点为“26”的二项树与根节点为“23”的二项树。
48.可以验证的是，上述非满幂二项树尽管造成了数据的空余，但对时间复杂度的影响是可以忽略的。可以计算验证的是，从步骤1~步骤2不难看出，幂数最大的二项树其幂数最多+1，相当于最坏情况下数据扩张了一倍。也就是说，原本的时间复杂度为lnn，改造后的时间复杂度最多为ln(2*n)。二者相减可知，一层合并对时间复杂度的影响仅仅是增加了ln2。此处的一层合并指的是从服务器b11、服务器b12、服务器b13与服务器b14至服务器b1的完整的合并过程。n为二项堆中节点的总数量。
49.基于此，本发明进而提出一种基于多层服务器间数据传输合并的数据存储方法，多层服务器至少包括：父服务器（例如：服务器b1）与关联的多个子服务器（例如：服务器b11~b14），多个子服务器的数据需要合并传输至父服务器，其特征在于，子服务器的数据合并至父服务器时采用权利要求1所述的基于二项堆的数据存储方法，且合并前的子服务器的非满幂二项树的根节点与根节点的嫡节点均携带子服务器的地址信息，合并后的父服务器的非满幂二项树的根节点与根节点的嫡节点均附加携带父服务器的地址信息。
50.根节点的嫡节点指的是根节点幂数最大的子节点。例如：在图3a中，根节点“51”的嫡节点指为“52”；根节点“52”的嫡节点指为“54”；根节点“22”的嫡节点指为“27”。
51.需要说明的是，“且合并前的子服务器的二项堆的根节点携带子服务器的地址信息，合并后的父服务器的二项堆的根节点附加携带父服务器的地址信息”所提到的2处“二项堆”也可以替换为非满幂树。
52.在一些实施例中，上述一种基于多层服务器间数据传输合并的数据存储方法以图3a与图3c所示。合并前，节点“51”与其嫡节点“52
”ꢀ
携带服务器b11的地址信息，节点“41”与其嫡节点“42
”ꢀ
携带服务器b12的地址信息，节点“31”与其嫡节点“34
”ꢀ
携带服务器b13的地址信息，节点“21”与其嫡节点“25
”ꢀ
携带服务器b14的地址信息；合并后，以图3d为准，节点“21
”ꢀ
与其嫡节点“31”均附加携带服务器b1的地址信息。
53.本发明的有益效果在于，当搜寻来自某个区域的全部节点时，效率大大提高。结合图3c不难看出，本发明遵循如下规律：（1）若父节点与某子节点的区域不一致，则父节点的以其他子节点为根的二项树的任意节点的区域与该某子节点的区域均不一致，且以该某子节点为根的二项树的任意节点与该父节点的区域均不一致。（2）若父节点与某子节点的区域一致，则以子节点为根的二项树的所有节点的区域与父节点一致。（3）若父节点与某子节点的区域一致，该父节点中幂数小于某子节点的其他子节点为根的二项树的所有节点的区域与父节点一致。
54.基于上述3个规律，以图3a与图3d为例，遍历任何一个区域，所涉及的节点最多为“21”、“31”、“34”、“41”、“51”、“52”、“42”、“25”这8个节点。而公知的二项堆，需要遍历全部节点才行。
55.假设需要查找服务器b13的全部数据，则只需要遍历“21”、“31”、“34”这3个节点即可以知晓服务器b13的全部数据在“31”为根节点的二项树上。具体的，首先查找“21”、“31”，由于“31”中携带了服务器b13的地址信息，而“21”并未携带服务器b13的地址信息，根据规律（1）可知无需遍历“41”、“25”等其他“21”的子节点。此时再遍历“34”发现其携带了服务器
b13的地址信息，根据规律（2）可知，服务器b13的全部数据在“31”为根节点的二项树上。
56.假设需要查的服务器b14的全部数据，则只需要遍历“21”、“31”、“41”、“25”这4个节点即可以知晓服务器b14的全部数据在“25”、“22”、“26”、“23”为根节点的二项树上。具体的，首先查找“21”、“31”，根据规律（1）可知，以“31”为根的二项树的任意节点与“21”的区域均不一致，因而无需遍历“34”。同样根据规律（1），遍历“41”后也无需遍历“51”。最后根据规律（3）可知，若父节点“21”与子节点“25”的区域一致，则父节点“21”中幂数小于某子节点的其他子节点“22”、“26”、“23”为根的二项树的所有节点的区域与父节点一致。
57.表面上看，上述似乎并没有节约多少时间，然而读者需要考虑到的是：首先，本发明的节点数量太少，随着节点的幂数越大，相对而言遍历的节点数量就大大减少。其次，现实中数据是经过多层服务器合并传至主服务器的，例如图1所示。在这种情形下，其所节约的时间就非常可观了。
58.回归图1，本发明不难拓展的是，当服务器b1的数据与服务器b2等等的数据合并至服务器b中时，也需要将先服务器b1的二项堆先改造成非满幂二项树方可再次合并，如图3d所示。由于图1中画出了3层合并，其时间复杂度仅增加了3*ln2。不难理解，从图3a至图3d，完成了一层合并的一整个循环。其有益效果也可以描述为：假设待搜寻的区域为服务器b14，则在总服务器的二项堆中，可以先以服务器b作为区域进行搜寻，进而在往下确定服务器b1的区域，进而再往下确定服务器b14的区域。即层层缩小范围进行搜寻。因此，多层服务器还包括：祖服务器，祖服务器关联多个父服务器且多个父服务器的数据需要合并传输至祖服务器；其特征在于，父服务器的数据合并至祖服务器时采用权利要求1所述的基于二项堆的数据存储方法，且合并后的祖服务器的非满幂二项树的根节点与根节点的嫡节点均携带祖服务器的地址信息。
59.本领域普通技术人员可以理解实现上述实施例方法中的全部或部分流程，是可以通过计算机程序来指令相关的硬件来完成，所述的计算机程序可存储于一非易失性计算机可读取存储介质中，该计算机程序在执行时，可包括如上述各方法的实施例的流程。其中，本技术所提供的各实施例中所使用的对存储器、数据库或其它介质的任何引用，均可包括非易失性和易失性存储器中的至少一种。非易失性存储器可包括只读存储器（read-only memory，rom）、磁带、软盘、闪存、光存储器、高密度嵌入式非易失性存储器、阻变存储器（reram）、磁变存储器（magnetoresistive random access memory，mram）、铁电存储器（ferroelectric random access memory，fram）、相变存储器（phase change memory，pcm）、石墨烯存储器等。易失性存储器可包括随机存取存储器（random access memory，ram）或外部高速缓冲存储器等。作为说明而非局限，ram可以是多种形式，比如静态随机存取存储器（static random access memory，sram）或动态随机存取存储器（dynamic random access memory，dram）等。本技术所提供的各实施例中所涉及的数据库可包括关系型数据库和非关系型数据库中至少一种。非关系型数据库可包括基于区块链的分布式数据库等，不限于此。本技术所提供的各实施例中所涉及的处理器可为通用处理器、中央处理器、图形处理器、数字信号处理器、可编程逻辑器、基于量子计算的数据处理逻辑器等，不限于此。
60.以上实施例的各技术特征可以进行任意的组合，为使描述简洁，未对上述实施例中的各个技术特征所有可能的组合都进行描述，然而，只要这些技术特征的组合不存在矛盾，都应当认为是本说明书记载的范围。
61.以上所述实施例仅表达了本技术的几种实施方式，其描述较为具体和详细，但并不能因此而理解为对本技术专利范围的限制。应当指出的是，对于本领域的普通技术人员来说，在不脱离本技术构思的前提下，还可以做出若干变形和改进，这些都属于本技术的保护范围。因此，本技术的保护范围应以所附权利要求为准。

技术特征：
1.一种基于二项堆的数据存储方法，包括：将数据以二项堆存储，并将二项堆改造成非满幂二项树，其特征在于，非满幂二项树的改造方法为：重复执行降根操作直至二项堆中只有一个根节点，并将所述二项堆视为非满幂二项树，其中，降根操作具体包括：选取二项堆中幂数最小的2颗二项树按照幂数从小到大分别是第一二项树与第二二项树，令第一二项树的幂数等于第二二项树的幂数后，对二者进行合并。2.一种基于多层服务器间数据传输合并的数据存储方法，其中，多层服务器至少包括：父服务器与关联的多个子服务器，多个子服务器的数据需要合并传输至父服务器，其特征在于，子服务器的数据合并至父服务器时采用权利要求1所述的基于二项堆的数据存储方法，且合并前的子服务器的非满幂二项树的根节点与根节点的嫡节点均携带子服务器的地址信息，合并后的父服务器的非满幂二项树的根节点与根节点的嫡节点均附加携带父服务器的地址信息；其中，根节点的嫡节点指的是根节点幂数最大的子节点。3.根据权利要求2所述的一种基于多层服务器间数据传输合并的数据存储方法，其中，多层服务器还包括：祖服务器，祖服务器关联多个父服务器且多个父服务器的数据需要合并传输至祖服务器；其特征在于，父服务器的数据合并至祖服务器时采用权利要求1所述的基于二项堆的数据存储方法，且合并后的祖服务器的非满幂二项树的根节点与根节点的嫡节点均携带祖服务器的地址信息。4.一种计算装置，包括存储器，用于存储一组指令；以及至少一个处理器，配置为执行该组指令以使得所述计算装置执行如权利要求1至3的任一项所述的方法。5.一种非暂态计算机可读存储介质，所述非暂态计算机可读存储介质存储计算机的一组指令，该组指令用于在被执行时使所述计算机执行权利要求1至3的任一项所述的方法。

技术总结
一种基于多层服务器间数据传输合并的数据存储方法，包括：子服务器的数据合并至父服务器时采用基于二项堆的数据存储方法，且合并前的子服务器的二项堆的根节点携带子服务器的地址信息，合并后的父服务器的二项堆的根节点附加携带父服务器的地址信息。基于二项堆的数据存储方法包括：将数据以二项堆存储，并将二项堆改造成非满幂二项树；其中，非满幂二项树的改造方法包括：重复执行降根操作直至二项堆中只有一个根节点，并将所述二项堆视为非满幂二项树，其中，降根操作具体包括：选取二项堆中幂数最小的2颗二项树按照幂数从小到大分别是第一二项树与第二二项树，令第一二项树的幂数等于第二二项树的幂数后，对二者进行合并。对二者进行合并。对二者进行合并。


技术研发人员：请求不公布姓名
受保护的技术使用者：南京市高淳区朔洲扬业科技服务有限公司
技术研发日：2023.03.29
技术公布日：2023/7/12