阿里面试， redis 里存有 10 亿键值对，找出一个指定前缀的所有键，说出实现原理。
linxiaoziruo · 2020-07-25 19:37:50 +08:00 · 4697 次点击这是一个创建于 1613 天前的主题，其中的信息可能已经有所发展或是发生改变。
 |
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 2020-07-26 10:39:19 +08:00
官方做法就是遍历所有键
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