Closest k points - performance on large lists
I think what you are trying to do is a kind of SPATIAL JOIN. A similar question has been answered here, albeit with a fixed size radius for returned points instead of asking for $k$ closest points. 

I would suggest using a spatial index $L$. Then you can perform $k$-nearest neighbor queries on the index for each point. The complexity would be about or $O(|Q| * k * log |L|)$.
I did some performance test of different spatial indexes here (Figure 28) with 2D and 3D datasets, you should be able to get around 100,000 $k$-nearest neighbor searches per second (on an index with 10,000,000 points). Some of these spatial indexes have updates rates of up to 1,000,000 updates per second, see Figure 40 in the same document. Especially quadtrees and the PH-Tree have high updates rates.

Not sure that it matters, but the PH-Tree uses internally z-curves (Morten order), which means that the ordering of elements uses z-order and is independent of insertion/deletion order. However, also note that the PH-Tree does not support duplicates, there can be only one point at any given coordinate.