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

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

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

## 常见数据类型

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

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

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

基于上述知识，我们就可以理解数据库中数据类型的存储大小和取值范围了。
| 名称    |  存储大小   |  取值范围   |
| --- | --- | --- |
|  SMALLINT   |  2字节   |  -32768 ～ +32767   |
|  INTEGER(别名INT或INT4)   |  4字节   |  -2147483648～+2147483647   |
|   BIGINT（别名INT8）  |   8字节  |   -9223372036854775808～+9223372036854775807  |

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

## 采用数据表行存储

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

![](/img/f37f7055-c146-4125-a34f-32ba4b965fc7.png)
上表给出了10的各个数量级下数据表的大小趋势图，当测试数字量达到100万时，数据表占用存储空间已经达到92+M，测试中止。

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

## 采用数据库中数组类型存储

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

![](/img/aa770439-31bc-499c-b72d-9c46fd9ca14b.png)

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

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

## 理论存储量

`1个bigint 8字节`

`100万个bigint 7.6M`

`40亿个bigint 29.8G`

`40亿个int4 14.9G`

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

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

## Bitmap（位图）

![](/img/50c8cc67-04e9-421a-bda4-530222a63848.png)

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更好的位图压缩算法。

由于Roaring Bitmap算法较为复杂，请允许我准备更加充分后为大家带来更详细介绍。