CN115765754A - 一种数据编码方法及一种编码数据比较方法 - Google Patents

Abstract

本说明书实施例提供了一种数据编码方法及一种编码数据比较方法，确定待编码数据中有效负载的字节数量；所述有效负载为能够表征所述待编码数据大小的指定数据；生成索引字节；所述索引字节至少包括：长度数据，所述长度数据用于表征所述有效负载的字节数量；将生成的所述索引字节与所述待编码数据的有效负载进行组合，将组合后的数据作为所述待编码数据的编码结果。由于有效负载包括的字节和一个数据的大小相关，通过增加索引字节来记录数据有效负载的字节数量，在实现了压缩的同时，能保证压缩后的数据可以参与排序且可以与其他压缩后的数据比较大小。

Description

一种数据编码方法及一种编码数据比较方法

技术领域

本说明书一个或多个实施例涉及计算机应用技术领域，尤其涉及一种数据编码方法及一种编码数据比较方法。

背景技术

计算机设备一般默认将所有数据以固定长度的数据类型(比如int64、int32)进行存储。这样使得对于大小较小的数据而言，可能会造成存储资源或者数据传输带宽的浪费。

为了解决上述问题，相关技术中一般会通过改变数据的编码方法来实现对数据的压缩。但是相关技术中的编码方法使得多个数据之间无法进行大小比较或排序，对于需要进行排序或大小比较的场景中，相关技术中的编码方法将造成较大不便。

发明内容

有鉴于此，本说明书一个或多个实施例提供一种数据编码方法及一种编码数据比较方法。

根据本说明书一个或多个实施例的第一方面，提出了一种数据编码方法，包括：

确定待编码数据中有效负载的字节数量；所述有效负载为能够表征所述待编码数据大小的指定数据；

生成索引字节；所述索引字节至少包括：长度数据，所述长度数据用于表征所述有效负载的字节数量；

将生成的所述索引字节与所述待编码数据的有效负载进行组合，将组合后的数据作为所述待编码数据的编码结果。

根据本说明书一个或多个实施例的第二方面，提出了一种编码数据比较方法，包括：

获取待进行比较的两个编码数据；所述编码数据是通过上述的数据编码方法编码得到的；

基于每个编码数据的索引字节，确定每个编码数据的长度数据；

基于两个编码数据的长度数据，对两个编码数据进行大小比较。

根据本说明书实施例的第三方面，提供一种数据编码装置，包括：

字节数量确定模块，用于确定待编码数据中有效负载的字节数量；所述有效负载为能够表征所述待编码数据大小的指定数据；

索引字节生成模块，用于生成索引字节；所述索引字节至少包括：长度数据，所述长度数据用于表征所述有效负载的字节数量；

组合模块，用于将生成的所述索引字节与所述待编码数据的有效负载进行组合，将组合后的数据作为所述待编码数据的编码结果。

根据本说明书实施例的第四方面，提供一种编码数据比较装置，包括：

编码数据获取模块，用于获取待进行比较的两个编码数据；所述编码数据是通过上述的数据编码方法编码得到的；

长度数据确定模块，用于基于每个编码数据的索引字节，确定每个编码数据的长度数据；

比较模块，用于基于两个编码数据的长度数据，对两个编码数据进行大小比较。

根据本说明书实施例的第五方面，提供一种计算机可读存储介质，其上存储有计算机指令，该指令被处理器执行时实现上述的数据编码方法或数据解码方法。

根据本说明书实施例的第六方面，提供一种计算机设备，所述计算机设备包括：

处理器；

用于存储处理器可执行指令的存储器；

所述处理器通过运行所述可执行指令以实现上述的数据编码方法或数据解码方法。

根据本说明书实施例的第六方面，提供一种计算机程序，所述计算机程序处理器运行时实现上述的数据编码方法或数据解码方法。

根据本说明书实施例的第七方面，提供一种数据库系统，所述数据库系统中的数据通过上述的数据编码方法进行编码；所述数据库系统通过上述的编码数据比较方法进行数据排序，得到排序结果；

所述数据库系统在接收到用户的数据查询请求的情况下，基于所述排序结果响应用户的数据查询请求。

本说明书实施例提供了一种数据编码方法及一种编码数据比较方法，确定待编码数据中有效负载的字节数量；所述有效负载为能够表征所述待编码数据大小的指定数据；生成索引字节；所述索引字节至少包括：长度数据，所述长度数据用于表征所述有效负载的字节数量；将生成的所述索引字节与所述待编码数据的有效负载进行组合，将组合后的数据作为所述待编码数据的编码结果。

由于有效负载包括的字节和一个数据的大小相关，通过增加索引字节来记录数据有效负载的字节数量，在两个数据的索引字节大小不同的情况下，可以只比较两个数据索引字节的大小就能确定两个数据的大小；在两个数据的索引字节大小相同的情况下，说明两个数据有效负载部分一样长，那么可以进一步比较两个数据的有效负载部分从而比较两个数据的大小。这样，通过上述方法，在实现了压缩的同时，能保证压缩后的数据可以参与排序且可以与其他压缩后的数据比较大小。

应当理解的是，以上的一般描述和后文的细节描述仅是示例性和解释性的，并不能限制本说明书。

附图说明

此处的附图被并入说明书中并构成本说明书的一部分，示出了符合本说明书的实施例，并与说明书一起用于解释本说明书的原理。

图1是本说明书根据一示例性实施例示出的一种VarInt的编码范围的示意图。

图2是本说明书根据一示例性实施例示出的一种数据编码方法的流程图。

图3是本说明书根据一示例性实施例示出的二进制数据存储方式的示意图。

图4是本说明书根据一具体实施例示出的一种编码后数据的示意图。

图5是本说明书根据一示例性实施例示出的一种数据解码方法的流程图。

