2000W 个不重复的 32 位长字符串存于 mysql 中，现在怎样判断该数据表中存在某个特定值？
Reign · 2017-02-15 17:38:20 +08:00 · 3742 次点击这是一个创建于 2840 天前的主题，其中的信息可能已经有所发展或是发生改变。
目前的业务逻辑是，有 2000W 个 32 位长字符串存在 mysql 中，该 mysql 表就只有 2 个字段，自增 id 和 hash ，现在要验证这个表中是否存在某个 hash 值，怎样用最简单快速的方法查询？我想到过用 redis 来存，但是内存吃不消，有没有好的解决方案？谢谢
 |
1
eote 2017-02-15 17:39:22 +08:00
排序+binary search
|
|
2
eote 2017-02-15 17:40:29 +08:00
或者 bitmap
|
 |
3
forestyuan 2017-02-15 17:44:57 +08:00
建个索引然后用 SQL 查询就行了吧
|
 |
4
withlqs 2017-02-15 17:46:09 +08:00
字典树
|
 |
5
Reign OP @forestyuan 感觉有点慢 硬盘很渣
|
 |
6
allenhu 2017-02-15 17:47:44 +08:00
加多一列 crc ，存 crc32 （ hash ），然后 加 index idx_crc(crc32),配合缓存，速度不会太慢。
|
 |
7
freeminder 2017-02-15 17:48:06 +08:00  1
bloom filter?
|
 |
8
liuxu 2017-02-15 17:49:04 +08:00
这。。该 hash 分表了，根据 hash 最后 2-3 位分成 100-1000 个表。
|
 |
10
w2exzz 2017-02-15 17:49:28 +08:00
显然是再增加一列啊……这一列保存 hash 值…… hash 值留 8 位就行了
然后搜索的时候先匹配 hash 值，匹配到了再匹配全部内容。都一致就找到了。 hash 不一致就 pass |
|
11
forestyuan 2017-02-15 17:56:20 +08:00
如果自己写算法，一来容易有 BUG ，二来也不一定比数据库引擎优化的好。
|
 |
12
Michaelssss 2017-02-15 18:00:00 +08:00
2000W 好像建个索引就完事了。。。。这数据量不大。。。 5~10MS 都出来了。。。
redis 你没必要全部扔进去啊，- -查询成功一次扔一次，缓存成功就直接走缓存，缓存失败再去 mysql ，这才是缓存的意义啊 |
|
13
Michaelssss 2017-02-15 18:02:28 +08:00
如果要自己写算法就是 boolean filter
|
 |
14
jianzhiyao020 2017-02-15 18:14:26 +08:00
建索引啊，有这么复杂？
|
 |
15
cloudzhou 2017-02-15 18:21:07 +08:00
@allenhu 方法可行
另外有一个取巧的方法，需要更改一下业务： 就是 hash 里面隐含着 id 我详细解释一下，比如在生成 hash 的时候（大部分是随机值） hash 值为空，先 save 一下，得到自增 id ，比如 1000 ，然后简单的用 36 进制表示，就是 rs 然后命名规则如下： 1 位是表示 36 进制长度 + N 位是 36 进制值 + （ 32-1-N ）位随机值 然后 update set hash = '...' where id = 1000 更新进去 例子，比如 1000 ，那么表示为 2rs... 这样， hash 里面直接可以获取 id ，然后取出来直接进行字符匹配，判断是否正确。 |
|
17
allenhu 2017-02-15 18:33:18 +08:00
@cloudzhou 你说的这个方法有点意思，但是好像并不能解决 lz 说的问题，因为一开始，你是没法知道自增 id 是多少的，你知道的只是后面那部分
|
 |
18
manhere 2017-02-15 18:34:29 +08:00
彩虹表？
|
 |
19
Abirdcfly 2017-02-15 18:37:15 +08:00 via iPhone
建索引，挺快的。
|
 |
20
ichou 2017-02-15 19:39:05 +08:00 via iPhone
2000 万数据量不大啊，感觉有索引不至于慢到不能接受哦
|
|
21
ichou 2017-02-15 19:47:51 +08:00 via iPhone
@cloudzhou 你不觉得你多了一次写入么，哈哈
如果要保证原子性，你还必须要加上事务，写并发一旦飙起来，扑街 |
 |
