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

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

  •  
  •   kisshere · 125 天前 · 1467 次点击
    这是一个创建于 125 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

    求推荐

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

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

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

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

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