图6是本说明书根据一示例性实施例示出的一种编码数据比较方法的流程图。

图7是本说明书根据一示例性实施例示出的一种数据编码装置的框图。

图8是本说明书根据一示例性实施例示出的一种编码数据比较装置的框图。

图9是本说明书根据一示例性实施例示出的一种数据编码装置或数据解码装置所在计算机设备的一种硬件结构图。

具体实施方式

这里将详细地对示例性实施例进行说明，其示例表示在附图中。下面的描述涉及附图时，除非另有表示，不同附图中的相同数字表示相同或相似的要素。以下示例性实施例中所描述的实施方式并不代表与本说明书一个或多个实施例相一致的所有实施方式。相反，它们仅是与如所附权利要求书中所详述的、本说明书一个或多个实施例的一些方面相一致的装置和方法的例子。

需要说明的是：在其他实施例中并不一定按照本说明书示出和描述的顺序来执行相应方法的步骤。在一些其他实施例中，其方法所包括的步骤可以比本说明书所描述的更多或更少。此外，本说明书中所描述的单个步骤，在其他实施例中可能被分解为多个步骤进行描述；而本说明书中所描述的多个步骤，在其他实施例中也可能被合并为单个步骤进行描述。

计算机设备一般都是以固定长度的数据类型来对数据进行存储，比如对于整数而言，数据类型可以是int64(占用8字节，64比特)、int32(占用4字节，32比特)、int16(占用2字节，16比特)。由于计算机被设计为只能对两个相同长度的数据进行比较或者进行加减运算，这样存储可以保证计算机的处理效率。

而为了节约存储空间、节省传输带宽，相关技术中一般会对数据进行压缩。相关技术中针对整数一般是通过变长编码(Variable-length quantity，VLQ)的方法来完成整数的压缩，比如通过VarInt和LEB128等完成压缩。

VLQ处理思路是，由于不是所有的整数的有效负载都会占用某一数据类型的全部字节，比如对于数据类型int64而言，使用这一数据类型的整数一般占用8个字节，但是在使用该数据类型存储整数100的情况下，通过一个字节就能表征100这个整数的有效负载部分，其余七个字节实际上是不需要的。而且一般在数据库中，较小的整数比较大的整数的出现频率更为频繁，使用VLQ实现压缩可以节约整数占用的空间。

需要说明的是，之所以称VLQ是一种编码方法而不是一种压缩方法，是因为压缩方法包括很多种，通过改变编码方法来实现压缩只是压缩方法的一种。本说明书中介绍的VLQ和后文本说明书实施例的方法(也可以看作属于VLQ方法)都是通过改变了整数的编码方式，以实现压缩的效果。对于这种编码方法而言，是通过对大量有效负载不足8个字节的数据(以int64为例)进行编码，从而实现总体上的压缩，对于单个整数而言可能并不能实现压缩方法。比如本来就占满了8个字节64位的整数，通过VLQ可能会使得整体占用的字节变多。还需要说明的是，本说明书中所提及的编码方法，都是针对二进制的编码方法。

接下来将对相关技术中的VarInt的编码方法进行说明。VLQ这一类的方法与不压缩的方法相比，需要解决的一个重要问题是：相比于不压缩，由于不同的整数占用的字节数目不同，需要通过编码方法的设置，使得计算机可以知道每个整数占用的字节数目。

为了解决上述问题，VarInt将每个字节最开始的一个比特设置为连续位(connection bit)，连续位如果为1，则表征连续位所在字节不是该整数的最后一个字节，读取该整数仍需读取下个字节；连续位如果为0，则表征连续位所在字节是该整数的最后一个字节，读取该整数无需读取下个字节。在设置好连续位后，针对每个整数，提取其有效载荷对应的多个比特，以七个比特为一组，从最低位(也就是最后一位)开始进行组的划分，确定有效载荷的比特对应的组的数量(如果最后最高位的比特不足一组，则在最高位比特前补零)，然后根据划分的组，设置连续位，生成压缩后的整数。其中，VarInt的编码范围如图1所示。

举例而言，十进制的127，未压缩前的int16类型的二进制字节编码为0000000001111111，通过VarInt压缩后字节编码为01111111，最左边的0位连续位。十进制的128，未压缩前的int16类型的二进制字节编码为00000000 10000000，压缩后字节编码为1000000100000000，划线的两个比特(即两个字节各自最左边的比特)为连续位。

相关技术中VLQ的其他方法压缩方法也类似，在此不再赘述。

上述压缩方法的核心思想就是：去除数据中对于表征大小无用的字节，只保留有用的字节。上述举例中只是以整数为例进行举例，需要说明的是，采用上述思想的压缩方法也可以应用于其他的数据中可能会包括较多对于表征大小而言无用的字节的数据。

数据库中一般存储有大量数据，存在压缩数据的需求。而且为了更为方便的从数据库中检索出某一条数据，需要先对数据进行排序(需要排序的原因是，如果不排序，需要将用户输入的检索条件和每一条数据进行比较，如果进行排序，可以采用二分法检索，检索效率更高)。而相关技术中的VLQ编码后的数据无法进行直接比较或排序。

上述方法中，对于压缩后的不同数据而言，其不一定是一样长的，这导致通过相关技术中的编码方法无法直接比较或排序。如果需要比较，还需要对压缩后的数据进行解压。而解压需要消耗较多的资源，解压后再进行比较或排序，将会带来较多的资源消耗，降低比较或排序的效率。

为了在消耗较小的资源的情况下，实现对压缩后的数据进行排序或比较，考虑到对于有些种类的数据而言，两个数据的大小和字节数量有关，可以在每个压缩后(即编码后，后同)数据的头部(即计算机读取该数据时会首先读取的位置)存储数据的有效负载的长度数据(即该有效负载包括的字节数量)，这样在两个数据的有效负载的字节数量不一样长时，可以只比较头部中存储的有效负载的长度数据就能比较两个数据的大小；在两个数据有效负载的长度数据一致的情况下，可以进一步读取有效负载字节来比较两个数据的大小。