22
luban 2017-02-15 19:50:43 +08:00 via iPhone
redis 开压缩，两三 G 内存吧
|
 |
23
billlee 2017-02-15 20:30:07 +08:00
才两千万，直接建索引足够了
|
 |
24
xfwduke 2017-02-15 20:42:47 +08:00
有效数据行长度 40 bytes
2000kw 数据 762MB 算上 Innodb 的空洞, 各种乱七八糟的元数据, 3GB 差不多了吧 这点数据, 写算法都多余, 建个索引 就现在服务器的内存量, 最后整个索引估计都在 buffer pool 里面. 别说服务器了, 桌面机都能搞定, 并发访问不大的话 |
 |
25
shiny 2017-02-15 20:46:18 +08:00
做索引，而且不需要整个字符串都在索引里面。
|
 |
26
ryd994 2017-02-16 06:46:28 +08:00 via Android
hash 不要用 hex 字符串存，用二进制字符串或者 binary 类
|
|
27
ryd994 2017-02-16 06:51:44 +08:00 via Android
另外楼上有说取前几位加列的，你们真的懂数据库索引么？
索引 n 叉树结构本来就是先比较前面的 如果后几位的随机性比前几位好的话，取后几位做联合索引，或者用于分表，倒是有的 换句话说，如果这种技巧有用，数据库自己早就该用了 |
 |
28
azh7138m 2017-02-16 10:19:44 +08:00 via Android
彩虹表吧，之前黄易那个我算完是 7500w 条， MySQL 分下表就好了，其他优化不做查起来也是快的飞起
|
 |
29
jsou 2017-02-16 12:30:11 +08:00
才 2000w 数据,建个索引,一个 where 条件不就出来了.
如果这都要优化这优化那的,那这数据库软件就不能用了. |
 |
30
ijustdo 2017-02-16 16:35:11 +08:00
把这个 32 位串当做表的主键
|
 |
31
Septembers 2017-02-16 16:53:43 +08:00
直接建立个 Hash Index 吧
see https://dev.mysql.com/doc/refman/5.7/en/index-btree-hash.html |
|
32
Septembers 2017-02-16 16:57:08 +08:00
Hex String 直接 string 储存开销有点大
可用固长 binary 储存可获得小一半的开销（同时也能降低索引的储存开销） see https://dev.mysql.com/doc/refman/5.7/en/binary-varbinary.html |
 |
33
abccoder 2017-02-16 17:06:23 +08:00
建立索引直接搞
|
|
34
ijustdo 2017-02-16 17:08:23 +08:00
别在 yy 其它建撒索引了 把这个 32 位串当做表的主键 这样最快 不行你们可以试试看
|
 |
35
realpg 2017-02-19 12:26:24 +08:00
高度怀疑楼主只是在编问题，根本没有这个环境进行测试
首先使用我的专用低性能测试机（用于测试程序性能） MYSQL 导入 2000W 条记录，插入 2000W 条数据用时 2787 秒(因为生成随机串的发生器有一定不随机性，生成了一部分重复数据，实际数据量 19787975 条，近似当两千万看吧 懒得继续插了)  结构（索引情况）  服务器配置： AMD 不知道啥时候的双核低端 CPU ， 2G*2 DDR2 800 内存，硬盘 500G 普通 SATA 淘汰硬盘 随便从库里找 50 个串进行搜索，使用 SQL NO CACHE 同时每个数据只查一次避免其他缓存干扰 执行时间均为 0.00002 秒  |
|
36
realpg 2017-02-19 12:30:52 +08:00
不小心发出去了
插入两千万条数据用了将近 3000 秒，对我的破机器 IO 性能有直接概念了吧 DDR2 内存时期的古董双核 AMD 入门 CPU ，执行性能也有概念了吧 索引直接加在 hash_id 上，未限定索引长度，全默认，唯一索引 直接检索，都是 0.0002 秒这个量级，检索过一次产生缓存以后，每次查询都是 0.0001 |
Select Language