定时器管理:nginx的红黑树和libevent的堆

时间:2022-03-25 00:13:42

libevent 发生超时后,

while循环一次从堆顶del timer——直到最新调整的最小堆顶不是超时事件为止,(实际是del event),但是会稍后把这个timeout的 event放到active 任务list里,

等待处理,event标记为timeout,等处理actvie队列时再由应用层callback函数决定怎么处理标记为timeout的事件。

 

nginx处理超时时,直接删除红黑树中( event结构体里的 )rb node成员,同时调用应用层早已通过add timer注册好的超时handler函数。之所以没有用堆,

因为每次直接从内部删除节点,而不是堆顶部。

 

关键点,采用堆,删除时间是O(1),但是要调整堆,logn。插入时间基本是lgn。

采用红黑树,删除节点是3次旋转,但是,找到最小节点要logn。插入时间基本是lgn。

 

总体看,都差不多。

堆排序和红黑树性能比较 :http://blog.sina.com.cn/s/blog_56e6a0750101b0fo.html