没有完美的数据结构：从时空权衡到缓存友好的选择之道
1953年，IBM工程师Hans Peter Luhn在一份内部备忘录中提出了一个改变计算机科学进程的想法：用哈希函数将数据映射到固定位置，实现快速查找。这个被称为"哈希表"的数据结构，至今仍是计算机领域应用最广泛的发明之一。 ...
LSM树
B+树与LSM-tree：为什么数据库存储引擎没有万能方案
1970年7月，波音研究实验室的 Rudolf Bayer 和 Edward McCreight 首次流传了一篇题为"Organization and Maintenance of Large Ordered Indices"的论文，两年后正式发表在 Acta Informatica 期刊。他们发明的 B-tree 在此后五十年里统治了数据库存储引擎的设计。 ...
布隆过滤器：用 9.6 个比特存储一个不确定的「是」
1970年，计算机科学家Burton Howard Bloom在《Communications of the ACM》上发表了一篇论文，标题是"Space/Time Trade-offs in Hash Coding with Allowable Errors"。论文只有五页，提出的问题却出奇地实用：如果你想在一个有限的内存空间里存储大量数据，并且允许偶尔犯错，能做到什么程度？ ...