文件系统的树:从 ext4 extent tree 到 btrfs CoW B-tree

你的 ext4 文件系统上有一个 1TB 的数据库文件。内核如何在 O(log n) 时间内找到文件偏移量 847,293,510,144 对应的物理磁盘块?答案藏在 extent tree 里。本文逐一拆解 ext4、XFS、btrfs、ZFS、F2FS 五种文件系统的树形结构设计。

无锁队列:Michael-Scott 算法与 ABA 问题

当多线程争抢一把 mutex 保护的队列时,吞吐量随线程数增长反而下降——锁成了瓶颈。无锁队列用 CAS 循环取代互斥,换来真正的无阻塞并发,但也引入了 ABA 问题和内存回收的工程深渊。

点定位与梯形分解

给定一个被线段划分的平面,如何快速确定一个查询点落在哪个区域?梯形分解用随机增量法构建 O(log n) 查询的优雅结构。