[jws]

I wonder: Why primes? Why not just crack off 4 bits at each level?

[doomrobo]

I think if you do it this way you can extend the tree without recalculating all the entries. I can just add the next prime to the list of primes.

[ball_of_lint]

In that case you could just use a binary tree taking from lsb to msb, and then expand down a level only on collisions.

The reason for primes is that it is more likely to distinguish between numbers earlier in the tree so that it doesn't get as deep as fast. Where a binary tree couldn't tell 0 and 256 apart until the 8th level, this could tell them apart at the second level: 0 mod 3 = 0, 256 mod 3 = 1

[rhizome]

you mean like a radix tree?