一.理论基础前置复习什么是完全二叉树除了最后一层外其他层都达到最大节点数且最后一层节点都靠左排列1.小顶堆小顶堆(Min-Heap)是一种特殊的完全二叉树结构,核心原则只有一条:堆序性质:任意一个父节点的值,都小于或等于它的子节点的值。也就是说,根节点永远是整棵树里最小的元素。关键特征1. 完全二叉树除了最后一层,其他层都是满的,最后一层的节点从左往右依次填充,不能有空隙。这个性质保证了堆可以用数组来紧凑存储,不需要用链表/指针存左右子节点。2. 数组存储的下标关系如果用数组存储,下标从 0 开始,对于下标为i的节点:父节点下标:(i - 1) / 2左子节点下标:2i 1右子节点下标:2i 23. 只保证父子关系,不保证兄弟节点大小左子节点和右子节点之间没有大小约束,只要求父节点 ≤ 两个子节点即可。所以小顶堆不是完全有序的,只有根节点能保证是最小值,其他位置的相对顺序是不确定的。两个核心操作插入(Push)—— 上浮(Sift Up / Bubble Up)把新元素放到数组末尾(树的最后一个位置)和父节点比较,如果比父节点小,就交换位置重复这个过程,一路往上冒泡,直到满足堆序性质或到达根节点删除堆顶(Pop)—— 下沉(Sift Down / Bubble Down)把根节点(最小值)取出,同时把数组最后一个元素挪到根节点位置从根开始,和左右子节点中较小的那个比较,如果比子节点大就交换重复这个过程,一路往下沉,直到满足堆序性质或到达叶子节点2.时间轮算法1️⃣ 数组/链表 while-true-sleep- 原理:用一个数组(或链表数组),每个下标代表一个时间刻度(比如每秒一个格子),格子里挂一个链表存放这个时刻要执行的任务。一个死循环线程不断遍历数组,走到哪个下标,就把那个链表里的任务取出来执行。特点:实现最简单,直观缺点:如果时间跨度很大(比如要支持1年后执行),数组就要开得很大,内存浪费严重- 性能每次 tick 的成本:O(1) 定位到当前格子,但格子里如果堆积了很多任务,遍历这个链表是 O(m)(m 该格任务数)主要损耗:死循环空转:线程一直while(true) { sleep(); check(); },即使没任务也在消耗 CPU 做无意义的唤醒检查内存浪费:要支持多长的延迟,数组就要开多大。比如要支持1小时后执行,按秒精度就要开 3600 个格子,大部分格子常年是空的2️⃣ round 型时间轮- 原理:数组大小固定(比如只做 60 格,代表 60 秒一圈),但每个任务额外记一个round值,表示还要转几圈才轮到它。指针走到对应格子时,先把 round 减一,减到 0 才真正取出执行。特点:✅ 用固定大小的数组就能支持任意长的延迟时间(不用开一个超大数组)❌遍历到某个格子时,要检查这个格子链表里所有任务的 round 值,任务多的时候效率较低,而且转一圈的时间粒度受限(比如 60 秒一圈,精度就只能到秒级)-性能每次 tick 的成本:仍然要遍历当前格子链表里所有任务,逐个检查 round 是否为 0——这是它最大的性能瓶颈主要损耗:如果一个格子里同时挂了 1000 个不同 round 值的任务(比如有的转1圈就到,有的要转100圈),每次指针扫过这个格子,都要把这 1000 个任务全部检查一遍 round 值,即使其中 999 个这一轮根本不需要处理相当于用固定内存换来了重复扫描的 CPU 开销,典型的空间换时间失败案例——省了内存,但没省计算3️⃣ 分层时间轮-原理:不只一个轮子,而是多个不同粒度的轮子叠在一起,比如:秒轮:管理多少秒后执行天轮:记录几点执行月轮:记录几号执行月轮转到某一格,就把里面的任务降级丢进天轮;天轮转到某一格,再看是否到执行时间。类似钟表的时针、分针、秒针分层联动。特点:✅ 效率最高,不需要遍历大量任务,每层只处理少量的降级操作✅ 能优雅支持几号几点执行这种长跨度、高精度的场景❌ 实现复杂度最高-性能每次 tick 的成本:均摊下来接近 O(1)为什么损耗更低:秒轮/天轮每次只处理当前这一格的任务,不需要检查 round(因为压根没有 round 这个概念)只有当某一层转完一圈时,才会触发一次降级操作(把上层的一批任务搬到下层),这个操作不是每个 tick 都发生,而是被摊薄到很多次 tick 里类似时针不动,分针每转一圈才拨一下时针——大部分时候只有最细粒度的那个轮子在真正工作,粗粒度的轮子几乎不动一张表总结损耗来源方案CPU 损耗来源内存损耗适用规模数组线性扫描空转 大数组全遍历高(数组要开满时间跨度)任务量小、demoround 型同格任务逐个判断 round,任务堆积时严重中(环形数组,大小固定)中等任务量分层时间轮接近均摊 O(1),仅降级时有开销低(每层数组都很小)海量任务,如 Kafka/Netty/RocketMQ
一.理论基础前置复习什么是完全二叉树除了最后一层外其他层都达到最大节点数且最后一层节点都靠左排列1.小顶堆小顶堆(Min-Heap)是一种特殊的完全二叉树结构,核心原则只有一条:堆序性质:任意一个父节点的值,都小于或等于它的子节点的值。也就是说,根节点永远是整棵树里最小的元素。关键特征1. 完全二叉树除了最后一层,其他层都是满的,最后一层的节点从左往右依次填充,不能有空隙。这个性质保证了堆可以用数组来紧凑存储,不需要用链表/指针存左右子节点。2. 数组存储的下标关系如果用数组存储,下标从 0 开始,对于下标为i的节点:父节点下标:(i - 1) / 2左子节点下标:2i 1右子节点下标:2i 23. 只保证父子关系,不保证兄弟节点大小左子节点和右子节点之间没有大小约束,只要求父节点 ≤ 两个子节点即可。所以小顶堆不是完全有序的,只有根节点能保证是最小值,其他位置的相对顺序是不确定的。两个核心操作插入(Push)—— 上浮(Sift Up / Bubble Up)把新元素放到数组末尾(树的最后一个位置)和父节点比较,如果比父节点小,就交换位置重复这个过程,一路往上冒泡,直到满足堆序性质或到达根节点删除堆顶(Pop)—— 下沉(Sift Down / Bubble Down)把根节点(最小值)取出,同时把数组最后一个元素挪到根节点位置从根开始,和左右子节点中较小的那个比较,如果比子节点大就交换重复这个过程,一路往下沉,直到满足堆序性质或到达叶子节点2.时间轮算法1️⃣ 数组/链表 while-true-sleep- 原理:用一个数组(或链表数组),每个下标代表一个时间刻度(比如每秒一个格子),格子里挂一个链表存放这个时刻要执行的任务。一个死循环线程不断遍历数组,走到哪个下标,就把那个链表里的任务取出来执行。特点:实现最简单,直观缺点:如果时间跨度很大(比如要支持1年后执行),数组就要开得很大,内存浪费严重- 性能每次 tick 的成本:O(1) 定位到当前格子,但格子里如果堆积了很多任务,遍历这个链表是 O(m)(m 该格任务数)主要损耗:死循环空转:线程一直while(true) { sleep(); check(); },即使没任务也在消耗 CPU 做无意义的唤醒检查内存浪费:要支持多长的延迟,数组就要开多大。比如要支持1小时后执行,按秒精度就要开 3600 个格子,大部分格子常年是空的2️⃣ round 型时间轮- 原理:数组大小固定(比如只做 60 格,代表 60 秒一圈),但每个任务额外记一个round值,表示还要转几圈才轮到它。指针走到对应格子时,先把 round 减一,减到 0 才真正取出执行。特点:✅ 用固定大小的数组就能支持任意长的延迟时间(不用开一个超大数组)❌遍历到某个格子时,要检查这个格子链表里所有任务的 round 值,任务多的时候效率较低,而且转一圈的时间粒度受限(比如 60 秒一圈,精度就只能到秒级)-性能每次 tick 的成本:仍然要遍历当前格子链表里所有任务,逐个检查 round 是否为 0——这是它最大的性能瓶颈主要损耗:如果一个格子里同时挂了 1000 个不同 round 值的任务(比如有的转1圈就到,有的要转100圈),每次指针扫过这个格子,都要把这 1000 个任务全部检查一遍 round 值,即使其中 999 个这一轮根本不需要处理相当于用固定内存换来了重复扫描的 CPU 开销,典型的空间换时间失败案例——省了内存,但没省计算3️⃣ 分层时间轮-原理:不只一个轮子,而是多个不同粒度的轮子叠在一起,比如:秒轮:管理多少秒后执行天轮:记录几点执行月轮:记录几号执行月轮转到某一格,就把里面的任务降级丢进天轮;天轮转到某一格,再看是否到执行时间。类似钟表的时针、分针、秒针分层联动。特点:✅ 效率最高,不需要遍历大量任务,每层只处理少量的降级操作✅ 能优雅支持几号几点执行这种长跨度、高精度的场景❌ 实现复杂度最高-性能每次 tick 的成本:均摊下来接近 O(1)为什么损耗更低:秒轮/天轮每次只处理当前这一格的任务,不需要检查 round(因为压根没有 round 这个概念)只有当某一层转完一圈时,才会触发一次降级操作(把上层的一批任务搬到下层),这个操作不是每个 tick 都发生,而是被摊薄到很多次 tick 里类似时针不动,分针每转一圈才拨一下时针——大部分时候只有最细粒度的那个轮子在真正工作,粗粒度的轮子几乎不动一张表总结损耗来源方案CPU 损耗来源内存损耗适用规模数组线性扫描空转 大数组全遍历高(数组要开满时间跨度)任务量小、demoround 型同格任务逐个判断 round,任务堆积时严重中(环形数组,大小固定)中等任务量分层时间轮接近均摊 O(1),仅降级时有开销低(每层数组都很小)海量任务,如 Kafka/Netty/RocketMQ
