💡
原文中文，约5200字，阅读约需13分钟。
📝
内容提要
Go语言中的定时器使用四叉堆存储，经历了多个版本的优化。1.9之前使用单一堆，1.10-1.13采用64个堆，1.14后每个P维护独立堆，减少竞争。四叉堆相比于二叉堆高度更低，适合大数据量场景。
🎯
关键要点
- Go语言中的定时器使用四叉堆存储，经历了多个版本的优化。
- 1.9版本之前，所有计时器由全局唯一的四叉堆维护，竞争激烈。
- 1.10-1.13版本使用64个四叉堆，减少竞争压力，但未根本解决问题。
- 1.14版本后，每个P维护独立的四叉堆，避免goroutine竞争。
- 四叉堆相比于二叉堆高度更低，适合大数据量场景。
- 四叉堆的父子节点索引计算与二叉堆不同，操作时间复杂度更优。
- Go的运行时中，四叉堆的实现位于src/runtime/time.go文件。
- timers数据结构代表Timer的集合，每个P都有一个timers实例。
- Timer结构体引用Timers，便于管理Timer的创建、删除和执行。
- 四叉堆的操作方法包括上浮和下沉，适用于优先队列。
- d-ary堆是二叉堆的泛化，允许更快的降低优先级操作。
- Go生态圈已有相应库实现d-ary堆，便于使用和测试。
❓
延伸问答
Go语言中的定时器是如何存储的？
Go语言中的定时器使用四叉堆存储，经历了多个版本的优化。
四叉堆相比于二叉堆有什么优势？
四叉堆相比于二叉堆高度更低，适合大数据量场景，操作时间复杂度更优。
Go 1.14版本对定时器的处理有什么改进？
Go 1.14版本后，每个P维护独立的四叉堆，避免了goroutine之间的竞争。
四叉堆的父子节点索引是如何计算的？
四叉堆的父节点索引为 (i - 1) // 4，子节点索引为 4 * i + 1 到 4 * i + 4。
Go生态圈中是否有实现四叉堆的库？
是的，Go生态圈中已有相应库实现d-ary堆，如ahrav/go-d-ary-heap。
四叉堆的操作方法有哪些？
四叉堆的操作方法包括上浮和下沉，适用于优先队列。
➡️
