skip-list 标签归档

共 5 篇文章 · 返回首页

并发跳表：标记删除、乐观加锁与 ConcurrentSkipListMap

跳表插删要改多个指针，靠标记删除或乐观加锁把它们变成一次线性化操作。对照 Pugh、Harris、Fraser、HLLS 与 JDK 21、LevelDB、RocksDB 源码，并用 TSan 与对拍验证实现，实测独占 CPU 与超额订阅两种情形下的吞吐。

用 Seidel–Aragon 的祖先引理和 Pugh 的逆向分析推导 Treap 深度、旋转次数与跳表查找路径，逐项用计数实验核对；对照 Redis、LevelDB、RocksDB、JDK 源码核对 p 与层数上限，并讨论对手看得见随机性时的退化。

拆解 Lucene PostingsFormat 中 freqs/positions/offsets/payloads 各层语义；说明块编码、skip list 与 impacts 如何服务相交剪枝；解释短语查询为何依赖 positions。

从零实现 WAL 和 MemTable：WAL 的 record 格式与 32KB Block 对齐、跳表的 O(log n) 插入与查找、InternalKey 编码、崩溃恢复的正确性证明。从零写一个 LSM-Tree 存储引擎系列第 2 篇。

五篇长文，从 LSM-Tree 的设计哲学讲到完整 KV 引擎实现，最后用 Rust 重写并三方 benchmark 对比。每篇含完整 C 代码、架构图、数学推导。