Skip to content

compression-algorithm-research-lab/go-varint

Repository files navigation

Varint的Go实现

一、这是什么

可变长int的类型,类似于数据库中的varchar类型,正常情况下int是要存储为多个字节的,比如int64,需要8个字节,比如使用int64来存储1这个数字,把对应的int64的这8个字节展开为每一个bit大概是这个样子:

image-20221201004517168

可以看到,只使用了一个bit,其实有效位只有一个bit,其它的都浪费了,varint就是想着尽可能的提高bit的利用率,每个数组不再使用固定的字节数表示,而是需要多长就使用多长,但是这样怎么知道究竟使用了几个字节呢,于是就把byte的最高的一个bit拿出来作为标记位,如果为1则表示后续后续的一个字节还是表示的这个数字,如果为0则表示这个数字已经结束,比如数字1024,则表示为:

image-20221201005133305

这样子只需要两个字节就可以了。

什么样子的数据适合使用varint

值的分布范围很大,并且绝大多数的值都分布在较小的那边,对于这种类型的树,直接使用偏移收缩不合适,直接使用较小的数据类型不合适大的放不下了,那么就是用varint类型,使得绝大多数数据都能消耗较小的空间,并且部分有需要的仍然使用较大的空间。

应用场景

  • 无符号证书持久化存储时节省空间
  • 内存计算节省空间,支持更大规模的计算量

二、安装

go get -u github.com/compression-algorithm-research-lab/go-varint

三、Example

TODO 2022-11-27 21:57:06

About

variable length int encoding

Topics

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages