第七章第二节 时间轮与时间堆
时间轮
一层的简单时间轮如下图所示。
实线指针指向轮子上的一个槽，，它以恒定的速度顺时针转动，每隔si时间转动一槽。记时间轮的槽数为N，则指针运转一周的时间为N·si。每个槽指向一个定时器链表，每个链表上的定时器的定时时间在模N·si下一致。
因此，如果需要添加一个(相对)定时时间为ti的定时器，而此时指针指向槽cs，则该定时器将被插入槽(cs+(ti/si)) mod N对应的链表中。
时间轮采用了哈希表的思想，将定时器散列到不同的链表上，使得不同链表上的定时器数量均很少，从而定时器的插入操作更快。
可以看出，si值越小，定时精度越高；N值越大，执行效率越高。
分层时间轮
在设计时间轮时，如果遇到不同周期触发的定时事件，只使用一个时间轮的话会导致很多槽对应的定时器链表为空，从而降低时间轮的效率，更好的办法是采用分层时间轮。
分层时间轮是这样一种思想：(1)凡是任务列表中应该被执行的，全部取出来执行；(2)每个时间粒度对应一个时间轮，多个时间轮之间进行级联协作。
下面举例说明
任务一：每天2点；任务二：每周二8点；任务三：每月12日10点；各任务的时间粒度分别为天、周、月，因此设计三个时间轮——天轮、周轮、月轮；如下图所示。
初始添加任务时，将任务一添加到天轮、任务二添加到周轮、任务三添加到月轮；
那么，当周轮的指针转到2时，将任务二复制到天轮，天轮接管该任务，当指针转到8时执行(执行后要删除该任务)；当月轮的指针转到12时，将任务三复制到天轮，天轮接管该任务，当指针转到10时执行(执行后要删除该任务)；
时间堆
时间堆的思路是：将所有定时器中定时最近的定时器的超时值作为超时时间。一旦超时，必然是超时时间最小的定时器到期，从而处理该定时器的超时事件。
然后，再从剩余的定时器中找出定时最近的定时器，将其超时值作为超时时间；最小堆正是对这种定时方案的最佳工具。
最小堆是一种完全二叉树，因此可使用数组来组织；对于节点i，其左右子节点分别为2i+1、2i+2，其父节点为[(i-1)/2]。
参考链接