So I was recently playing with the new job system in Unity 2018.1.0b8 and managed to jobify this kdtree. I placed the project with examples on GitHub:
https://github.com/chanfort/kdtree-jobified-unity
In order to jobify, I converted kdtree class into struct and also set 4 arrays to store kdtree data instead of recursive tree of objects. The content includes the old kdtree class, the new kdtree struct and the example in KDtest.cs .
The example test is set to compare performance between the old kdtree and the new jobified one. The test runs with 5000 points kdtree build at startup. 5000 other query points are searching for their nearest neighbours in the kdtree on every update.
The options changes by pressing A (build in arrays and original kdtree class), B (new kdtree struct and native arrays) and C (jobified (multithreaded) kdtree with IJobParallelFor usage over neighbour search) keys in the keyboard.
The performance is as follows:
Editor: A - 28 FPS, B - 12 FPS, C - 23 FPS
When build: A - 64 FPS, B - 58 FPS, C - 125 FPS
So at the moment, improvements are only visible when running the build project (not running in Editor).
I will update these numbers when Unity will release Burst compiler ( likely 2018.2 ). So stay tuned - looks very promising.