我在读丹尼尔·莱米尔的文章《神秘的位图索引》（http://lemire.me/blog/archives/2008/08/20/the-mythical-bitmap-index/），他在文章中说
位图索引的压缩大小最多与表的大小成比例！不考虑不同值的数目！
我努力想知道他是怎么计算这个值的。
我知道对于长度为n的运行长度编码文本，最坏的情况是空间使用与n（2n？）所以O（N）。
我还知道，对于特定列的位图索引数，最坏的情况是列的基数为n，其中n是表中的记录数（这样每个记录在该特定列中都有一个唯一的值）。这意味着将有n个位图索引。
然而，在位图索引的最坏情况假设下，当运行长度编码时，每个位图索引将具有恒定的空间使用量，因为它只是一些0，1，然后是一些0，所以o（1）。
因此，在最高基数n下，所有位图索引的总空间使用量仅为n x o（1）=o（n）。
但是，对于所有可能的情况，如何从这个特定的计算到最坏的情况？我不清楚我描述的情况，其中cardinality=n，是所有位图索引加在一起使用的最坏情况空间。
如何计算表中列的所有运行长度编码位图索引加在一起的最坏空间使用情况？
最佳答案
根据位图索引的性质，整个矩阵中1s的数目不会超过n（如果所有值的列都已就位，则1s的数目将等于n）。具有n[i]1s的列的压缩大小将为o（n[i]）（最坏情况是1和0交替）。因此，压缩列的总大小不会超过o（sum（n[i]））
关于database - 特定列的所有位图索引的压缩大小最多与表的大小成比例吗？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/27506150/