以下是基于数据覆盖的一个初步讨论，实用中，位映射有广泛的应用领域，也有大量的算法实现需求。在经过初步的推演后，我发现这不是可以一蹴而就的。所以先给出一个简单的实现和应用算法讨论。

Bitmap 的数据库持久化实现

Bitmap 是一个常见的数据类型，常用于优化大量数值的存储和查询。这个概念对于数据库程序员应该不陌生，Oracle 等数据库通过这种技术优化查询。通常程序员会在一些算法或数据结构书籍上读到以 C 语言 char* 实现的 bitmap 。这里，我们考虑一个在数据库中存储的 bitmap 实现。

PG 上的数据结构实现

bitmap 的实现不难，PostgreSQL 中提供了 bitstring 类型，可以直接存储位串。但是单行 bitstring 能提供的数据长度终归有限。为了存储和性能的需要，我们将其设计为一个表。通过索引值将 bitmap 分片为 bitstring 集。

create table bitmap(idx bigint, segment bit(32));

分析

计算时我们将一个bitmap表视为一个完整的bitmap数据集，设 segment 的宽度为 w ，索引值为 i 。将第行的 idx 置为0，则第 i 个索引行上的第 b 位对应整个 bitmap 的第 b+i*w 位。逆推之，bitmap 第 x 位为 x div w 行，第 x%w 位。

因为数据分行存储，位计算操作也需要重新定义，要考虑跨界定位问题。Postgres 的 bit 本身支持左移右移操作。这点并不复杂。可以利用掩码技巧将计算参数分解为区片。具体算法几乎与 C 语言版本一致。当然针对一些有规则操作时，可以充分的利用 SQL 和 PLSQL 的语法特色进行简化。

实例

覆盖统计

详细内容介绍见下一段中的链接。这里简单介绍一下：每个数据样本是一个由大量一维区间值组成的文本。每一行是一个（起点，终点）区间。要计算二到N个样本件的覆盖率。而数据本身是未经整理的，可能有重复。

事实上，这个例子是我最初着手实现 bitmap 的起因。可以说 bitmap 可以直接优化此类问题，首先bitmap以至少8倍以上的比例节省存储空间（以 c 语言 char* 每字节存储位置状态来计）。而空间缩减后对查询性能也有直接提升。

这个应用的操作非常好实现，将收集来的数据区间段(s, e)转换为二进制数 2^s+2^(s+1)+...+2^e ，即从 s 到 e 之间都为1的二进制位串。然后与整个 bitmap 做或运算。示例代码如下：

create or replace function segment_over(s bigint, e bigint) returns void as $$
 declare
    sidx bigint;
    eidx bigint;
    d_data bit(32) := 4294967295::bit(32); -- pow(2, 32) -1
 begin
    if currval('bitmap_idx_seq') < (e/32)+1 then
        for i in currval('bitmap_idx_seq')..e/32+1 loop
             insert into bitmap(segment) select 0::bit(32);
         end loop;
    end if;
    sidx := s/32;
    eidx := e/32;
    if sidx = eidx then
         update bitmap set segment = (d_data << cast((32-e%32) as int))&(d_data >> cast((s%32) as int)) where idx = sidx;
     else
        update bitmap set segment = segment | (d_data >> cast((s%32) as int)) where idx = sidx;
         update bitmap set segment = d_data where sidx < idx and idx < eidx;
         update bitmap set segment = segment | (d_data << cast((e%32) AS INT)) where idx = eidx;
     end if;
end;
$$ language plpgsql;

优化分析

此示例中，segment_over 操作并未做任何深度优化，仅仅是将前述的思路直接实现出来而已。实际上根据业务，我们还可以进一步的提高操作效率。

例如，由于覆盖度操作是在数据区迭加或操作，单向的填充动作，可以将已覆盖区间直接压缩掉（这需要将 idx 字段扩展为起点和终点一对数据，或者通过触发器机制同步一个查询表）。

再例如，前例中我们的 segment 长度为32，idx 是一个 bigint 类型。这对于海量数据比较有效，不过如果总样本量较小，完全可以用 integer ，这样可以减少很多转型操作。

在 segment_over 中，我写了一个防出错的探测代码，如果索引值超出了初始化范围，会扩展 bitmap 表。但是实际上很多应用，其总数据量是有明确上界的。此时可以去掉这部分代码，使用一个一次性的初始化代码，例如下面这样：

create or replace function init(len bigint) returns void as $$
 declare
    i bigint;
begin
    truncate table bitmap restart identity;
     insert into bitmap(idx, segment) select 0, 0::bit(32);
     if len/32 < 1 then
        return;
    end if;
    for i in 1..len/32 loop
         insert into bitmap(segment) select 0::bit(32);
     end loop;
    if len%32 > 0 then
        insert into bitmap(segment) select 0::bit(32);
     end if;
end;
$$ language plpgsql;

将 segment 的宽度调整为略大于覆盖区间长度期望值的数值，可以减少对中间区间的覆盖操作，也有优化读写效率的可能。

数据库实现的动机

使用数据库存储 bitmap ，可以避免海量长度 bitmap 超出内存容量的情况，是一个比较经济的实现方式，特别是在机器不够强劲，或者没有条件部署云或网格集群的场景。只要熟练数据库层开发即可。

由于 Postgres 中已经实现了完备的并发访问、数据备份和查询等功能，可以避免自己开发文件型 bitmap 所需要考虑以上问题，带来的开发成本。轻松可以满足 OLAP 的需求，在线随时查询覆盖情况。

合理的使用数据库功能，可以有效的降低使用和开发成本，这种组件式的开发和集成方式，对于当下追求灵活、高性价比和可持续性的 IT 产业理念，是契合的。

……

劉鑫
March.Liu

挖坑不填是一种美德

2009年10月7日星期三