前阵子做用户画像系统，遇到一个看起来特别简单的需求：存 1 亿个用户的布尔标签。
不就是 True/False 吗？我当时想，这有什么难的，一行代码的事。
结果前前后后优化了 5 版，每一版都觉得“这下总完美了吧”，结果上线就翻车，内存和速度来回横跳，最后才发现原来这么简单的问题，水比我想象的深多了。
今天把整个踩坑过程写出来，从新手最容易写的第一版代码，到最后怎么一步步被逼到写混合存储，相信你看完会对“空间换时间”这句话有新的理解。
第一版：新手写法，list 一把梭
最开始我想都没想，直接写了最符合 Python 直觉的代码：
# 1亿个用户，默认都是未激活 user_active = [False] * 100_000_000 标记某个用户激活了 user_active[1234567] = True写完本地跑了个小测试没问题，就推到测试环境了，结果容器刚启动没两秒直接 OOM 被 Kill。
我当时还纳闷，不就是 1 亿个布尔值吗？能占多少内存？
算完账我傻了：Python 的 list 存的根本不是布尔值本身，是指针。64 位系统下一个指针 8 字节，1 亿个指针就是 800MB。这还没算别的，光一个标签就占了快 1G 内存，我有十几个标签，这不得直接 10G 起步？
而且你以为这就完了？Python 的 bool 是对象，虽然 True 和 False 是单例，但 list 本身的开销还不止指针，算下来实际内存比 800MB 还多。
翻车点：把 Python 的动态类型特性想当然了，高级语言帮你屏蔽了底层细节，但不代表底层细节不存在。
第二版：用 bytearray，内存直接砍 10 倍
被 OOM 打醒之后，我第一个想到的就是：布尔值不就是 0 和 1 吗？我用字节数组存啊，一个字节存一个布尔值，总不浪费了吧？
user_active = bytearray(100_000_000) user_active[1234567] = 1改完一测内存：1 亿字节，也就是 95MB 左右，比第一版的 800MB 直接砍了快 90%，当时觉得自己可太聪明了。
这版稳稳当当跑了一周，我都以为这事结束了，直到产品过来说：我们要做全量用户，大概 10 亿个用户。
我算了算：10 亿字节是 950MB，好像也不是不能接受？但紧接着我又发现一个更致命的问题：如果我的标签是“是否付费用户”这种，1 亿个用户里可能只有 100 万个付费的，那 bytearray 还是要老老实实占 1 亿字节，其中 99% 都是 0，这不是纯纯浪费吗？
就好像你买了一栋 100 层的楼，就为了放一把椅子，虽然椅子确实放下了，但这楼钱花得冤不冤啊？
翻车点：固定长度存储在稀疏数据下，内存浪费是指数级的。
第三版：位图压缩，再砍 8 倍
这时候我想到了位图（Bitmap）。对啊！一个字节有 8 位，我用一位存一个布尔值，不就又能省 8 倍内存？
# 用int当位图，或者用bitarray之类的库 user_active = 0 # 一个int可以存很多位 标记第n位为1 user_active |= (1 << 1234567)算下来 1 亿位只需要 12.5MB，10 亿位也才 125MB，比 bytearray 又省了 8 倍，当时我觉得这已经是物理极限了——一位存一个信息，总不能再小了吧？
结果我还是太年轻了。
我拿“是否付费用户”这个标签测了下：1 亿用户里 100 万付费的，位图占 12.5MB。但是我换个思路，如果我只存那 100 万个付费用户的 ID 呢？一个 ID 用 4 字节存，100 万个 ID 才 4MB，比位图的 12.5MB 还小 3 倍！
如果更极端一点，1 亿用户里只有 1 万个付费用户，那位图还是 12.5MB，存索引只需要 40KB，差了 300 多倍。
哦，原来位图的“一位一个”在极端稀疏的数据下，还是浪费。那为什么不直接存索引呢？
翻车点：你以为的物理极限，只是“密集数据下的物理极限”，数据分布变了，最优解也会变。
第四版：稀疏存储，只存异常索引
说干就干，我把存储方式改成了：只存值为 True 的位置索引，存在一个排序好的数组里。
import array 初始是空数组，因为默认都是False true_indices = array.array('I') 标记用户1234567为True，就把索引插进去（保持有序） 这里省略二分查找插入的代码 true_indices.append(1234567)这版在稀疏数据下简直无敌：1 亿用户 100 万 True，内存 4MB；1 万 True，内存 40KB，比位图省太多了。
我当时拍桌子说，这总该是最终方案了吧？
结果上线第二天，监控报警，接口超时。
查了半天发现问题了：我另一个标签是“是否登录过”，这个标签 99% 的用户都是 True，只有不到 1% 的用户从来没登录过。按照稀疏存储的逻辑，我要存 9900 万个索引，算一下内存：9900 万 * 4 字节 = 380MB。
还记得位图占多少吗？12.5MB。
差了 30 倍。
而且更坑的是速度：位图查某个位置是不是 True，直接位运算 O(1)；稀疏存储要二分查找，O(log n)，数据量大了之后速度差了 10 倍都不止。
我当时人都傻了：合着密集的时候位图好，稀疏的时候索引好，那我到底用哪个？
总不能让业务方自己判断这个标签是稀疏还是密集吧？产品说用户行为是会变的，这个月付费用户少，下个月搞活动可能付费用户就多了，总不能到时候我再改代码切存储方式吧？
翻车点：没有一种存储结构能通吃所有数据分布，你以为的最优解，换个场景就是最差解。
第五版：为什么不能自动切换？
我盯着屏幕上两种存储方式的内存对比图，突然冒出来一个想法：
为什么我不能写一个类，内部自己判断当前数据是稀疏还是密集，自动选择用哪种存储方式？数据密的时候就用位图/数组，数据稀的时候就存索引，数据分布变了就自动在两种模式之间切换，对外 API 还和普通 list 一模一样，用户根本感知不到底层变了？
比如：
- 初始化的时候全是 False，那就是稀疏模式，只存 True 的索引
- 当 True 的数量超过某个阈值，自动切换成密集模式，用连续数组存
- 如果之后 True 又变少了，再自动切回稀疏模式
- 所有的索引、赋值、切片操作，都和普通 list 用法完全一样
这思路听起来是不是特别简单？但真要写起来坑特别多：
- 两种模式之间切换的阈值设多少合适？
- 切换的时候怎么保证原子性？
- 切片、位运算、统计 count 这些操作怎么在两种模式下都保持高性能？
- 频繁修改的时候会不会来回切换导致性能抖动？
我当时自己试着写了个原型，写了三天，边界情况写得头都大了，改了七八个版本还是有 bug。直到我搜 PyPI 的时候发现，哦，原来已经有人把这个思路完整实现了，就是 bool-hybrid-array。
说实话我最开始看到这个库的时候还挺不屑的，觉得不就是个布尔数组吗，能玩出花来？直到我看了它的实现思路，发现和我想的一模一样，但是人家把所有坑都踩完了。
它的逻辑特别朴素：
- 数据密集的时候，底层用 numpy 存连续数组，numpy 访问快
- 数据稀疏的时候，底层用 array.array 存异常索引，省内存
- 你不管怎么修改，它内部自动判断要不要切换存储模式
- 对外 API 和 Python list 几乎一模一样，索引、切片、赋值怎么用 list 就怎么用它
最有意思的是它的设计细节：为什么密集区用 numpy，稀疏区用 array？因为密集区长度是固定的，numpy 性能好；稀疏区索引要频繁增删，numpy 每次修改都创建新数组太慢，用 array.array 刚好。这个细节一看就是真的写过业务踩过坑的人想出来的，不是纸上谈兵。
给你们看个最简单的例子：
from bool_hybrid_array import BoolHybridArr, TruesArray, FalsesArray 创建1亿个False，这时候几乎不占内存，因为是稀疏模式 arr = FalsesArray(100_000_000) 只设置100万个位置为True for i in range(1_000_000): arr[i * 100] = True 这时候内存只有几MB，远小于bytearray的97MB print(arr[1000]) # True，访问速度和list几乎一样 print(arr[1234]) # False 如果你手贱设置了9000万个True，它会自动无缝切换成密集存储 整个过程不需要你手动干预，API完全一致它还有个 memory_usage 方法，可以直接告诉你当前用了多少内存，比原生 list 省了多少，要不要优化，特别直观。
我知道看到这里肯定有人会说：“这不就是个轮子吗？我自己也能写。”没错，原理确实不复杂，但是你自己写要处理多少边界情况？要测多少种数据分布？要踩多少坑？别人已经把这些坑都踩完了，测试也写好了，API 也设计得顺手，直接拿来用就完事了。
当然我也不是说这东西就是银弹，你要是就存几千个布尔值，那直接用 list 就行，犯不上引个第三方库。但是当你要存百万、千万甚至上亿级别的布尔值，而且数据分布你还不确定的时候，这种自动切换的混合存储确实能省你很多事。
最后说点实在的：选型建议
优化到最后我最大的感触是：根本没有什么“最好的”存储结构，只有最适合你当前场景的。
给大家一个我踩完坑总结出来的选型指南，不用记什么花里胡哨的概念：
- 数据量小于 100 万：直接用 list[bool]，可读性最重要，那点内存根本不值当优化
- 数据量 100 万-1000 万，分布稳定密集：用 bytearray，简单高效，标准库不用引依赖
- 数据量超过 1000 万，或者分布稀疏/不确定：可以试试 bool-hybrid-array 这种混合存储，一劳永逸不用你自己判断
- 需要做大量位运算（与或非、交集并集）：可以配合位图一起用，它也支持位运算
很多人做优化一上来就找最牛逼的技术、最复杂的数据结构，其实完全没必要。工程上的优化从来不是追求理论最优，而是在你当前的业务场景下，用最简单、最可维护的方式解决问题。
就像这个布尔存储的问题，你说它难吗？一点都不难，不就是存 0 和 1 吗？但真要做到极致，要在内存、速度、可维护性之间找平衡，就需要你一层一层去优化，一次一次去翻车，最后才能找到那个最合适的点。
哦对了，最后提一嘴，这个库的作者说他做这个东西的初衷是写线性筛的时候发现密集数组太占内存、稀疏数组跑起来太慢，所以才做了混合存储。你看，所有的优化本质上都是被业务逼出来的，没有凭空想出来的银弹。
如果这篇文章对你有帮助，欢迎点个赞收个藏，也可以去项目主页看看实现代码，其实核心逻辑不复杂，但是很多细节值得学习。
