0, 0.25, 0.5, 0.75
[0.16, 0.67, 0.66, 0.03, 0.84, 0.39, 0.7, 0.25, 0.44, 0.36]
0: [0.03] 0.25: [0.36, 0.25] 0.5: [0.39, 0.44] 0.75: [0.66, 0.67, 0.7, 0.84]
Values remapped: [0.66, 0.67]
N - 0.1, 0.94, 0.98 E - 0.2, 0.28 S - 0.45, 0.55 W - 0.68, 0.79, 0.85
N - 0.1, 0.94, 0.98 E - 0.2, 0.28 M - 0.45 - The key that gets remapped! S - 0.55 W - 0.68, 0.79, 0.85
1. 0, 1/4, 1/2, 3/4
2. If a new node is added, we expect k/(n+1) will need to change
So, say the 10 keys are 0.1, 0.2, 0.3, 0.4, 0.8, 0.7, 0.3, 0.2, 0.9, 0.6. The stored keys will look as follows:
0: {0.1, 0.9} 1/4: {0.2, 0.3, 0.2} 1/2: {0.4, 0.6} 3/4: {0.8, 0.7}
Say another new node location, 0.29 is added.
Our new server layout will look like this:
0: {0.1, 0.9} 1/4: {0.2, 0.2} 0.29: {0.3} 1/2: {0.4, 0.6} 3/4: {0.8, 0.7}(Edited: 2020-09-23)
1) Locations: 0.0, 0.25. 0.50, 0.75 Random numbers are 0.13 0.28 0.41 0.94 0.85 0.30 0.46 0.43 0.73 0.04 2) Keys stored 0.0 are {0.04,0.94} Keys stored 0.25 are {0.28,0.13,0.30} Keys stored 0.50 are {0.43,0.46,0.41} Keys stored 0.75 are {0.85,0.73} 3) Random Node location Generated : 0.80 Keys remapped : 0.85(Edited: 2020-09-23)
1. N:0 E:0.25 S:0.5 W:0.75
2. N: 0.096, 0.08, 0.03 E: 0.34, 0.18 S: 0.48, 0.52 W: 0.81, 0.83, 0.76 3. New location SW: 0.53 0.52 is remapped to SW
4 nodes -> 0, 0.25, 0.5, 0.75
node-Key -> 0: 0.03 distribution 0.25: 0.30, 0.20, 0.21 0.50: 0.62, 0.52, 0.39 0.75: 0.63, 0.73, 0.81
New Node -> 0.16
Keys remapped -> 0.16: 0.20(Edited: 2020-09-23)
//Place four nodes at the N,S,E,W points of a circle. 0.0 0.25 0.50 0.75 //generate random 10 keys 0.1 0.2 0.3 0.4 0.5 0.55 0.6 0.7 0.8 0.9 //put the keys into the circle 0.0 => [0.1,0.9] 0.25 => [0.2,0.3] 0.50 => [0.4,0.5,0.55,0.6] 0.75 => [0.7,0.8]
//Pick a random new node location and add it to the ring. 0.0 => [0.1,0.9] 0.25 => [0.2,0.3] 0.50 => [0.4,0.5] 0.60 => [0.55,0.6] 0.75 => [0.7,0.8]
//new keys remapped [0.55,0.6] (k/n+1) = 10/(4+1) = 2 = count([0.55,0.6]) < 4 = (k-n)
conclusion: remapped keys much smaller than (k-n)(Edited: 2020-09-23)
Random keys -> 0.1, 0.15, 0.30, 0.45, 0.55, 0.65, 0.70, 0.80, 0.94, 0.99 0 => 0.1, 0.94, 0.99 0.25 => 0.15, 0.30 0.50 => 0.45, 0.55 0.75 => 0.65, 0.70, 0.80
a new node is added at 0.90 0 => 0.1, 0.99 0.25 => 0.15, 0.30 0.50 => 0.45, 0.55 0.75 => 0.65, 0.70, 0.80 0.90 => 0.94
0.94 was remapped from 0 to 0.90
0, 0.25, 0.5, 0.75
Generating 10 random numbers (using online random numbers generator): 0.23 0.87 0.50 0.49 0.85 0.72 0.53 0.66 0.04 0.05
Mapping [0] => 0.04, 0.05 [0.25] => 0.23 [0.5] => 0.50, 0.49, 0.53 [0.75] => 0.87, 0.85, 0.72, 0.66
New node at 0.86 0.87 and 0.85 will be remapped(Edited: 2020-09-26)