Our aim is to develop dynamic data structures that support \(k\)-nearest neighbors (\(k\)-NN) queries for a set of \(n\) point sites in \(O(f(n) + k)\) time, where \(f(n)\) is some polylogarithmic function of \(n\). The key component is a general query algorithm that allows us to find the \(k\)-NN spread over \(t\) substructures simultaneously, thus reducing a \(O(tk)\) term in the query time to \(O(k)\). Combining this technique with the logarithmic method allows us to turn any static \(k\)-NN data structure into a data structure supporting both efficient insertions and queries. For the fully dynamic case, this technique allows us to recover the deterministic, worst-case, \(O(\log^2n/\log\log n +k)\) query time for the Euclidean distance claimed before, while preserving the polylogarithmic update times. We adapt this data structure to also support fully dynamic geodesic \(k\)-NN queries among a set of sites in a simple polygon. For this purpose, we design a shallow cutting based, deletion-only \(k\)-NN data structure. More generally, we obtain a dynamic \(k\)-NN data structure for any type of distance functions for which we can build vertical shallow-cuttings. We apply all of our methods in the plane for the Euclidean distance, the geodesic distance, and general, constant complexity, algebraic distance functions.