I'm now very curious on this. My gut was more that it is 2^(number of dimensions) that is important here. As such, for a single dimensional storage of data, standard binary tree. Add in another dimension, but still want to halve the search space with every comparison, add another branch factor to the tree.

That said, this implies that for 3d space, you would want 8 way trees? But, I don't think I've ever heard of that being done/used.