此外，读取数据的时候，还可以根据数据头部(后文称之为索引字节)中记录的长度数据来确定有效负载的长度，从而能确定数据与数据之间的分界线的位置。

需要说明的是，虽然知道两个数据有效负载的长度数据就能直接比较两个数据的大小，但是如果不在数据的头部记录上述信息，而是在需要进行排序的时候统计每个数据有效负载的长度数据，将会耗费较多的处理资源，降低排序或比较的效率。具体而言，如果使用本说明书提供的方法，只需要读取索引字节就能完成两个数据的大小比较或排序，而如果不使用本说明书提供的方法，将需要读取一个数据的所有字节，读取数据本身是需要消耗计算机的资源的，这无疑降低了计算机的处理效率。

本说明书实施例提供了一种数据编码方法及一种编码数据比较方法，确定待编码数据中有效负载的字节数量；所述有效负载为能够表征所述待编码数据大小的指定数据；生成索引字节；所述索引字节至少包括：长度数据，所述长度数据用于表征所述有效负载的字节数量；将生成的所述索引字节与所述待编码数据的有效负载进行组合，将组合后的数据作为所述待编码数据的编码结果。

由于有效负载包括的字节和一个数据的大小相关，通过增加索引字节来记录数据有效负载的字节数量，在两个数据的索引字节大小不同的情况下，可以只比较两个数字索引字节的大小就能确定两个数据的大小；在两个数据的索引字节大小相同的情况下，说明两个数据有效负载部分一样长，那么可以进一步比较两个数据的有效负载部分从而比较两个数据的大小。这样，通过上述方法，在实现了压缩的同时，能保证压缩后的数据可以参与排序且可以与其他压缩后的数据比较大小。

接下来将对本说明书示出的一种数据编码方法进行说明。

如图2所示，图2是本说明书根据一示例性实施例示出的一种数据编码方法的流程图，包括：

步骤201，确定待编码数据中有效负载的字节数量。

其中，所述有效负载为能够表征所述待编码数据大小的指定数据。

具体而言，为了可以使得编码(即压缩)后的数据可以被比较，首先需要确定每个待编码数据的有效负载的长度数据，即确定有效负载的字节数量。

首先，对于该方法的执行主体而言，可以是由任何可以进行存储和计算的计算机设备来执行。也可以由多个计算机组成的系统来完成，本说明书对于该方法的执行主体不作限定。

对于该方法的应用场景而言，如上所述，数据库中需要节省存储空间、节省传输带宽，且存在对存储的同一列的数据进行比较排序的需求，因此本说明书的方法可以应用在数据库中。当然，本说明书的方法也可以应用于其他既需要节省存储空间和传输带宽、又存在对压缩后的数据进行排序或比较需求的场景中，上述应用于数据库的场景并不表征对本说明书的限定。

其次，对于该方法中涉及的整数而言，需要说明的是，待编码数据需要满足以下条件，才能使得编码后的整数能够比较，且编码能达到压缩的效果：第一，以定长的数据类型存储的待编码数据中需要有可能有很多的前导零(或者说不表征实际大小的字节)，否则无法达到压缩效果；第二，以定长的数据类型存储的待编码数据的有效负载的长度需要和数据的大小存在相关性，可以通过比较两个数据的有效负载的长度来确定两个数据的大小。

满足上述条件的数据可以是整数。当然也可以是其他的满足上述条件的数据，本说明书对于数据的具体类型不做限定。

接下来首先对步骤201中的各个名词进行说明。

待编码数据即待进行编码的数据，也即待进行压缩的使用定长的数据类型进行编码数据。待编码数据是存储在计算机设备中的数据，其可以是任何数据类型的数据，比如说可以是int64类型的、也可以是其他类型的数据，本说明书对于待编码数据的数据类型不做限定。

需要说明的是，本说明书中的编码方法涉及的字节、比特都是以二进制的形式进行存储数据的字节和比特。

有效负载(payload bytes)可以理解为可以表征该数据的大小所需的指定字节。比如某个整数为0082，那么082和82都可以作为该数据的有效负载，也即有效负载是能表征该数据的大小，且占用空间不超过该数据占用空间的字节。

如果为了提高压缩率，那么有效负载可以是用于表征该数据的大小所需的最少字节。

在有效负载可以是用于表征该数据的大小所需的最少字节的情况下，对于正数和无符号数据而言，有效负载也即表征去除二进制的待编码数据的前导零字节后剩余的字节，所述前导零字节用于表征所有比特都为前导零的字节。需要说明的时候，有些情况下待编码数据中并不包括前导零字节，那么这种情况下，去除了前导零字节的有效负载也即待编码数据的所有字节。

对于负数而言，由于计算机是以补码的形式来存储负数，负数也就是去除了前缀(确定距离MSB最近的0，该0和MSB之间的1即为前缀)。

前导零(leading zero)即为：对于一个数据而言，从最高有效位(mostsignificant bit，MSB)开始往后直至遇到第一个非零数字，这个非零数字和最高有效位之间的0即为前导零。前导零也即对表征该数据大小无用的0，也即有效负载前面的0。需要说明的是，如上所述，本说明书的方法是针对二进制的数据进行说明的，步骤201中的前导零也即用于表征数据的二进制数据中的前导零。

前导零字节即该字节中包括的所有比特都存储的前导零的字节。一个字节(byte)包括8比特(bit，也称为8位)，每一比特用于存储一个二进制的0或1。从另一个方面进行说明，前导零字节也就是：先确定距离MSB最近的存储1的比特所在字节，该确定的字节之前的字节即为前导零字节。

