V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
wheeler
V2EX  ›  数据库

请问 1000 万级别的 md5 条目(16 字节)需要能够尽可能快判断 exists,同时最好能够节省存储资源,应该怎么做比较好呢

  •  
  •   wheeler · 2023-08-09 22:00:27 +08:00 · 2050 次点击
    这是一个创建于 461 天前的主题,其中的信息可能已经有所发展或是发生改变。

    目前是直接灌的 sqlite ,不知道有没更好的做法

    20 条回复    2023-08-10 18:25:59 +08:00
    xmh51
        1
    xmh51  
       2023-08-09 22:07:04 +08:00
    使用嵌入式的磁盘 key value 数据库即可
    https://github.com/jankotek/mapdb
    https://github.com/berkeleydb/je
    xmh51
        2
    xmh51  
       2023-08-09 22:08:12 +08:00   ❤️ 1
    推荐 berkeleydb
    qwerthhusn
        3
    qwerthhusn  
       2023-08-09 22:09:13 +08:00   ❤️ 1
    看下布隆过滤器能不能满足需求
    kokutou
        4
    kokutou  
       2023-08-09 22:17:08 +08:00 via Android   ❤️ 1
    按开头首字母数字分成 32 个库扔固态上,分 32 个地址去查询,会比直接一个数据库查快吗?
    或者 32^32 个库呢?
    leonshaw
        5
    leonshaw  
       2023-08-09 22:17:45 +08:00   ❤️ 2
    数据也就 100 多 M 而已
    dode
        6
    dode  
       2023-08-09 22:23:12 +08:00 via Android   ❤️ 1
    树结构,分层,分区,可以优化命中次数
    Vegetable
        7
    Vegetable  
       2023-08-09 22:26:16 +08:00   ❤️ 1
    别想了,数据库就是最好的办法。其他方法都快不了多少,但是多费不少事儿。

    很久以前做过一个手机号 md5 的反查的工具,穷举国内手机号大概是 40 多亿个,基于二分法在硬盘上反查,普通固态上一秒我记得能处理大概四五千个吧。我估摸着数据库应该不会比这慢,不过数据塞到数据库里很烦,当时能用的数据库还是个机械硬盘,直接给我劝退了
    virusdefender
        8
    virusdefender  
       2023-08-09 22:27:27 +08:00   ❤️ 1
    我这有个 1400w 的 sha256 存 boltdb 才 600 多 M
    aikdong
        9
    aikdong  
       2023-08-09 22:28:21 +08:00   ❤️ 1
    1000 万直接放内存里面,单线程 1000 万次比较 0.36s:
    ```python
    import string
    import random
    # initializing size of string
    N = 16
    data = set()
    for i in range(10000*1000):
    data.add(''.join(random.choices(string.ascii_letters, k=N)))

    start=time.time()
    sample = ''.join(random.choices(string.ascii_letters, k=N))
    for _ in range(10000*1000):
    if sample in data:
    pass
    end=time.time()
    print("set:", end-start)
    ```
    x77
        10
    x77  
       2023-08-09 22:35:37 +08:00 via Android   ❤️ 1
    这种问题偏理论技术,偏工程的技术(放内存啥的)提升很有限,要鸟抢换炮的提升估计得有理论上的支撑
    rrfeng
        11
    rrfeng  
       2023-08-09 23:03:43 +08:00 via Android   ❤️ 1
    除非没有 100M 内存,不然不需要选择…
    raycool
        12
    raycool  
       2023-08-09 23:54:00 +08:00   ❤️ 1
    放内存里
    thinkershare
        13
    thinkershare  
       2023-08-10 00:17:44 +08:00   ❤️ 1
    这么点数据,有啥可讨论的。
    weiqk
        14
    weiqk  
       2023-08-10 00:21:45 +08:00
    @leonshaw
    >> 数据也就 100 多 M 而已
    这个数据量啥也不用想,放内存,遍历 @wheeler
    WuSiYu
        15
    WuSiYu  
       2023-08-10 00:29:58 +08:00   ❤️ 2
    扔内存里用哈希表就行,用 redis 即可
    leonshaw
        16
    leonshaw  
       2023-08-10 00:32:30 +08:00
    @weiqk 遍历有点暴力,排个序二分差不多了
    smirkcat
        17
    smirkcat  
       2023-08-10 10:12:03 +08:00   ❤️ 1
    直接内存映射数据库 ,很多语言的都有,谷歌搜很多,python 我目前用到的,几千万数据,瞬间加载,就是初始化 db 文件需要点时间,后续查询非常快,上亿数据也没问题,内存映射数据应用到很区块链上和大数据分析上,可以了解一下啊
    smirkcat
        18
    smirkcat  
       2023-08-10 10:12:49 +08:00
    @smirkcat python lmdb
    wxf666
        19
    wxf666  
       2023-08-10 17:20:40 +08:00
    @leonshaw #16 用哈希应该更快些?
    leonshaw
        20
    leonshaw  
       2023-08-10 18:25:59 +08:00   ❤️ 1
    @wxf666 本来就是 md5 了,可以直接参考页表构造几级索引
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   5466 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 33ms · UTC 07:04 · PVG 15:04 · LAX 23:04 · JFK 02:04
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.