面向日期区间可用性的高效存储与搜索算法方案咨询

针对你的问题，除了正则表达式，有几种广泛应用的算法/数据库方案，能满足可维护性、数据库端过滤的要求，以下是具体方案：

方案1：游程编码（Run-Length Encoding, RLE） #

核心思路是把连续的可用/不可用日期压缩成区间记录，比如把AAANNAAAANA转化为[(0, 3, 'A'), (4, 6, 'N'), (7, 11, 'A')]（格式：起始日偏移、结束日偏移、状态），每个桨板只存储这些连续区间的集合，不用存每天的状态。

具体做法（Postgres） #

• 用JSONB字段存储区间集合，建表语句：

CREATE TABLE paddle_availability (
    paddle_id INT PRIMARY KEY,
    ranges JSONB NOT NULL -- 示例值：[{"start":0,"end":3,"status":"A"},{"start":4,"end":6,"status":"N"}]
);

• 查询时，给定目标区间的起始偏移target_start和结束偏移target_end，只需检查是否存在一个或多个A状态的区间完全覆盖目标区间：

SELECT paddle_id
FROM paddle_availability,
     jsonb_to_recordset(ranges) AS r(start INT, end INT, status TEXT)
WHERE status = 'A'
  AND r.start <= target_start
  AND r.end >= target_end
GROUP BY paddle_id;

• 性能优化：可以给ranges字段加GIN索引，或者把区间拆成单独的表（每个区间一条记录），然后建复合索引(paddle_id, status, start, end)，查询速度会更快。

优缺点 #

• 可维护性强：区间语义清晰，更新时只需修改对应的区间（比如某段日期被预订，把原A区间拆成前后两段即可）
• 存储量极小：远低于单条日记录，也比字符串存储更紧凑
• 查询逻辑是标准SQL，容易理解和维护

方案2：Postgres原生Range类型 + 区间索引 #

核心思路是利用Postgres内置的daterange类型存储可用的连续日期区间，直接用原生区间操作符完成查询，完全贴合数据库原生能力。

具体做法 #

方式1：单区间单记录（推荐高读场景）

-- 建表：每个可用区间对应一条记录
CREATE TABLE paddle_available_ranges (
    paddle_id INT,
    available_range DATERANGE NOT NULL,
    PRIMARY KEY (paddle_id, available_range)
);

-- 创建GIST索引加速区间查询
CREATE INDEX idx_paddle_available_range ON paddle_available_ranges USING GIST (available_range);

• 查询逻辑：给定目标日期区间target_range（比如daterange('2023-01-20', '2023-01-25', '[]')），查找所有包含该区间的可用记录：

SELECT DISTINCT paddle_id
FROM paddle_available_ranges
WHERE available_range @> target_range;

方式2：单桨板多区间数组存储

CREATE TABLE paddle_availability (
    paddle_id INT PRIMARY KEY,
    available_ranges DATERANGE[] NOT NULL
);

CREATE INDEX idx_paddle_available_ranges ON paddle_availability USING GIN (available_ranges);

-- 查询
SELECT paddle_id
FROM paddle_availability
WHERE target_range <@ ANY(available_ranges);

优缺点 #

• 完全利用Postgres原生特性，无需自定义逻辑，可维护性极强
• GIST/GIN索引对区间查询优化极佳，适合高读负载场景
• 更新操作简单：新增/删除预订时，只需调整对应的daterange（合并相邻A区间，拆分被占用的区间）

方案3：位向量存储 + 位运算 #

核心思路是将每个日期的可用性映射为二进制位（可用=1，不可用=0），存储为Postgres的BIT或BYTEA类型，通过位运算快速判断目标区间是否全为可用状态。

具体做法 #

• 建表语句：

CREATE TABLE paddle_availability (
    paddle_id INT PRIMARY KEY,
    availability_bit BIT(730) NOT NULL -- 对应2年730天，每个位代表一天的可用性
);

• 查询逻辑：假设目标区间是从day_start（0开始偏移）到day_end（含），长度为days = day_end - day_start + 1，通过位运算判断区间内是否全为1：

SELECT paddle_id
FROM paddle_availability
WHERE bit_count(
    availability_bit << (730 - day_end - 1) >> (730 - day_end + day_start)
) = days;

优缺点 #

• 存储效率极高：730位仅占92字节，远小于字符串或RLE存储
• 位运算底层执行速度快，适合高并发读场景
• 可读性稍弱，但逻辑清晰，属于标准位操作，不属于底层hack

方案4：Redis Bitmap 高读负载优化 #

核心思路是利用Redis的Bitmap数据结构，每个桨板对应一个Bitmap，每个偏移量对应日期（从起始日开始的天数），位值表示可用性。通过Redis的位操作在内存中完成过滤，适合极高读负载的场景。

具体做法 #

• 初始化Bitmap：每个桨板的Bitmap key为paddle:availability:{paddle_id}，设置对应日期的位：

# 第10天可用（偏移量9，从0开始计数）
SETBIT paddle:availability:123 9 1
# 第11天不可用
SETBIT paddle:availability:123 10 0

• 查询逻辑：用Lua脚本在Redis端完成过滤，直接返回符合条件的桨板ID：

-- 输入参数：target_start（起始偏移）、target_end（结束偏移）、待检查的桨板ID列表（KEYS）
local target_start = tonumber(ARGV[1])
local target_end = tonumber(ARGV[2])
local result = {}

for _, pid in ipairs(KEYS) do
    local key = "paddle:availability:" .. pid
    -- 统计目标区间内可用天数（位为1的数量）
    local available_days = redis.call('BITCOUNT', key, target_start, target_end)
    if available_days == (target_end - target_start + 1) then
        table.insert(result, pid)
    end
end

return result

• 优化：结合地图搜索的特性，将桨板按地理位置分组，减少每次检查的桨板数量，进一步提升性能。

优缺点 #

• 内存占用极低：35万桨板×730位≈30MB，适合大规模存储
• 位操作是纯内存操作，速度极快，应对高读负载能力强
• 过滤逻辑在Redis端完成，减轻Postgres压力，适合架构拆分

内容的提问来源于stack exchange，提问作者orokusaki