数据编码方法、图数据存储方法、图数据查询方法及装置.pdf

(19)中华人民共和国国家知识产权局(12)发明专利申请(10)申请公布号CN113641841A(43)申请公布日2021.11.12(21)申请号202111204226.X(22)申请日2021.10.15(71)申请人支付宝（杭州）信息技术有限公司地址310000浙江省杭州市西湖区西溪路556号8层B段801-11(72)发明人张松清江进付治钧袁琳朱炳鹏王伟生(74)专利代理机构北京永新同创知识产权代理有限公司11376代理人林锦辉刘景峰(51)Int.Cl.G06F16/51(2019.01)G06F16/53(2019.01)权利要求书7页说明书21页附图13页(54)发明名称数据编码方法、图数据存储方法、图数据查询方法及装置(57)摘要本说明书的实施例提供数据编码方法、图数据存储方法、图数据查询方法及装置。在该数据编码方法中，基于数据记录的键值对中的键对待编码数据的各个数据记录进行数据分片，所得到的各个数据分片的分片标识基于该数据分片中的数据记录的键的一致性哈希值确定。针对各个数据分片，通过使用完美哈希算法对该数据分片中的各个数据记录的键值对中的键进行完美哈希计算，确定各个数据记录在该数据分片中的片内索引。基于待编码数据的各个数据记录在对应数据分片中的片内索引，将各个数据记录的键值对记录到对应数据分片；并且针对记录有数据记录的每个数据分片，分别生成数据分片文件以及对应的完美哈希因子文件。CN113641841ACN113641841A权利要求书1/7页1.一种基于完美哈希的数据编码方法，包括：基于数据记录的键值对中的键对待编码数据的各个数据记录进行数据分片，所得到的各个数据分片的分片标识基于该数据分片中的数据记录的键的一致性哈希值确定；针对各个数据分片，通过使用完美哈希算法对该数据分片中的各个数据记录的键值对中的键进行完美哈希计算，确定各个数据记录在该数据分片中的片内索引；基于所述待编码数据的各个数据记录在对应数据分片中的片内索引，将各个数据记录的键值对记录到对应数据分片；以及针对记录有数据记录的每个数据分片，分别生成数据分片文件以及对应的完美哈希因子文件。2.如权利要求1所述的数据编码方法，其中，基于数据记录的键值对中的键对待编码数据的各个数据记录进行数据分片包括：对待编码数据中的各个数据记录的键值对中的键进行一致性哈希计算；对各个数据记录的一致性哈希值进行以数据分片数量为模数的取模处理；以及将取模结果相同的数据记录划分到同一数据分片，各个数据分片的分片标识基于对应的取模结果确定。3.如权利要求1所述的数据编码方法，其中，所述待编码数据包括图数据的点表数据，所述点表数据的每个节点数据中的图节点的节点标识和节点属性在数据编码时分别充当该节点数据的键和值，基于所述待编码数据的各个数据记录在对应数据分片中的分片索引，将各个数据记录的键值对记录到对应数据分片包括：基于各个节点数据在对应数据分片中的节点数据片内索引，将各个节点数据的节点标识和节点属性记录到对应数据分片。4.如权利要求1所述的数据编码方法，其中，所述待编码数据包括图数据的边表数据，所述边表数据的每个边数据包括起始图节点的节点标识、终止图节点的节点标识以及边属性，在对所述边表数据的各个边数据进行数据分片之前，所述数据编码方法还包括：通过下述过程对所述边表数据中的边数据进行数据更新：针对每条边，分别基于起始图节点的节点标识和终止图节点的节点标识进行节点分片，确定起始图节点和终止图节点所在节点分片的节点分片标识，各个节点分片的节点分片标识基于对应节点标识的一致性哈希值确定，以及分别使用点表数据编码时的完美哈希因子文件中的对应完美哈希因子计算起始图节点的节点标识的完美哈希值以及终止图节点的节点标识的完美哈希值，确定起始图节点和终止图节点在所在节点分片中的片内索引；分别将各个起始图节点的节点分片标识和片内索引组合以及将各个终止图节点的节点分片标识和片内索引组合，得到各个起始图节点的全局节点标识和各个终止图节点的全局节点标识；以及针对每条边，将起始图节点的全局节点标识和终止图节点的全局节点标识组合为边标识，其中，边标识在数据编码时充当边数据的键，以及边属性在数据编码时充当边数据的值。5.如权利要求4所述的数据编码方法，其中，基于所述待编码数据的各个数据记录在对2CN113641841A权利要求书2/7页应数据分片中的片内索引，将各个数据记录的键值对记录到对应数据分片包括：基于各个更新后的边数据在对应边数据分片中的边数据片内索引，将各个更新后的边数据的边属性存储到对应边数据分片。6.如权利要求1所述的数据编码方法，其中，所述待编码数据包括图数据的邻居表数据，所述邻居表数据的每个邻居数据包括起始图节点的节点标识以及所有终止图节点的节点标识，所述数据编码方法还包括：通过下述