阿里面试， redis 里存有 10 亿键值对，找出一个指定前缀的所有键，说出实现原理。
linxiaoziruo 2020-07-25 19:37:50 +08:00 5027 次点击这是一个创建于 1907 天前的主题，其中的信息可能已经有所发展或是发生改变。
 | 1 ruanimal 2020-07-25 21:24:27 +08:00 前缀树？不然只能遍历吧 |
 | 2 wangyzj 2020-07-26 00:44:35 +08:00 他是让你造 java 代码的火箭 还是让你造 redis 内部数据结构的火箭啊？ |
 | 3 izzy27 2020-07-26 09:19:08 +08:00 倒排？ |
 | 4 SingeeKing PRO 官方做法就是遍历所有键 https://redis.io/commands/keys https://github.com/redis/redis/blob/unstable/src/db.c#L630 自己实现的话，之前我遇到这个需求时做法是用另一个键存。比如存了 a::b::c 和 a::b::d，就在 a::b 中存储 c 和 d |
 | 5 linxiaoziruo OP @SingeeKing 有个 scan 命令 |
 | 6 jeffh 2020-07-26 14:01:05 +08:00 scan 遍历吧，具体 scan 内部是不是遍历就不清楚了 |
 | 7 useben 2020-07-26 17:12:01 +08:00 前面的在答什么。。。 |
 | 8 gabon 2020-07-26 21:09:15 +08:00 via Android scan，之前有个 Redis key 迁移的场景就是用的 scan，axxx-》 bxxx |
 | 9 hangszhang 2020-07-26 21:40:40 +08:00 这还能怎么办?sacn 啊 |
| 10 linxiaoziruo OP scan 都知道，关键是 scan 怎么实现大数据查找的，面试官想问 scan 的原理，本质是想知道我有没有看过 scan 的源码。 |
 | 11 BlackwithBrown 2020-07-27 09:47:38 +08:00 scan 0 MATCH X* COUNT 1000 遗憾的是 redis 的底层也是先根据游标遍历再根据 match 筛选的 |
 | 12 Aresxue 2020-07-27 10:45:15 +08:00 自己设计结构的话仿照 mysql 的索引使用 B+树去处理，多层 hash，这样速度会有提升，但索引本身是一份冗余数据，相当于空间换时间了 |
 | 13 palmers 2020-07-27 10:53:41 +08:00 我觉得这道题就是简单的考察 redis 命令 scan 以及 scan 大致的原理 就是利用游标什么的 就是具体怎么使用的 这样基本应该可以及格了 深层次应该不会是主要考察点 否则就是不是应用了 但答对了 肯定是加分不少 |
| 14 linxiaoziruo OP @palmers 只是考察 scan 的话就没必要特意加上 10 亿数据这个前提，还着重跟我确认 10 亿数据。 |
| 15 palmers 2020-07-27 11:08:12 +08:00 @linxiaoziruo 对啊 数量级大 是应该用 scan 啊 否则 keys 会阻塞 业务会受影响 |
 | 16 acainiao 2020-07-27 11:19:05 +08:00 via iPhone n 叉树，每个节点最多 26 个字节点，可以确保常数事件 |
 | 17 IMXT 2020-07-27 11:31:21 +08:00 via Android tire |
 | 18 portlet 2020-07-27 11:33:31 +08:00 字典树 |
Select Language