得到待编码数据有效负载的方法也即为：去除待编码数据的前缀部分(即如上述的前导零字节或者是负数的前缀)，得到有效负载。

步骤203，生成索引字节。

其中，所述索引字节至少包括：长度数据，所述长度数据用于表征所述有效负载的字节数量。

具体而言，为了使得编码后的字节可以进行比较，增加了用于比较、确定数据之间的分界的索引字节。为了完成上述目的，索引字节中至少包括有效负载的长度数据，这样，读取了索引字节后就能进行大小比较和排序(在两个数据长度数据不一样长的情况下)，并且读取了索引字节之后就能确定当前数据的有效负载部分多长，从而确定有效负载部分在哪里结束，从而区分不同的编码后的数据。

如上所述，索引字节(header byte)也即用于比较大小的字节。由于索引字节记录的是有效负载的长度数据，而长度数据是基于有效负载的字节数量来确定的，一般最长的待编码数据也不会超过8个字节，一个字节来表征十进制的8是完全足够的，也即索引字节是单个字节。

对于索引字节和有效负载的顺序而言，如果能在读取数据之前预先得知每个数据索引字节的位置(比如可以将相关信息存储在数据存储的文件的文件头中)，那么编码数据中索引字节可以在有效负载前面，也可以在有效负载后面。

如果没有预先记录每个数据的索引字节的位置，最好将索引字节存储在有效负载前面，如前文所述，索引字节中存储有有效负载字节的数量，需要通过读取索引字节确定有效负载字节的长度，从而确定当前字节在哪结束。

接下来将对索引字节中包含的长度数据进行说明。

如上所述长度数据是根据有效负载的字节数量得到的，也即长度数据可以反映有效负载的字节数量的多少，通过比较两个已经通过本说明书提供的数据编码方法完成编码的数据的索引字节，便可以对两个数据的字节数量的多少进行比较，从而可以确定两个数据的大小。

接下来通过几个示例来对长度数据的具体形式进行说明。需要说明的是，下面的几个示例并不表征对本说明书中长度数据的限定，只要能表征有效负载的字节数量的多少的长度数据都能作为本说明书中的长度数据。

首先，长度数据可以直接记录有效负载的字节数量。这样在比较不同已经编码完成的数据的大小时，可以直接将长度数据拿出进行比较。

在比较时，对于有些数据类型而言(比如整数)，在数据是无符号数据(比如无符号整数unsigned integer)的情况下，所有数据都是正数，那么长度数据越大即表征该数据越大。在数据是有符号数据的情况下，如果两个数据都是正数，那么和无符号数据的处理方法相同；如果两个数据都是负数，那么则长度数据越大表征该数据越小；如果两个数据一个是负数一个是正数，那么正数一定大于负数。

上述方法中，对于有符号数据而言，符号位可以加在索引字节中，这样只读取索引字节即可以方便确定数据的大小；符号位也可以加在有效负载部分的首个比特，这样只读取索引字节加上有效负载部分的一个比特就能完成大小的比较。

在符号位加在索引字节的情况下，换言之，所述待编码数据为有符号数据；所述索引字节至少包括：符号位和长度数据；所述符号位用于表示所述待编码数据的正负。

需要说明的是，在上述情况下，长度数据不限于上述的直接记录有效负载的字节数量，还可以是其他的形式，比如可以是下述的形式。

其次，长度数据还可以是其他形式，比如可以是如下形式：

在待编码数据为正数的情况下(包括待编码数据是无符号数据、待编码数据是有符号数据的正数)，记录的长度数据和有效负载的字节数量正相关，比如长度数据可以是直接记录为有效负载的字节数量。比如一个数据有效负载包括4个字节，那么可以直接在索引字节中记录上4(二进制即为00000100)。

在待编码数据为负数的情况下，记录的长度数据和有效负载的字节数量负相关，比如长度数据总共编码4位的情况下，可以是记录所述长度数据为二进制的有效负载的字节数量的反码。举例来说说有效负载是4，二进制为0100(假设有效负载的字节数量只编码4位，这4位可以位于索引字节任意设定位置，其他位置可以存储0或存储其他内容，索引字节存储的其他内容详见前文和后文，在此暂不做说明)，对二进制的上述有效负载的字节数量进行01反转(即计算反码)后得到的数据为1011，可以将1011作为存储的长度数据。

这样，在比较两个编码后数据的大小的情况下，如果两个编码后数据同号(即同为正数或者同为负数)，可以直接比较长度数据，长度数据更大的数据则对应的数据更大。如果两个编码后数据不同号(即一个为正数，一个是负数)，则只要从有效负载或其他位置读取出符号位就能直接判断两者大小。

此外，在长度数据是上述内容基础上，为了更为方便完成大小比较，索引字节中除了可以包括长度数据，还可以包括符号位。此外，如果符号位放置在长度数据之前，且在数据为正数时符号位为1，在数据为负数时符号为0，则可以直接根据长度数据比较两个数据，两个数据(不论两个数据的正负)的长度数据的大小反映了两个数据的大小。

换言之，索引字节至少包括符号为和长度数据，且符号位顺序在所述长度数据之前。在所述待编码数据为正数的情况下，所述符号位为1，所述长度数据为所述有效负载的字节数量；在所述待编码数据为负数的情况下，所述符号位为0，所述长度数据为二进制的有效负载的字节数量的反码。

举例而言，一个正数8，有效负载的字节数量为1，索引字节的符号为设置为1，假设符号位设置在索引字节的第7位(即MSB，MSB为第7位，LSB为第0位，如图3所示，图3存储的数据为10100000，每个方框代表一个比特，所有方框组合起来代表一个字节)，且长度数据设置在有负载的第6-3位(需要说明的是，上述索引字节和长度数据的位置只是一种举例，也可以设置在其他位置，比如符号位设置在第7位，长度数据设置在第0-3位)，那么该整数8编码后的索引字节为10001000。一个正数600有效负载的字节数量为2，索引字节的符号位设置为1，按照上述的编码方式，索引字节编码为：10010000。两个数索引字节直接比较大小，很容易得到600的索引字节比8的索引字节大。

