这个问题我前后被问过不下十次有刚毕业的应届生有写了五年业务代码的后端也有做数据平台的架构师。每次被问到我都觉得只背结论太可惜了——InnoDB用B树是因为磁盘IO、Redis用跳表是因为内存操作这句话方向没错但信息量约等于零。真正值得挖的是藏在一堆术语底下的物理规律和工程权衡。今天就把这件事从头到尾掰开聊一遍。先说结论再讲道理B树和跳表本身没有谁好谁坏它们是两套完全不同的设计取舍。InnoDB选B树是因为它的战场在磁盘Redis选跳表是因为它的战场在内存。两者互换都会在各自最核心的读写路径上付出难以接受的代价。而这个代价到底有多大才是这篇文章真正想让你带走的东西。1. 这个经典对比题本质上比的是硬盘和内存的物理差异1.1 一次内存访问和一次磁盘访问相差四五个数量级先看一组谁都会背但不一定真感受过的数字。CPU访问L1缓存大概是0.5纳秒到1纳秒访问主内存大概是100纳秒级别而一次机械磁盘的随机IO寻道加旋转延迟通常是5到10毫秒。10毫秒除以100纳秒差了大约5万倍也就是四到五个数量级。这个差距有多夸张我换个说法如果一次内存访问是你从沙发上站起来拿杯子的时间那一次磁盘随机访问大约相当于你订了张机票飞一趟上海再飞回来。注意这还只是一次访问。数据库里每条SQL背后都是成千上万次这种操作所以存储引擎的每一层设计首要任务就是穷尽一切手段减少磁盘随机访问。SSD的出现让这个差距缩小了一些随机读大概能到0.1毫秒到0.2毫秒但依然比内存慢三个数量级左右。而且SSD的随机写和顺序写在寿命、擦除粒度、写放大上还有自己的一套逻辑存储引擎同样要刻意把随机IO转成顺序IO。这就是为什么InnoDB要引入页这个概念。磁盘不是按字节读的是按块读的机械盘按扇区通常512字节到4KB而InnoDB自己又把逻辑读写单位定成了16KB的页。一次IO最少也要读一整个页进来所以索引结构必须围绕一次IO尽量多拿有用的数据来设计。1.2 存储引擎选型的三个约束介质、访问模式、实现成本理解了IO差距再看任何存储系统的索引选型其实都是在三个约束里找平衡存储介质的物理特性读写是顺序快还是随机快最小IO单位多大业务访问模式追求点查还是范围查写多还是读多数据量级多大实现与维护成本结构是否容易实现、是否方便做并发控制、是否利于持久化InnoDB面对的是磁盘介质 以点查和范围查为主 支持事务和崩溃恢复这个组合Redis面对的是内存介质 高频读写 单线程事件循环 持久化靠RDB/AOF这个组合。组合不同最优解自然不同。这个三角约束的框架比背一百个数据结构对比表格都有用。后面所有细节其实都是在往这个框架里填肉。2. B树是为磁盘而生的从一次页读取到千万级数据的数学账2.1 B树用矮胖换少读盘B树最核心的设计就是矮胖。一棵三层B树从根节点到叶子节点只要走三次指针也就是三次磁盘IO就能定位到目标记录所在的页。为什么能做到这么矮因为每个节点——也就是InnoDB里的一个页——能存很多个key和孩子指针。假设页大小16KB主键是8字节的bigint再加6字节的页指针一个KV对大约14字节。那么一个非叶子页大约能存16KB / 14B约1170个指针。三层B树能覆盖的叶子页数量就是1170 × 1170约137万个页。如果每个页里存放的行比较紧凑比如按常见行大小折算差不多能支撑千万到两千万行的表。这个账要会自己算面试和实际调优都能用到。关键在于树的层数决定了磁盘IO的次数磁盘IO的次数决定了查询的耗时量级。B树的矮胖结构就是为把磁盘访问次数压到三次以内这个目标服务的。2.2 聚簇索引让按主键插入几乎变成顺序写B树另一个容易忽略的优点是InnoDB的主键索引是聚簇索引。什么意思就是叶子节点直接存放整行数据数据行物理上就按主键顺序排列在B树的叶子页里。这个设计直接影响了写入性能。如果你用自增主键新插入的行主键是递增的那么在索引层面新数据几乎总是追加到最右边的叶子页里。再加上InnoDB在底层分配新页时尽量分配物理相邻的页这样磁盘写入大概率是顺序追加而不是东写一块西写一块。这也是为什么业内反复强调不要用UUID作主键——UUID随机性太强每插一条都可能落到不同的叶子页B树要频繁做页分裂和页重组本来能顺序写的场景变成大量随机写性能自然崩。反过来看B树的页分裂本身是一种成本。一个页满了要把一半记录挪到新页涉及原页和新页的写入如果页恰好不在buffer pool里还得先从磁盘读进来。这个成本在顺序插入时能接受在随机插入时会被放大成典型的写放大问题。2.3 叶子节点双向链表范围查询的隐藏助攻顺着聚簇索引往下再挖一层——B树的所有叶子节点按key顺序用双向链表串了起来。这意味着范围查询比如WHERE id BETWEEN 100 AND 1000在找到第一个命中的叶子页之后后续记录直接从链表上顺序往后拖就行不需要回树里逐层查找。这个特性对磁盘介质特别重要。因为顺序读相邻页比随机访问分散页快太多链表把逻辑上连续的数据尽量锚定在物理上相邻的页中。范围查询的IO从随机访问退化成顺序预读性能差距可能是两个数量级。MySQL优化器也特别依赖这个特性所以对B树而言范围查询几乎是零成本附带的能力。3. 跳表凭什么成为Redis ZSet的默认选择如果面试被问到回答的四层递进3.1 内存里没有寻道B树最核心的优势被消解了现在把场景切到Redis。Redis把所有数据放在内存里内存随机访问虽然比顺序访问慢一点但慢的幅度很小不存在磁盘那种寻道旋转的物理惩罚。B树为磁盘优化的种种设计——页、矮胖、叶子链表——在内存里不能说完全没用但性价比变了。最典型的变化是一次查找读多少个节点。磁盘场景下我们希望一次IO尽量少因为一次IO就是10毫秒级别的开销内存场景下一次指针跳转就是几纳秒到几十纳秒的事情多走十几步完全无所谓。B树用每层大扇出换来的矮胖优势在内存里就不值钱了。Redis需要的是一个在内存里容易实现、维护成本低、支持范围查询、插入删除都够快的有序结构。跳表就是在这个约束下冒出来的最优解之一。3.2 跳表的结构与概率平衡不需要旋转的树跳表的本质可以理解成有序链表 分层索引。最底层是一个完整的有序链表上面每一层都是下一层的稀疏索引。查找的时候从最高层往下走每层跳过一批节点最终落到底层精确定位。它用什么机制保持平衡不是旋转是概率。新节点插入时先抛硬币——严格说是按概率随机——决定它出现在哪些层上。Redis的实现里这个概率是1/4也就是一个新节点有1/4概率升高一层再往上又是1/4以此类推。单看数学期望大部分节点只有一两层高少数节点会比较高整体呈幂律分布。这就是跳表和红黑树、AVL树最本质的区别平衡树靠旋转来强行维持结构稳定跳表靠概率让结构在统计意义上大致均衡。前者维护成本高但性能有确定性保证后者实现简单、维护便宜性能是期望意义上的好。Redis官方和社区反复提到过选用跳表的重要原因包括实现简单、几乎不出Bug、调试方便、天然支持范围查询而且在没有锁的单线程模型下没有并发旋转的负担。你如果问为什么不用红黑树答案就是红黑树实现复杂范围查询需要中序遍历而跳表在有序链表上横向走就行。在Redis这种追求简单可靠、能省则省的项目里红黑树的复杂度完全不划算。3.3 插入一个元素跳表只改几个指针B树可能要分裂页再看写入路径这个对比非常直观。B树插入一条记录最坏情况可能触发叶页分裂继而向上蔓延极端情况下还要调整层高和根节点。每一步都涉及页的分配、数据的搬运、指针的改写。在MySQL里一次页分裂可能意味着两个页的磁盘写入和多次日志记录。跳表插入一个节点要做什么先在底层链表找到插入位置然后更新前后节点的指针就行了高层索引的指针更新也只需要改涉及的那几层。因为层数期望值很低刚才说过大部分节点只有一到两层平均下来每插入一个元素需要修改的指针数量是个很小的常数。在纯内存环境里这个操作成本几乎可以忽略。这里顺便提一句RDB持久化和AOF重写都需要把全量数据顺序写出去。跳表作为底层有序存储遍历时走一遍最底层链表就是全局有序序列这对生成RDB快照特别友好。如果换成B树虽然叶子链表也能顺序遍历但每个页的存储结构在序列化、压缩方面反而不如跳表扁平。3.4 ZSet不是一棵跳表dict skiplist的经典组合有一半人不知道Redis的ZSet在底层面不是单独一棵跳表而是一个字典跳表的组合结构。dict负责按member查scoreO(1)搞定跳表负责按score范围和排序来查member。两者通过指针共享member和score对象不重复存数据。为什么非要这个组合因为单用跳表做按member查score需要O(log n)太浪费单用dict又做不了有序范围查询。7.0版本以后小规模ZSet还会先用listpack压缩存储等元素数超过阈值再升级成dict跳表这是Redis省内存的老传统。这个细节在面试里很加分因为它说明你不只是背了Redis用跳表这个结论而是理解了这个结论的边界。4. 互换实验把B树搬进Redis把跳表搬进MySQL4.1 Engine Yard把Redis存储换成B树ZSet操作慢了将近两成先看一个真实案例。2013年左右Engine Yard做过一个很有名的实验他们用B树改写了Redis的存储层想试试能不能替代跳跃表成为ZSet的底层结构。社区里公开的压测结果很清楚——B树版本在一些ZSet操作上比原版慢了大约15%到20%。原因不复杂。B树在内存里需要维护每个节点内部的键数组和节点间的链表插入时一旦页满就要分裂、搬运数据、更新父子指针这些操作在内存里就是实实在在的复制和移动开销。而跳表插入只需要申请新节点、改指针没有把某个页的一半数据挪走这种大搬运。引擎层面的测试还暴露了B树在内存碎片率上偏高因为页的分配和分裂会让内存区块碎片化。这个实验说明了一个很多人忽视的事实B树在磁盘上是神在内存里不见得打得过跳表。因为它的很多优势是基于页IO模型的脱离了这个模型优势就变成了负担。4.2 如果InnoDB用跳表随机IO与写放大反向做一个思想实验如果InnoDB底层用跳表代替B树会发生什么这里可以算一笔账估算写放大。InnoDB某条数据页的大小是16KB如果主键是随机的UUID每插入一条记录跳表需要更新多个层的指针而这些指针可能分布在不同节点中。这些节点在磁盘上的物理位置完全不连续每次更新指针都可能触发一次随机IO。多次随机IO叠加写放大系数轻松超过B树随机插入场景下的水平。更麻烦的是磁盘的最小IO单位是页。跳表的每个节点是散落分配的一个16KB的页里可能只装了寥寥几个跳表节点空间利用率非常难看。而B树用页内多键数组 页间双向链表的布局把一批逻辑相邻的key尽量塞进同一个页磁盘IO单位一次性搬回大量有效数据这是跳表根本做不到的。至于聚簇索引的优势——行数据物理上按主键顺序排列——跳表也没有对应的概念。跳表的底层链表只是逻辑有序物理位置完全随机范围查询时如果数据行被物理打散顺序扫描的局部性就很差磁盘预读机制直接失效。4.3 缓存局部性与CPU预取内存里为什么跳表和B树的差距不大这里面最微妙的一层是缓存局部性。B树把key集中在页里存储扫描一个页时CPU能顺序预取到一批key跳表的节点是分散的指针跳跃会破坏CPU预取。理论上B树在内存里应该也有局部性优势。但实际工程里Redis的单线程模型和极简数据结构设计让跳表避免了B树的内存开销和管理复杂度。而且Redis最重要的场景是点查和范围查跳表在百万级数据下平均只要跳十几层每一层是一两次指针跳转加起来不到几十纳秒到一两百纳秒对业务来说完全感知不到。换句话讲B树的局部性优势没有消失只是在内存场景下被指针跳转本身足够快给追平了。当一个劣势只影响百分之一毫秒的时间就不叫劣势叫可忽略的噪声。4.4 工程细节的分量持久化、并发与内存碎片最后要说说两类结构背后的工程负担。B树要支持事务和崩溃恢复就得配合redo log、undo log、双写缓冲、页校验等一整套机制。每次页分裂和页修改都要记日志崩溃后要基于逻辑日志和物理标记做恢复这部分复杂度和跳表完全不在一个量级。跳表结构本身几乎没有崩溃一致性问题Redis靠RDB和AOF在更高层解决了持久化。并发控制上InnoDB的B树页分裂时要加锁、做纵向锁定和横向锁定协调是数据库内核里公认的高难度模块。Redis选择单线程事件循环从根上绕开了多线程索引并发问题这也是跳表方案能够成立的重要前提——如果Redis是标准的多线程并发写索引跳表无锁化的复杂度也会上升。5. 跳出这两个选项从LSM-Tree和RocksDB看选型的本质5.1 LSM-Tree试图同时解决什么问题B树写入好还是读好读很好但随机写有页分裂和写放大问题跳表写入很轻但它只在内存里成立。那如果我就是想要写密集、还要扛海量数据呢LSM-Tree是第三种答案。LSM-Tree的思路是把随机写变成顺序写。数据先往内存里的MemTable写MemTable满了之后转成不可变的SSTable刷到磁盘。因为SSTable是顺序生成的磁盘写入全程是顺序IO。读的时候要查MemTable和多个SSTable于是要借助布隆过滤器、层级合并等技术来兜底读性能。RocksDB、LevelDB、HBase用的都是这个路子它们的取舍是牺牲一部分读性能和空间放大换来极端的写性能。这和B树正好形成对照——B树优先保证读写都有上限LSM优先保住写入吞吐。5.2 避坑经验回到业务场景而不是套结论这两年RocksDB很火有些团队把RocksDB当万能存储用结果发现它的读放大问题在某些场景下很难压住。如果你对这一段有切身体会就会明白真正决定架构成败的是对访问模式的判断——读写比、点查和范围查的比例、数据冷热分布比数据结构本身更能决定最终的存储选型。MySQL的InnoDB只用一个B树结构但为什么它在几十种业务形态下都能跑因为buffer pool把热页留在内存里磁盘IO被大量吸收B树在绝大多数时候是在内存页上做操作。Redis的跳表在几百万条数据的排行榜上也能保持低延迟因为范围查询和数据物理分布的耦合关系其实没有MySQL里那么严重。这些边界条件才是面试官真正希望你掌握的。5.3 如果面试被问到回答的四层递进虽然写这篇不是为刷题但这个问题确实高频出现在后端面试里所以我给出一个可以直接用的回答框架四层递进第一层介质差异B树优化磁盘IO跳表优化内存操作。这是最基本的结论。第二层操作差异InnoDB主键索引是聚簇索引数据按主键顺序存储B树的页内数组和叶子链表正好匹配磁盘分页读取和范围扫描Redis的ZSet需要同时支持按member查分数和按score范围查跳表实现简单插入删除稳定性好。第三层工程差异B树背后的redo log、页分裂、并发控制非常重跳表在单线程模型下几乎是零维护成本Engine Yard的实测数据可以作证。第四层认知模型所有的数据结构和存储系统都是介质物理特性、访问模式、实现成本三者之间的权衡不存在放之四海皆准的最优结构。把这四层讲完面试官基本就不用再追问了因为你已经把自己的分析框架展示出来了。6. 写在最后一些实际研发中的体会我自己在实战中的体会是别把这两个结构当成纯理论问题要当成性能预算问题。MySQL里把主键从自增换成UUID、导致大量页分裂的场景我亲手调过。表面看只是主键变了实际上随机插入让Buffer Pool命中率明显下降、IO队列持续走高性能直接掉了几个档次。排查到最后就是一句话B树的写入顺序太依赖主键顺序了。反过来做高并发排行榜的时候我最初用ZSet也想过要不要换成MySQL排序后来压测发现Redis的ZSet哪怕在百万量级下单次操作都在亚毫秒级MySQL经不起这种每秒几万次的范围查。选型不是理论竞赛是成本的直接换算。还有一个小技巧分享给做面试准备的朋友真没必要把两个结构的所有细节全背下来你只需要能算清楚磁盘IO次数、内存指针跳转次数、写放大系数这三个数字再结合一两个实例这个题就已经答完了。真正区分水平的不是谁背得全而是谁能把为什么背后的物理约束讲明白。再往后如果你想把这个问题研究透建议去看William Pugh的跳跃表原始论文再对比读一下InnoDB官方手册里关于聚簇索引和页分裂的章节。两者互相参照你会发现很多理所当然的架构选择当年都是在一堆彼此冲突的约束里咬牙拍板的结果。理解这一点比记住任何结论都值钱。