时间轮 Timing Wheel

管理成千上万个定时器，朴素做法（有序链表 / 最小堆）的添加与删除是 $O(n)$ 或 $O(\log n)$。时间轮 (timing wheel) 把这两个操作压到 $O(1)$：一个环形数组，每格 (slot) 代表一个时间刻度 tick、挂一条到期定时器的链表 (bucket)，一根指针随真实时间每 tick 前进一格，只处理当前格——结构与 clock 表盘同构。

需要澄清的是：$O(1)$ 说的是对它做添加 / 删除 / 触发这几类操作的复杂度，不是「数据结构本身」的复杂度——复杂度永远是操作的属性。时间轮借了这三个操作的 $O(1)$ 给自己贴标签，底层机件则是环形缓冲区 (ring buffer)：固定数组 + 取模回绕的指针。

下面依次看单层轮、分层轮，再对比有序链表 / 最小堆并归纳环形结构的用途。每个 demo 都能添加定时器、单步推进指针，观察 bucket 增删与代码逐行高亮。

1 · 单层时间轮：槽位、指针与 rounds

核心机件只有三样：一个环形数组，每格 (slot) 代表一个时间刻度 tick，每格挂一条 bucket（到期定时器的链表），一根指针 (pointer) 随真实时间每 tick 前进一格，到头绕回 0。添加一个延迟 delay 的定时器，只需算出落点槽位 (pointer + delay) % slots、挂进那一格——$O(1)$,推进时指针走一格，只处理当前格里到期的定时器，不扫描其余格子。延迟超过一圈 ($delay \ge slots$) 的定时器，靠 rounds（还要绕几圈） 留在同一槽。

1.1 · delay 超过一圈：rounds 的代价

设 slots = 8，添加一个 delay = 20 的定时器：落点槽位 (pointer + 20) % 8，而 $rounds = \lfloor (20-1) / 8\rfloor = 2$——指针要两次经过该槽（每次把 rounds 减一）才在第三次触发。这让单层轮能表示任意远的延迟，但代价藏在 tick 里：每次推进都要遍历当前整槽给计数减一，于是触发不再是干净的 $O(1)$，而退化为 $O(当前槽元素数)$。

2 · 分层时间轮：cascade 与「槽位膨胀」

单层轮要表示「最长 N 个 tick」的延迟，要么靠 rounds 退化 tick、要么把格数铺到 N 个。设精度 1ms、范围 1 天，单层就得开 86,400,000 个格子，且绝大多数永远为空。分层时间轮像钟表的时 / 分 / 秒三个盘：每升一层，一格的跨度 $\times slots$。远期定时器先挂粗粒度的高层轮；高层指针每推进一格，就把到期那一槽的定时器 cascade（降级） 重新分发到低层——越临近触发被搬到越细的轮，最终落到底层 L0 精确触发。

3 · 对比有序表 / 最小堆，与环形结构的用途

复杂度永远是操作的属性，不是数据结构本身的。管理海量定时器，核心操作是添加、删除、推进 / 触发。下面把同一批定时器分别交给有序链表、最小堆、时间轮三种实现，实时累计它们「添加一个定时器」消耗的基本操作数（比较 + 移动 / 交换），看出时间轮的 $O(1)$ 添加优势所在。

3.1 · 同一个机件，不同用途

时间轮底层是环形缓冲区 (ring buffer)：固定数组 + 取模回绕的指针。把它当调度盘（槽位按时间寻址、装到期任务）就是时间轮；把它当滑动窗口（只留最近 N 项）就是另一大类用途。两类都建立在同一机件上。

3.2 · 环形缓冲区：内存有界、覆盖最旧

3.3 · 时间轮：按未来时刻分桶，批量处理到期