阿里面试， redis 里存有 10 亿键值对，找出一个指定前缀的所有键，说出实现原理。

[linxiaoziruo]

[ruanimal]

前缀树？不然只能遍历吧

[wangyzj]

他是让你造 java 代码的火箭
还是让你造 redis 内部数据结构的火箭啊？

[izzy27]

倒排？

[SingeeKing]

官方做法就是遍历所有键
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

[linxiaoziruo]

@SingeeKing 有个 scan 命令

[jeffh]

scan 遍历吧，具体 scan 内部是不是遍历就不清楚了

[useben]

前面的在答什么。。。

[gabon]

scan，之前有个 Redis key 迁移的场景就是用的 scan，axxx-》 bxxx

[hangszhang]

这还能怎么办?sacn 啊

[linxiaoziruo]

scan 都知道，关键是 scan 怎么实现大数据查找的，面试官想问 scan 的原理，本质是想知道我有没有看过 scan 的源码。

[BlackwithBrown]

scan 0 MATCH X* COUNT 1000
遗憾的是 redis 的底层也是先根据游标遍历再根据 match 筛选的

[Aresxue]

自己设计结构的话仿照 mysql 的索引使用 B+树去处理，多层 hash，这样速度会有提升，但索引本身是一份冗余数据，相当于空间换时间了

[palmers]

我觉得这道题就是简单的考察 redis 命令 scan 以及 scan 大致的原理 就是利用游标什么的 就是具体怎么使用的 这样基本应该可以及格了 深层次应该不会是主要考察点 否则就是不是应用了 但答对了 肯定是加分不少

[linxiaoziruo]

@palmers 只是考察 scan 的话就没必要特意加上 10 亿数据这个前提，还着重跟我确认 10 亿数据。

[palmers]

@linxiaoziruo 对啊 数量级大 是应该用 scan 啊 否则 keys 会阻塞 业务会受影响

[acainiao]

n 叉树，每个节点最多 26 个字节点，可以确保常数事件

[IMXT]

tire

[portlet]

字典树