If you Google search the space complextiy of KNN, virtually all answers are saying that it costs $O(dN)$, where $d$ is the dimension of our data and $N$ is the number of our data.
But why?
I understand that we need to store $d \times N$ numbers, so that's where the $dN$ comes in.
But aren't we storing a lot more, for example, the $k$ $d$-dimensional nearest neighbors?
So the space complexity should be $O(dN + dk)$.
Is this correct? Are there any other "spaces" I am missing?
It depends on the implementation. Naively, the $k$NN algorithm just searches in prediction time through the training data to find the $k$ nearest neighbors, so you only need to store the train dataset. You could speed up the search by memoizing the nearest neighbors, then the size grows with the size of the memory. If you found the neighbors in advance for all the training cases, then you are correct but this does not guarantee that all the test cases will be included in this set (so it's disputable how much value would it have). There are also approximate nearest neighbors algorithms with different time and storage requirements. So the basic case is $O(Nd)$, and the other cases depend on implementation details.
