Go中秘而不宣的数据结构: 四叉堆，不是普通的二叉堆
原文中文，约5200字，阅读约需13分钟。
📝
内容提要
Go语言中的定时器使用四叉堆存储，经历了多个版本的优化。1.9之前使用单一堆，1.10-1.13采用64个堆，1.14后每个P维护独立堆，减少竞争。四叉堆相比于二叉堆高度更低，适合大数据量场景。
🔎
延伸解读
四叉堆的优势
四叉堆相比于传统的二叉堆，具有更低的高度，这使得在处理大数据量时，操作效率更高。特别是在需要频繁进行优先级调整的场景中，四叉堆的性能优势更加明显。
Go语言定时器的演变
Go语言中的定时器经历了多个版本的优化，从最初的全局堆到后来的每个P维护独立堆，这一变化显著减少了goroutine之间的竞争，提升了系统的整体性能。开发者在设计时需关注这些演变，以便更好地理解定时器的行为。
d-ary堆的应用
d-ary堆作为四叉堆的泛化，提供了更快的降低优先级操作，适合需要频繁调整优先级的应用场景。Go生态圈中已有相关库实现，开发者可以根据需求选择合适的数据结构进行优化。
❓
Q&A
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。
四叉堆的操作方法有哪些？
四叉堆的操作方法包括上浮和下沉，适用于优先队列。
🏷️
