首页

投稿

结构共享：改一棵树，只复制从根到改动处的那条路

315

0

2026-10-19 15:23:34

未经作者授权，禁止转载

用四片叶子的不可变二叉树讲结构共享：改一个元素，只新建从根到它的那条路，其余节点新旧两版共用，旧版本一直还在。Git 的目录树、Immer 的状态、Clojure 的 vector 都是它。

成富_Alex 发消息

全栈工程师 / 架构师 / 技术内容创作者 / 非畅销书作者

环形缓冲区：一块固定的数组，读写指针追着跑

03:16

LMAX Disruptor：每秒六百万笔订单，队列里一把锁都没有

06:05

时间轮：海量定时任务的 O(1) 调度

04:46

分层时间轮：像时针和分针，远的任务不用白转

03:18

LRU Cache：哈希表加双向链表，为什么每步都是 O(1)

03:57

CLOCK：不挪链表，只转一根指针的"近似 LRU"

03:36

LFU：按次数淘汰，老热点为什么赖着不走

03:44

2Q：新来的先在门口排队，来第二次才进正厅

03:01

ARC：在"看最近"和"看次数"之间自己调节

03:29

TinyLFU：淘汰之前，先问谁过去更常被请求

03:52

Gap Buffer：光标处留一段空白，打字只是往空白里填

02:47

Rope：在百万字文档开头打字，为什么不卡

04:25

Piece Table：原文一个字都不改，只记“从哪里拿几个字”

03:46

Roaring Bitmap：每块自己挑数组还是位图，亿级集合毫秒求交

06:03

令牌桶：平均每秒 1 次，但攒够了可以一下来 5 次

03:26

滑动窗口限流：固定窗口在整点交界处会放进两倍流量

04:18

熔断器：连续失败时，最好的请求是别发

03:49

写时复制：大家先共用一份，谁要改谁才复制

04:33

结构共享：改一棵树，只复制从根到改动处的那条路

04:40

工作窃取：每个线程先做自己的活，空了再偷别人的

03:57

差值 + Varint：一串有序的 ID，为什么每个只占一个字节

04:54

Arena 分配器：分配只挪一根指针，释放一次全部

03:39

Slab 分配器：同样大小的对象，释放了就原地再用

04:00

顶部