知识卡片
定时器用红黑树
Nginx 自己维护定时器事件,并用红黑树按超时时间组织节点,快速找到最近到期事件。它延续了 [[红黑树守住检索]] 的稳定复杂度价值。发散:时间也是一种需要索引的资源。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
原书出处
参考来源
- 位置:《深入理解Nginx:模块开发与架构解析(第2版)》第9章《事件模块》(源文件:`_epub-src/EPUB/text00078.html`)。
- 结论依据:原文明确以红黑树组织定时器;最早超时时间由树中最小键找到。
- 原始内容:定时器是通过一棵红黑树实现的。ngx_event_timer_rbtree就是所有定时器事件组成的红黑树,而ngx_event_timer_sentinel就是这棵红黑树的哨兵节点,如下所示。