当你第一次尝试实现斐波那契数列时,可能会写出这样的递归代码: public int fib(int n) { if (n <= 1) return n; return fib(n - 1) + fib(n - 2); } 这段代码看起来简洁优雅,但当 n 达到 50 时,程序会运行很长时间才能返回结果。问题出在哪里?重复计算。计算 fib(5) 时会调用 fib(3),计算 fib(4) 时又会再次调用 fib(3)。随着 n 增大,重复计算的次数呈指数级增长——时间复杂度高达 $O(2^n)$。 ...
2008年，一位数据库研究员做了一个简单的实验：他用C++手写了一段处理TPC-H Query 1的代码，然后与当时最先进的数据库系统对比性能。结果令人震惊——手写代码比数据库快了整整一个数量级。这个结果刺痛了数据库社区：为什么精心设计的查询引擎，竟然输给了几行手写的循环？ ...
1970年，Edgar Codd在IBM发表关系模型论文时，可能没有预见到Join操作会成为此后五十年数据库性能优化的核心战场。一个看似简单的"将两张表按共同键合并"的操作，在算法层面却隐藏着从$O(m \times n)$到$O(m + n)$的巨大差异——对于两张各有100万行的表，这意味着从万亿次比较降到百万次，性能差距可达六个数量级。 ...
1966年，IBM研究员Laszlo Belady发表了一篇题为《A Study of Replacement Algorithms for a Virtual-Storage Computer》的论文。这篇论文提出了一个看似简单的问题：当缓存空间有限时，应该淘汰哪个数据？ ...
2016年3月22日，一个名为Azer Koçulu的程序员删除了他在npm上发布的273个包。其中一个叫left-pad的包只有11行代码，功能简单到令人发指——在字符串左侧填充空格。然而，这个微不足道的包被Babel、React、Webpack等数千个项目依赖。几小时内，全球JavaScript开发者的构建流水线开始大规模崩溃，Facebook、PayPal、Netflix、Spotify等公司的开发团队陷入混乱。 ...
1997年，NASA的Mars Pathfinder探测器在火星表面成功着陆后不久，开始出现诡异的系统重启。每次重启都导致数据采集中断，任务濒临失败。工程师们排查后发现，问题出在一个经典的分布式系统困境：优先级反转导致低优先级任务长时间占用关键资源，高优先级的"看门狗"任务无法及时执行，系统误判为故障并触发重启。 ...
title: “跳表：概率如何击败确定性复杂度” date: “2026-03-07T04:35:05+08:00” description: “从William Pugh 1990年的原始论文出发，深入解析跳表的概率平衡原理、Redis与LevelDB的技术选型逻辑、与红黑树的权衡分析，以及为什么这种"用随机换简单"的设计哲学在高性能系统中持续发光。” draft: false categories: [“数据结构”, “算法”, “系统设计”] tags: [“跳表”, “Skip List”, “Redis”, “红黑树”, “概率数据结构”, “并发编程”, “LevelDB”] 1989年，马里兰大学的William Pugh向 Communications of the ACM 投递了一篇仅四页的论文。这篇论文提出了一个看似荒谬的问题：能不能用掷硬币的方式，替代红黑树中那些令人头疼的旋转操作？ ...