I find a python kdtree here : http://code.google.com/p/python-kdtree/
It’s very powerfull , kdtree generation take 13sec for 250 000particles but requesting to find the nearest neighbours particles of a particle or of a coordinate take 0.000002sec !And I can do a search for the 2 … 3 … 500 nearest neighbours and the time to find it is approximatly the same !!! The only problem is I cannot update particles position without have to rebuild the entire tree. I need to find a script with implementation of adding particles or changing particles corrdinate with self-balancing kd-tree. And just by reading wikipedia articles to see it’s seem to not be easy : http://en.wikipedia.org/wiki/K-d_tree#Adding_elements
My second option is octree. Octree seem to be easy to build and change I think. I need to find a good integration of it before to thinking about create my own. I’m not sure how octree exactly works like did a request like nearest neighbours.
My last option is to code my one tree. It’s I tree I have imaginated and it’s work. But it’s for sure is not the most efficient. Why ? because it’s soo simple than it’s impossible nobody thinking about it before me. I talk with my brother( I real coder/developper , ex-worker at Ubisoft and currently return at university to improve is skill ) yesterday and he think my idea is not bad but have probably limitation when time to come implementing other collision gemetry objects in the system than “same size” self-colliding particles.
My best guest for performance is Kd-Tree. Apparently XSI-ICE use it. I just need to find a self-balanced one 
. A lot of google search and reading to do !