一个负数-8，有效负载的字节数量仍为1，按照上述编码方式，长度数据应该编码为1110，符号位设置为0，则索引字节为01110000，同样的，-600的索引字节应该编码为01101000，可见，-8的索引字节比-600的索引字节更大。且上述正数的索引字节都比负数的索引字节更大。

需要说明的是，上述举例中都有未设置含义的比特，这些比特在上述例子中是设置为0了，当然，也可以将这些比特都设置为1或者设置为任意固定值，比如可以将0-2位设置成101等等，当然上述例子不表征对本申请的限定，为设置含义的比特可以设置为任意固定值。

其他索引字节的形式将在后文进行说明，在此暂不赘述。

步骤205，将生成的所述索引字节与所述待编码数据的有效负载进行组合，将组合后的数据作为所述待编码数据的编码结果。

具体而言，将索引字节和有效负载组合，就得到了编码后的待编码数据。

沿用上例，整数8编码后的索引字节为10001000，有效负载部分为00001000，那么编码后的8为10001000 00001000。

接下来将对索引字节的其他形式进行说明。

首先，如上所述，int64只包括8个字节，4比特就可以表征8，那么索引字节中除了可以编码上长度数据之外，还可以编码上待编码数据的前几位(即距离最高有效位最近的几位，这些值越大，则表征这个数据越大)。这样，如果两个待编码数据同号且长度相同，无需读取有效负载部分的内容，可以通过比较索引字节中待编码数据的前几位就可以对两个数据的大小进行比较，可以进一步提高比较或排序的效率。如果两个数据的索引字节完全相同，再读取两个数据的有效负载部分来确定两者的大小关系。

换言之，所述索引字节至少包括长度数据和第一负载数据；所述第一负载数据为：所述有效负载的前N位，N为所述索引字节中去除长度数据后剩余的比特数。

需要说明的是，在上述方案的情况下，索引字节中还可以进一步存储符号位，这样可以通过索引字节完成更快的数据比较。

还需要说明的是，由于编码第一负载数据需要读取有效负载，并将有效负载的部分数据写入索引字节，这样可能会消耗一部分编码处理效率。如果为了提高编码效率，可以选择不在索引字节写入第一负载数据。

此外，第一负载数据在写入索引字节后，可以仍将第一负载数据保留在有效负载部分，也可以不在有效负载部分进行保留，本说明书对此不作限定。

其次，为了节省编码后数据的占用字节数量，在待编码数据的有效负载的字节数量小于1，且该字节中用于表征该数据的比特数少于N的情况下，可以将这部分数据放入索引字节，然后不保留有效负载部分，以节约编码后数据的字节数量。

换言之，所述确定待编码数据中有效负载的字节数量，包括：在二进制的所述待编码数据去除前导零后的数据的比特数小于N的情况下，确定所述待编码数据中有效负载的字节数量为0；N为所述索引字节中去除长度数据后剩余的比特数。所述生成索引字节，包括：设置所述索引字节包括：长度数据和第二负载数据；所述第二负载数据用于表征所述待编码数据去除前导零后的数据。所述将生成的所述索引字节与所述待编码数据的有效负载进行组合，将组合后的数据作为所述待编码数据的编码结果，包括：将生成的所述索引字节作为所述待编码数据的编码结果。

此外，对于长度数据占用的比特数而言，可以将长度数据占用的比特数设置为固定值，比如设置为4位(如上所述，4位能表征所有数据的有效负载的字节数量)。为了减少长度数据占用的比特数，以在头部数据中留出更多空间来存储其他内容，还可以基于下述的方法来确定长度数据占用的比特数。

首先，长度数据占用的比特数可以基于下述方法确定：

获取需要编码的所有待编码数据的有效负载的字节数量；将获取的所述所有待编码数据进行分类，同一类的待编码数据的有效负载的字节数量相同；确定待编码数据的种类数量，并基于确定的种类数量，确定所述长度数据占用的比特数。

举例而言，如果所有数据的有效负载的字节数量只有1、2和8三种，那么长度数据可以只占用两个字节，比如可以用01表示有效负载字节数量为1，用10表示有效负载字节数量为2，用11表征有效负载字节数量为8。这种方式比较适用于所有待编码数据的数据分布较为集中的场景。

其次，长度数据占用比特数的确定方法，还可以是：

在所有待编码数据的数据类型相同的情况下，获取需要编码的所有待编码数据的数据类型；确定所述数据类型占用的字节数量；基于确定的字节数量，确定所述长度数据占用的比特数。

换言之，根据待编码数据的数据类型，来确定待编码数据有效负载最多可以占用的字节数量，从而确定长度数据占用的比特数，比如int64类型的数据，有效负载最多占用8个字节，8的二进制为1000，需要通过4个比特来表征，那么长度数据占用的比特数为4。int32类型的数据，有效负载最多占用4个字节，4的二进制为100，需要通过3个比特来表征，那么长度数据占用的比特数为3。int16类型的数据，有效负载最多占用2个字节，2的二进制为10，需要通过2个比特来表征，那么长度数据占用的比特数为2。

接下来将通过一具体实施例来对本说明书示出的一种数据编码方法进行说明。该例子中将以整数为例对上述编码方法进行说明。

整数的编码格式为：包括索引字节和有效负载。

索引字节的格式为：

第7位或最高有效位：符号位，1表示正数，0表示负数。对于无符号数字，不需要符号位，随后的所有位都可以相应地向前移动。

第6位-第3位：长度数据。对于正数，长度数据存储有效负载的字节数量。对于负数，将二进制的有效负载的字节数量的反转后的内容作为长度数据。

