Actually, on further thought, this seems like a particularly rare
situation. Like, in a linear key space, given a search key S and
another key A, there's only one other key that's equidistant from S
with A.
We have a 160 bit key space (right? something like that), which gives
about 10^48 possible values. The chance that there are two equidistant
keys from a given search key in a node with 10^3 or 10^4 stored keys
is (I think) somewhere around 1 - ((1 - 1/10^48)^(10^3)). Actually,
it's:
N
1 - product (1 - n/S)
n = 1
(N = number of chances to hit, S = size of space -- this is
essentially the birthday problem)
Which is pretty damn close to 10^-45. Which is so damn unlikely it
makes my head spin -- I think there's a much better chance of having
your node hit by a meteor made of frozen airplane toilet waste than
