首页   注册   登录
V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX  ›  程序员

有没有一种专门的 Nosql,只用来查询是否存在某个特定值的?

  •  
  •   kisshere · 27 天前 · 1366 次点击

    这种 Nosql 应该不叫“kv 库”了吧,应该叫做“v 库”了,因为不需要键值,只需要在千万级数据中查询某个特定值的存在,返回 bool 值即可,查询时间毫秒级

    求推荐

    23 回复  |  直到 2019-10-10 16:02:16 +08:00
        1
    ClarkAbe   27 天前 via Android
    这叫 k 库吧.....直接用一个 map 替代就行有这个键就 true 没有就.....
        2
    OakScript   27 天前
    布隆过滤器?
        3
    sadfQED2   27 天前 via Android
    Redis 装布隆过滤器扩展应该就是你想要的了
        4
    nicon   27 天前
    布隆过滤器
        5
    lihongjie0209   26 天前
    首先排除布隆过滤器, 布隆过滤器是一个概率型数据结构, 无法简单的使用 bool 作为返回值, 除非你只用它来确认数据不存在。
        6
    maemual   26 天前
    redis 存 kv,value 随意。。。。千万数量级不算多大,毫秒级不是问题
        7
    YUyu101   26 天前
    kv 本来就无所谓 v,v 又不直接存在结构里,只是个指针嘛。
        8
    luob   26 天前 via iPhone
    这应该叫 k 库不是 v 库……
    直接存 k,v 全都为空就行了。
        9
    0x000007b   26 天前
    @lihongjie0209 为啥,虽然 bloom 有误判率但功能上不是正好能完美实现嘛
        10
    lihongjie0209   26 天前
    @0x000007b #9 `只需要在千万级数据中查询某个特定值的存在` > 无法做到, 只能查询某个特定的值不存在
        11
    ztcaoll222   26 天前
    @lihongjie0209 #10 能接受少量的误判率不就能证明存在吗
        12
    lihongjie0209   26 天前
    @ztcaoll222 #11 只能证明“可能”存在
        13
    ztcaoll222   26 天前
    @lihongjie0209 #12 对啊, 我不是说了接受误判率吗
        14
    lihongjie0209   26 天前
    @ztcaoll222 #13 存在是一个绝对的概念, 就是 100%, 没有一种 “存在” 的定义是“在一定概率下 100%”。
        15
    ztcaoll222   26 天前
    @lihongjie0209 #14 ? 你在说什么, "可能存在"这个词是错的啰 ?
    这么纠结于存在这个定义, 不如问问楼主能否接受使用布隆过滤器这个方案
        16
    dusu   26 天前 via iPhone
    能接受误差 Redis 的 HyperLogLog 可以解惑。存 2^64 个元素仅需 12K。

    不能接受误差 Redis 的 bitmap 也是不错的选择。

    前提是你输入的数据是整型
        17
    fluorinedog   26 天前 via Android
    @dusu 什么鬼,hll 是用来计算 distinct value 的估计数量的,跟这需求不沾边。

    bloom filter 平均一个元素占用几个 bit,不过确实是概率算法。
    如果数据有范围,比如 N 个数据,出现在[0, 10N]区间里,其实 bitmap 就不错。
    要保证精确的话,还是得 bloom filter 初筛,然后 kv 表查询。
        18
    dusu   26 天前 via iPhone
    @fluorinedog hll 要统计的时候直接把整型往里丢 数据涨了就代表集合里没有 没涨不就代表集合里没有么?

    当然这不是原子操作,高并发下肯定有问题,主要是楼主也没有说要多大并发,只是要求毫秒级。
        19
    aguesuka   26 天前 via Android
    千万级的数据用 rbtree 也是毫秒级的吧。只要内存够大
        20
    realpg   25 天前
    直接 kv 库去 get 那个 key 不就好了
        21
    fluorinedog   7 天前 via Android
    @dusu 一口老血喷到屏幕上...
    第一,hll 可以基于高并发的原子操作,你刚好说反了
    第二,hll 是概率算法,在后期 hll 自己的数据结构起主导后,对于每个桶,要么不更新,要么一次更新增加 N 个元素。打个比方,hll 就像一个精确到 100 的倍数的 distinct value 统计函数,你用它来统计某个数是否在集合中的话,错误率是 99%好吧。
        22
    dusu   6 天前
    @fluorinedog 感谢老哥指导,小弟受教~之前确实理解错了
    不过我觉得可以通过控制每个 hll 桶内元素的数量去解决误差?
    像类似于可能在 1w 或 10w 的数据集的时候误差比较小,
    那么通可以过 id % 桶数量 找到对应 key 来减少误差,
    个人想法哈,仅供讨论...
        23
    fluorinedog   5 天前 via iPad
    @dusu 那 hll 就没有任何优势了。hll 本来就是用相对少量的定长内存统计大量的数据,但是当数据量很少时还不如 std::set 呢...
    同时从信息论的角度来看,hll 平均每个元素不到 0.1 个 bit 时,必然无法完成集合的 exists 功能。作为对比,bloom filter 平均一个元素有几个 bit,已经基本压缩到极致了。
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   4258 人在线   最高记录 5043   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.3 · 26ms · UTC 08:55 · PVG 16:55 · LAX 01:55 · JFK 04:55
    ♥ Do have faith in what you're doing.