如何存下40亿个不重复数字

如何存下40亿个不重复数字？作为一名数据工作者，你会如何设计表模型呢，带着这个问题我们一起来探索最佳方案。

常见数据类型

在深入理解这个问题之前，我们需要先回忆一下几个基础知识。

1 bit（比特） = 1个2进制数

1 byte(字节) = 8个2进制数 = 8 bit

基于上述知识，我们就可以理解数据库中数据类型的存储大小和取值范围了。

从上表我们可以看出，40亿这个数字已经超出了INTEGER类型的最大范围，所以只能选择BIGINT类型。

最简单粗暴的方式，创建一张数据表只有一个字段，生成40亿个不重复的数字并循环写入数据表，一个数字作为一条记录。

上表给出了10的各个数量级下数据表的大小趋势图，当测试数字量达到100万时，数据表占用存储空间已经达到92+M，测试中止。

该方案理论上具有可行性，但是没有实用价值，更别说实际应用中还要关注查询性能。

相比第一种方案：存下40亿个数字需要创建40亿条记录，采用数组存储则只需要创建一个数组字段类型，创建一条记录即可。

经测试，当把100万个数字作为一个数组存入一条记录的一个字段中时，数据表占用空间30+M。

相比第一个方案，该方案已经取得了非常大的优化，但是依然无法在实际场景中得到较好的应用。

1个bigint 8字节

100万个bigint 7.6M

40亿个bigint 29.8G

40亿个int4 14.9G

40亿个bigint类型数字竟然需要占用高达29.8G的存储空间，一般的办公电脑内存都没有这么大。

那么，如何才能存下40亿个不重复数字呢？

1个数字用一个bit位表示，那么40亿个数字就需要40亿个bit位表示

40亿个bit位占用的空间为4000000000bit/8 = 50000000byte = 48828.125Kb ≈ 47.68Mb

此时，存下小于40亿的40亿个数字只需要约47.68M，已经可以满足实际应用的要求。

我们继续思考，如果要表示4294967295这个数字，那么就需要4294967296个bit位

4294967296 = 2^32bit= 2^29byte(2^32bit / 8) = 2^19Kb = 2^9 Mb = 512Mb

如果只存储4294967295这个数字也需要512Mb的空间？

有没有更好方式呢？答案是肯定的，Roaring Bitmap更好的位图压缩算法。