I have seen people use OPTICS on millions of points, but that won't create "spherical" clusters.

Probably something extremely simple like LEADER is what you want.

K-means with large k is pretty problematic. First of all, the runtime scales badly with k, and secondly on noisy data you will have clusters with just one outlier quite often.

Mini-batch k-means won't help you much either. The batch sizes must be much larger than k. Plus, it never converges. So you'd need to run it as long as you can afford and then hope the result is good enough. That is okay for visual-bag-of-words but not for many other cases.

I have seen people use OPTICS on millions of points, but that won't create "spherical" clusters.

Probably something extremely simple like LEADER is what you want.

K-means with large k is pretty problematic. First of all, the runtime scales badly with k, and secondly on noisy data you will have clusters with just one outlier quite often.

For just 3 dimensional data, k-d-trees are definitely worth a try. In particular for large k. However these methods are not easy to implement. You'd need a nearest-neighbor join of two trees (one with the data, one with the centers). That requires some pretty complex data management that is not fun to do, and I don't know any k-d-tree library that would provide this functionality.

Mini-batch k-means won't help you much either. The batch sizes must be much larger than k. Plus, it never converges. So you'd need to run it as long as you can afford and then hope the result is good enough. That is okay for visual-bag-of-words but not for many other cases.