Fastbit中的bitmap索引算法
这篇讲的是开源数据处理库 Fastbit 的核心索引技术——bitmap 索引算法的实现。文章从 Fastbit 按列存储的特点出发，详细剖析了其索引类清晰的派生结构，并重点介绍了几种基础 bitmap 索引算法的设计思路。 作者从最直观的 relic（等值编码）讲起，它为每个不同值建立一个独立的 bitvector。随后引出其变形 bin（分桶编码），将值域划分为不相交区间。更巧妙的是 range 和 mesa 两种算法：range 算法通过累积 bin 的结果来标记“小于某值”，而 mesa 算法则允许区间重叠。这些基础算法构成了 Fastbit 索引的基石。 此外，文章还触及了扩展算法 direkte，它与 relic 几乎一致，但为小于最大值的所有值都建立了索引。这些从简单直接到巧妙演进的实现，展示了为满足不同查询需求，在存储与效率间进行的精细权衡。