第2位-第0位：有效负载1(payload bits)。在有效负载的比特数少于3的情况下，该位置存储有效负载(且这种情况下编码后的整数只包括索引字节)。在其他情况下，该位置存0。

然后得到索引字节后，再将索引字节和有效负载2部分进行拼接(有效负载的获取方法参见前文，在此不再赘述)，得到编码后的数据。

需要说明的是，该实施例中索引字节固定占用1个字节，有效负载可以占用0-8个字节，有效负载长度随着存储的整数的变化而变化。

编码后的整数包括的各部分如图4所示。

该实施例中，出于数字大小比较的目的，将索引字节设计为可被用于比较整数大小的排序：索引字节更大的整数代表该整数越大。如果索引字节相等，则必须比较有效负载字节。

因为符号位是最高有效位(MSB)，所以使用索引字节值比较，正数总是大于负数。由于较长的正数总是大于较短的正数，较长的负数总是小于较短的负数，因此长度位比较也符合上述规律(即可以直接通过比较索引字节的大小和整数的大小正相关)。

通过和相关技术中的方法比较可知，相关技术中的VarInt方法使用“连续位”来指示编码后整数的长度，由于连续位在每个字节的首位，这导致如果需要比较两个数据的大小，则必须读取编码后的整数的全部字节，否则无法直接确定包括的字节数量。

本申请中通过一个索引字节来表征编码后整数的有效负载的长度，只需要读取一个索引字节或一个字节加上一个符号位(如果待编码整数是有符号整数，且符号位没有设置在索引字节还需要读取符号位)就能比较两个整数的大小，解决了相关技术中通过VLQ方法压缩后的整数无法比较大小的问题。

此外，本说明书还提供一种数据解码方法，如图5所示，该方法包括以下步骤：

步骤501，从待解码数据的索引字节中确定所述待解码数据的有效负载的字节数量。

所述待解码数据是通过上述的数据编码方法编码得到的。

如上所述，索引字节中的长度数据可以以多种形式存储，上述方法中即根据编码方法，基于索引字节确定有效负载对应的字节数量。

步骤503，基于确定的所述有效负载的字节数量，读取有效负载。

确定有效负载的字节数量后，在索引字节后向后读取该数量的字节即可以得到有效负载。

步骤505，基于预设的数据类型，对所述有效负载进行处理得到所述待解码数据对应的解码结果。

由于有效负载是去掉前缀部分的字节，在得到有效负载后，需要基于数据类型(确定需要添加多少个前缀)和符号位(如果是正数，则前缀为0，如果是负数，则前缀是1)，在有效负载前补足够数量的0或1，并添加符号位，得到解码结果。

此外，本说明书还提供根据本说明书实施例的第七方面，提供一种数据库系统，所述数据库系统中的数据通过上述的数据编码方法进行编码；所述数据库系统通过上述的编码数据比较方法进行数据排序，得到排序结果。

所述数据库系统在接收到用户的数据查询请求的情况下，基于所述排序结果响应用户的数据查询请求。

通过上述的数据方法进行编码，可以使得编码后的数据在达到较好的压缩效果的同时可以被比较。同时，如上所述，由于数据库系统为了提高检索效率，可以预先基于上述的方法，对编码数据进行排序(一般是对同一列的数据进行排序)，从而在数据库系统接收到用户的数据检索请求的情况下，基于排序结果来通过检索效率更高方法来检索。

如图6所示，本说明书还提供一种编码数据比较方法，包括以下步骤：

步骤601，获取待进行比较的两个编码数据；所述编码数据是通过上述的数据编码方法编码得到的。

该方法可以应用于需要对编码数据进行比较或者排序的场景中，比如可以应用于在需要搜索数据库中的数据的情况下(如前文所述，这种情况下需要对数据库中的数据进行排序)。

编码数据也就是通过上述的方法编码得到的数据，即包括索引字节和有效负载部分的数据。

步骤603，基于每个编码数据的索引字节，确定每个编码数据的长度数据。

编码数据中包括索引字节，索引字节包括长度数据，那么可以从索引字节中读取对应的长度数据。

步骤605，基于两个编码数据的长度数据，对两个编码数据进行大小比较。

长度数据用于表征编码数据有效负载部分的字节数量，而有效负载的字节数量和编码数据的大小相关，对于正数而言，有效负载部分字节数量越多，则证明该数据越大；对于负数就恰好相反，因此可以基于长度数据来进行数据比较。

如果在索引字节中存储了长度数据和符号位，且所述符号位在长度数据之前；在所述待编码数据为正数的情况下，所述符号位为1，所述长度数据为所述有效负载的字节数量；在所述待编码数据为负数的情况下，所述符号位为0，所述长度数据为二进制的有效负载的字节数量的反码。

上述情况下，会使得编码数据越大，对应的索引字节也就越大，那么可以直接根据索引字节来确定两个数据的大小。

也即捕捉605包括：对两个编码数据的索引字节进行大小比较，基于索引字节的比较结果确定两个编码数据的比较结果；其中，索引字节的大小和编码数据的大小正相关。

如图7所示，图7是本说明书根据一示例性实施例示出的一种数据编码装置的框图，所述装置包括：

字节数量确定模块710，用于确定待编码数据中有效负载的字节数量；所述有效负载为能够表征所述待编码数据大小的指定数据；

索引字节生成模块720，用于生成索引字节；所述索引字节至少包括：长度数据，所述长度数据用于表征所述有效负载的字节数量；

组合模块730，用于将生成的所述索引字节与所述待编码数据的有效负载进行组合，将组合后的数据作为所述待编码数据的编码结果。

在一可选实施例中，所述待编码数据为有符号数据；所述索引字节至少包括：符号位和长度数据；所述符号位用于表示所述待编码数据的正负。

