We study clustering in dynamic graphs, where edges (and possibly vertices) arrive over time and the underlying cluster structure evolves gradually. We design a hierarchical data structure that maintains this cluster structure with $O(d)$ amortised update time and $\widetilde{O}(n_T^{1/d})$ amortised query time, for any large constant $d$, where $n_T$ is the number of vertices at time $T$. This improves on the previous state of the art (Laenen and Sun, ICML 2024), which has $O(1)$ update time but $O(n_T/\log n_T)$ amortised query time. Experiments on synthetic and real-world datasets confirm the improvement.