【全文检索引擎】Postings 与 codec：freqs、positions、skip 与 impacts
拆解 Lucene PostingsFormat 中 freqs/positions/offsets/payloads 各层语义；说明块编码、skip list 与 impacts 如何服务相交剪枝；解释短语查询为何依赖 positions。
skip-list 标签归档
共 4 篇文章 · 返回首页
并发跳表：ConcurrentSkipListMap 的设计
Java 的 `java.util.concurrent` 提供了 ConcurrentHashMap，却没有 ConcurrentTreeMap——取而代之的是一个基于跳表的 ConcurrentSkipListMap。为什么 Doug Lea 选择了跳表而不是红黑树？因为平衡树的旋转操作会同时修改多个节点的指针，在并发场景下几乎不可能做到无锁；而跳表天然的分层链表结构使得每次修改只涉及局部指针，为 CAS 操作提供了完美的施展空间。
【从零写一个 LSM-Tree 存储引擎】WAL + MemTable：崩溃了也不丢数据
从零实现 WAL 和 MemTable：WAL 的 record 格式与 32KB Block 对齐、跳表的 O(log n) 插入与查找、InternalKey 编码、崩溃恢复的正确性证明。从零写一个 LSM-Tree 存储引擎系列第 2 篇。
从零写一个 LSM-Tree 存储引擎
五篇长文，从 LSM-Tree 的设计哲学讲到完整 KV 引擎实现，最后用 Rust 重写并三方 benchmark 对比。每篇含完整 C 代码、架构图、数学推导。