在一可选实施例中，所述符号位顺序在所述长度数据之前；在所述待编码数据为正数(即大于0)的情况下，所述符号位为1，所述长度数据为所述有效负载的字节数量；在所述待编码数据为负数(即小于0)的情况下，所述符号位为0，所述长度数据为二进制的有效负载的字节数量的反码。

在一可选实施例中，所述索引字节至少包括长度数据和第一负载数据；所述第一负载数据为：所述有效负载的前N位，N为所述索引字节中去除长度数据后剩余的比特数。

在一可选实施例中，字节数量确定模块710，用于在二进制的所述待编码数据去除前导零后的数据的比特数小于N的情况下，确定所述待编码数据中有效负载的字节数量为0；N为所述索引字节中去除长度数据后剩余的比特数；索引字节生成模块720，用于设置所述索引字节包括：长度数据和第二负载数据；所述第二负载数据用于表征所述待编码数据去除前导零后的数据；组合模块730，用于将生成的所述索引字节作为所述待编码数据的编码结果。

在一可选实施例中，所述装置还包括第一比特数确定模块750(图中未示出)，用于在所有待编码数据的数据类型相同的情况下，获取需要编码的所有待编码数据的数据类型；确定所述数据类型占用的字节数量；基于确定的字节数量，确定所述长度数据占用的比特数。

在一可选实施例中，所述装置还包括第二比特数确定模块760(图中未示出)，用于获取需要编码的所有待编码数据的有效负载的字节数量；将获取的所述所有待编码数据进行分类，同一类的待编码数据的有效负载的字节数量相同；确定待编码数据的种类数量，并基于确定的种类数量，确定所述长度数据占用的比特数。

如图8所示，图8是本说明书根据一示例性实施例示出的一种编码数据比较装置，包括：

编码数据获取模块810，用于获取待进行比较的两个编码数据；所述编码数据是通过上述的数据编码方法编码得到的；

长度数据确定模块820，用于基于每个编码数据的索引字节，确定每个编码数据的长度数据；

比较模块830，用于基于两个编码数据的长度数据，对两个编码数据进行大小比较。

在一可选实施例中，所述编码数据的索引字节中还包括符号位，所述符号位在长度数据之前；在所述待编码数据为正数的情况下，所述符号位为1，所述长度数据为所述有效负载的字节数量；在所述待编码数据为负数的情况下，所述符号位为0，所述长度数据为二进制的有效负载的字节数量的反码。

在上述情况下，比较模块830，用于对两个编码数据的索引字节进行大小比较，基于索引字节的比较结果确定两个编码数据的比较结果；其中，索引字节的大小和编码数据的大小正相关。

上述装置中各个模块的功能和作用的实现过程具体详见上述方法中对应步骤的实现过程，在此不再赘述。

对于装置实施例而言，由于其基本对应于方法实施例，所以相关之处参见方法实施例的部分说明即可。以上所描述的装置实施例仅仅是示意性的，其中所述作为分离部件说明的模块可以是或者也可以不是物理上分开的，作为模块显示的部件可以是或者也可以不是物理模块，即可以位于一个地方，或者也可以分布到多个网络模块上。可以根据实际的需要选择其中的部分或者全部模块来实现本说明书方案的目的。本领域普通技术人员在不付出创造性劳动的情况下，即可以理解并实施。

如图9所示，图9示出了实施例数据编码装置或数据解码装置所在计算机设备的一种硬件结构图，该设备可以包括：处理器1010、存储器1020、输入/输出接口1030、通信接口1040和总线1050。其中处理器1010、存储器1020、输入/输出接口1030和通信接口1040通过总线1050实现彼此之间在设备内部的通信连接。

处理器1010可以采用通用的CPU、微处理器、应用专用集成电路(ApplicationSpecific Integrated Circuit，ASIC)、或者一个或多个集成电路等方式实现，用于执行相关程序，以实现本说明书实施例所提供的技术方案。所述处理器通过运行可执行指令以实现上述的方法。

用于存储处理器可执行指令的存储器1020可以采用ROM(Read Only Memory，只读存储器)、RAM(Random Access Memory，随机存取存储器)、静态存储设备，动态存储设备等形式实现。存储器1020可以存储操作系统和其他应用程序，在通过软件或者固件来实现本说明书实施例所提供的技术方案时，相关的程序代码保存在存储器1020中，

输入/输出接口1030用于连接输入/输出模块，以实现信息输入及输出。输入输出/模块可以作为组件配置在设备中(图中未示出)，也可以外接于设备以提供相应功能。其中输入设备可以包括键盘、鼠标、触摸屏、麦克风、各类传感器等，输出设备可以包括显示器、扬声器、振动器、指示灯等。

通信接口1040用于连接通信模块(图中未示出)，以实现本设备与其他设备的通信交互。其中通信模块可以通过有线方式(例如USB、网线等)实现通信，也可以通过无线方式(例如移动网络、WIFI、蓝牙等)实现通信。

总线1050包括一通路，在设备的各个组件(例如处理器1010、存储器1020、输入/输出接口1030和通信接口1040)之间传输信息。

需要说明的是，尽管上述设备仅示出了处理器1010、存储器1020、输入/输出接口1030、通信接口1040以及总线1050，但是在具体实施过程中，该设备还可以包括实现正常运行所必需的其他组件。此外，本领域的技术人员可以理解的是，上述设备中也可以仅包含实现本说明书实施例方案所必需的组件，而不必包含图中所示的全部组件。

本说明书实施例还提供一种计算机可读存储介质，其上存储有计算机程序，该程序被处理器执行时实现上述的数据编码方法或数据解码方法。

