data-structures - Redis区间查询

Question

我有元组 (S, T) 形式的数据，其中 S 是字符串，T 是整数。 S 和 T 都不是唯一的，而它们的组合是唯一的。我需要获取所有元组 S1 == S2和 |T1 - T2| <= C .使用 Redis 可以高效地完成任务吗？

Answer 1

一种方法是将数据存储在列表中并使用 Lua 脚本进行检索。首先，对于 (Sn,Tn) 形式的元组, 像这样插入:

LPUSH myKey S1:T1
LPUSH myKey S2:T2
... and so on

然后，使用下面的Lua脚本:

local function split(div,str)
    if (div=='') then return false end
    local pos,arr = 0,{}
    for st,sp in function() return string.find(str,div,pos,true) end do
        table.insert(arr,string.sub(str,pos,st-1))
        pos = sp + 1
    end
    table.insert(arr,string.sub(str,pos))
    return arr
end

local key = KEYS[1]
local sVal = ARGV[1]
local tVal = tonumber(ARGV[2])
local cVal = tonumber(ARGV[3])
local length = redis.call("LLEN", key)

if (tonumber(length) == 0) then
    return nil
end

local data = redis.call("LRANGE", key, 0, tonumber(length))
local retval = {}

for index,val in pairs(data) do
    local parts = split(":", val)    
    if (parts[1] == sVal and math.abs(tonumber(parts[2]) - tVal) <= cVal) then
        table.insert(retval, val)
    end
end

return retval

另存为script.lua并执行它:

$ redis-cli "$(cat script.lua)" 1 myKey sValue tValue cValue

这将返回匹配 Sn:Tn 的所有元组(以 S1 == S2 and |T1 - T2| <= C 形式) .