我正在阅读 Daniel Lemire 的帖子 The Mythical Bitmap Index ( http://lemire.me/blog/archives/2008/08/20/the-mythical-bitmap-index/ )，他在帖子中说
位图索引的压缩大小最多与表的大小成正比！与不同值的数量无关！
我很难看出他是如何计算这个值的。
我知道长度为 N 的运行长度编码文本的最坏情况下的空间使用与 N （2N？）成正比，所以 O（N）。
我也知道特定列的位图索引数量的最坏情况是当列的基数为 N 时，其中 N 是表中的记录数（因此每条记录在该特定列中都有唯一值） . 这意味着将有 N 个位图索引。
然而，在位图索引的最坏情况假设下，每个位图索引在运行长度编码时将具有恒定的空间使用，因为它只是一些零，1，然后是一些零，所以 O(1)。
因此，在最高基数 N 下所有位图索引的总空间使用量仅为 N x O(1) = O(N)。
但是，对于所有可能的情况，您如何从这个特定的计算转到最坏的情况？我不清楚我描述的情况，其中基数 = N，是所有位图索引加在一起的最坏情况空间使用情况。
您将如何计算为表中的列添加在一起的所有运行长度编码位图索引的最坏情况空间使用情况？