计算机可读介质包括永久性和非永久性、可移动和非可移动媒体可以由任何方法或技术来实现信息存储。信息可以是计算机可读指令、数据结构、程序的模块或其他数据。计算机的存储介质的例子包括，但不限于相变内存(PRAM)、静态随机存取存储器(SRAM)、动态随机存取存储器(DRAM)、其他类型的随机存取存储器(RAM)、只读存储器(ROM)、电可擦除可编程只读存储器(EEPROM)、快闪记忆体或其他内存技术、只读光盘只读存储器(CD-ROM)、数字多功能光盘(DVD)或其他光学存储、磁盒式磁带，磁带磁磁盘存储或其他磁性存储设备或任何其他非传输介质，可用于存储可以被计算设备访问的信息。按照本文中的界定，计算机可读介质不包括暂存电脑可读媒体(transitory media)，如调制的数据信号和载波。

本说明书还提供一种计算机程序，所述计算机程序处理器运行时实现上述的数据编码方法或数据解码方法。

还需要说明的是，术语“包括”、“包含”或者其任何其他变体意在涵盖非排他性的包含，从而使得包括一系列要素的过程、方法、商品或者设备不仅包括那些要素，而且还包括没有明确列出的其他要素，或者是还包括为这种过程、方法、商品或者设备所固有的要素。在没有更多限制的情况下，由语句“包括一个……”限定的要素，并不排除在包括所述要素的过程、方法、商品或者设备中还存在另外的相同要素。

上述对本说明书特定实施例进行了描述。其它实施例在所附权利要求书的范围内。在一些情况下，在权利要求书中记载的动作或步骤可以按照不同于实施例中的顺序来执行并且仍然可以实现期望的结果。另外，在附图中描绘的过程不一定要求示出的特定顺序或者连续顺序才能实现期望的结果。在某些实施方式中，多任务处理和并行处理也是可以的或者可能是有利的。

Claims (13)

1.一种数据编码方法，包括：

确定待编码数据中有效负载的字节数量；所述有效负载为能够表征所述待编码数据大小的指定数据；

生成索引字节；所述索引字节至少包括：长度数据，所述长度数据用于表征所述有效负载的字节数量；

将生成的所述索引字节与所述待编码数据的有效负载进行组合，将组合后的数据作为所述待编码数据的编码结果。

2.根据权利要求1所述的方法，所述待编码数据为有符号数据；

所述索引字节至少包括：符号位和长度数据；所述符号位用于表示所述待编码数据的正负。

3.根据权利要求2所述的方法，所述符号位顺序在所述长度数据之前；

在所述待编码数据大于0情况下，所述符号位为1，所述长度数据为所述有效负载的字节数量；

在所述待编码数据为小于0的情况下，所述符号位为0，所述长度数据为二进制的有效负载的字节数量的反码。

4.根据权利要求1所述的方法，所述索引字节至少包括长度数据和第一负载数据；所述第一负载数据为：所述有效负载的前N位，N为所述索引字节中去除长度数据后剩余的比特数。

5.根据权利要求1所述的方法，

所述确定待编码数据中有效负载的字节数量，包括：

在二进制的所述待编码数据去除前导零后的数据的比特数小于N的情况下，确定所述待编码数据中有效负载的字节数量为0；N为所述索引字节中去除长度数据后剩余的比特数；

所述生成索引字节，包括：

设置所述索引字节包括：长度数据和第二负载数据；所述第二负载数据用于表征所述待编码数据去除前导零后的数据；

所述将生成的所述索引字节与所述待编码数据的有效负载进行组合，将组合后的数据作为所述待编码数据的编码结果，包括：

将生成的所述索引字节作为所述待编码数据的编码结果。

6.根据权利要求1所述的方法，所述长度数据占用比特数的确定方法，包括：

在所有待编码数据的数据类型相同的情况下，获取需要编码的所有待编码数据的数据类型；

确定所述数据类型占用的字节数量；

基于确定的字节数量，确定所述长度数据占用的比特数。

7.根据权利要求1所述的方法，所述长度数据占用比特数的确定方法，包括：

获取需要编码的所有待编码数据的有效负载的字节数量；

将获取的所述所有待编码数据进行分类，同一类的待编码数据的有效负载的字节数量相同；

确定待编码数据的种类数量，并基于确定的种类数量，确定所述长度数据占用的比特数。

8.一种编码数据比较方法，包括：

获取待进行比较的两个编码数据；所述编码数据是通过权利要求1-7任一项所述的方法编码得到的；

基于每个编码数据的索引字节，确定每个编码数据的长度数据；

基于两个编码数据的长度数据，对两个编码数据进行大小比较。

9.根据权利要求8所述的方法，所述编码数据的索引字节中还包括符号位，所述符号位在长度数据之前；在所述待编码数据大于0的情况下，所述符号位为1，所述长度数据为所述有效负载的字节数量；在所述待编码数据为小于0的情况下，所述符号位为0，所述长度数据为二进制的有效负载的字节数量的反码；

所述基于两个编码数据的长度数据，对两个编码数据进行大小比较，包括：

对两个编码数据的索引字节进行大小比较，基于索引字节的比较结果确定两个编码数据的比较结果；其中，索引字节的大小和编码数据的大小正相关。

10.一种数据库系统，所述数据库系统中的数据通过权利要求1-7任一项所述的方法进行编码；所述数据库系统通过权利要求8或9所述的方法进行数据排序，得到排序结果；

所述数据库系统在接收到用户的数据查询请求的情况下，基于所述排序结果响应用户的数据查询请求。

11.一种计算机设备，包括：

处理器；

用于存储处理器可执行指令的存储器；

其中，所述处理器通过运行所述可执行指令以实现如权利要求1-9中任一项所述的方法。

12.一种计算机可读存储介质，所述计算机可读存储介质上存储有计算机指令，所述计算机指令被处理器执行时实现如权利要求1-9中任一项所述的方法。

13.一种计算机程序，所述计算机程序处理器运行时实现如权利要求1-9中任一项所述的方法。

Images