系统设计

title: “为什么数据库索引选择B+树而不是Hash？从磁盘IO特性到范围查询的技术真相” date: “2026-03-07T05:05:02+08:00” description: “为什么数据库索引选择B+树而不是Hash？从磁盘IO特性到范围查询的技术真相” draft: false categories: [“数据库”, “系统设计”] tags: [“B+树”, “Hash索引”, “数据库索引”, “InnoDB”, “PostgreSQL”, “磁盘IO”, “范围查询”] 1972年，Rudolf Bayer和Edward McCreight在波音研究实验室工作时遇到了一个棘手问题：如何高效地组织存储在磁盘上的大量有序数据？他们在当年发表的论文"Organization and Maintenance of Large Ordered Indexes"中提出了B树（B-tree），这个数据结构在此后的半个世纪里统治了数据库索引设计。但有一个疑问始终困扰着许多开发者：Hash表在内存中拥有O(1)的查找效率，为什么数据库偏偏选择了看起来更慢的B+树？ ...

想象这样一个场景：你的生产环境中有一个存储过程，平时执行只需几百毫秒，突然某天开始，同样的调用却需要几分钟甚至更长时间。你检查了服务器资源——CPU、内存、磁盘IO都正常。你把存储过程中的SQL语句单独拎出来执行，发现跑得飞快。你尝试ALTER一下存储过程（什么代码都没改），问题竟然消失了。 ...

2014年4月，Heartbleed漏洞震惊全球。这个OpenSSL库中的缓冲区越界读取漏洞可能导致服务器私钥泄露，理论上需要立即撤销并重新签发所有受影响的证书。然而，马里兰大学的研究团队在三周后发现：超过73%的易受攻击证书未被重新签发，超过87%未被撤销。更令人担忧的是，撤销率在周末会显著下降——仿佛攻击者也会休息。 ...

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 投递了一篇仅四页的论文。这篇论文提出了一个看似荒谬的问题：能不能用掷硬币的方式，替代红黑树中那些令人头疼的旋转操作？ ...

2011年8月28日，一名伊朗用户在访问Gmail时发现浏览器显示的证书异常。这条看似微不足道的线索，揭开了一场影响超过30万人的大规模中间人攻击。攻击者不是破解了加密算法，也没有入侵Google的服务器——他们只是拿到了一张合法的证书。 ...

在Stack Overflow上搜索"Markdown解析"，会出现超过2万个问题。其中最高赞的一个问题是：“为什么***foo***会被解析成斜体加粗，而***foo**却变成了粗体加星号？“这个看似荒谬的问题，实际上触及了Markdown解析器最核心的设计困境。 ...

1971年，ACM Computing Surveys发表了一篇题为《System Deadlocks》的论文。作者Edward G. Coffman Jr.、M. J. Elphick和Arie Shoshani系统阐述了死锁发生的四个必要条件——互斥、持有并等待、非抢占、循环等待。这篇论文奠定了此后半个多世纪死锁研究的理论基础。然而，五十年过去了，死锁仍然是数据库系统中最常见的生产事故之一。2021年，北卡罗来纳州立大学的研究团队对106个数据库后端Web应用进行调研，收集了49个真实的死锁案例。研究发现，跨请求的数据库锁死锁不仅最常见，也是现有工具最难处理的类型。 ...