红色警报，Redis跳表那些面试题又来了，准备好被难倒没？

（来源：网络技术社区与常见面试题汇总）

红色警报,Redis跳表那些面试题又来了，准备好被难倒没？

朋友们,是不是感觉每次面试官一提到Redis，心里就咯噔一下？尤其是当“跳表”这两个字从他们嘴里蹦出来的时候，是不是瞬间觉得空气都凝固了？别慌，今天咱们就来把这些磨人的小妖精一个个揪出来，看看它们到底想干嘛。

面试官最爱问的,也是最基础的：“Redis为啥要用跳表来实现有序集合（Zset）的一部分，而不用红黑树之类的？”（来源：高频面试题）

你可别小看这个问题,它背后藏着好几个坑，最简单的回答是：跳表实现起来比红黑树简单多了，代码好写，不容易出错，调试也方便，对于Redis这种追求性能和稳定性的数据库来说，简单可靠就是王道，但光说这个可不够。

你得接着说：跳表在范围查找上优势巨大！想象一下，你要找分数在70到90分之间的所有学生，如果用红黑树，你得中序遍历，效率是O(N)，但跳表不一样，它底层是有序链表，找到70分那个节点后，直接在链表上往后遍历就行了，巨快无比，而Redis的有序集合经常用于排行榜、延时任务这些需要范围查询的场景，所以跳表是绝配。

还有一点,虽然红黑树的插入、删除、查找也是O(logN)，但跳表的常数项更小，而且在并发环境下，跳表更容易实现无锁操作，虽然Redis是单线程用不上这点，但这也体现了跳表设计的优越性。

紧接着,第二个经典问题就来了：“详细说一下跳表的查找过程，是怎么做到那么快的？”（来源：数据结构深度考察）

你就把跳表想象成一个多层的火车票售票系统,最底层（L1）是所有车票，按顺序排好队，比如从1号到1000号，你想找850号票，如果一张张数，得数850次，太慢了。

售票处加了第二层（L2），这一层只卖尾号是0的票，比如10, 20, 30... 1000，现在你找850号，先在L2层找，快速跳到800号票，然后从800号再下到L1层，往后数50张就找到了，速度快了很多。

如果数据量再大,还可以加第三层（L3），只卖尾号是00的票，比如100, 200, 300... 以此类推，这个“层”就是索引，跳表的查找就是从最高层的索引开始，像下楼梯一样，一层层往下跳，每次跳过一大片不可能的数据，最终定位到目标，这就是它“跳”字的由来，时间复杂度是O(logN)。

第三个常问的点是关于插入的：“新节点插入时，层高是怎么确定的？为什么不能固定层高？”（来源：对跳表核心机制的理解）

如果固定层高,比如所有新节点都是3层，那随着数据插入，上层节点会变得非常密集，索引的效果就大打折扣了，最后可能退化成接近普通链表。

所以跳表用了一个非常巧妙又随机的办法：抛硬币，一个新节点进来，它肯定在第一层，然后开始抛硬币，如果是正面，它就“晋升”到第二层；再抛一次，如果又是正面，就晋升到第三层……直到抛到反面为止，这样，每个节点的层高是随机的，但总体上，高层级的节点会非常少，低层级的节点多，自然而然地形成了一种“金字塔”式的索引结构，既保证了效率，又避免了人为维护平衡的开销。

第四个问题可能会更深入一点：“跳表和B+树在范围查找上都有优势，它们有啥区别？”（来源：对比类问题）

这是个好问题,简单说，B+树更像一本厚厚的字典，有严格的目录结构，所有数据都放在叶子节点上，非常规整，特别适合磁盘这种块设备读写，因为一次I/O可以读入一个节点（包含很多数据），而跳表更像一个多级导航系统，更“松散”一些，它是在内存中的链表基础上加索引，更适合完全在内存中操作，所以Redis这种内存数据库用跳表很合适，而MySQL的索引用B+树是为了减少磁盘I/O。

面试官可能会来个突然袭击,考察你的知识广度：“除了有序集合，Redis还有哪里用到了跳表？”（来源：对Redis源码的深入了解）

这时候你别懵,其实在Redis的集群模式中，每个节点也维护着一个跳表，这个跳表是用来快速定位某个键（key）应该由哪个槽（slot）负责，进而知道是哪个节点负责，这保证了集群中节点能高效地路由请求。

你看,一个看似简单的跳表，能挖出这么多问题，从为什么用，到怎么工作，再到和别的数据结构对比，最后到实际应用，下次面试前，别再只是死记硬背“跳表是O(logN)”了，把这些前因后果、来龙去脉都想清楚，才能真的不怕问，红色警报常响，但准备充分了，它就是你的冲锋号！