Introducing sibling meshes
Set of meta-tree structures that assist node-insertion and fault-recovery
- Every node keeps n ptrs to “similar” nodes w.r.t. 1 property
- Example: all nodes ending in 629 belong to a single mesh
- Each node belongs to Log(N) meshes, where N = number of unique IDs in namespace
- Meshes decrease in size as granularity becomes more fine
Plaxton Trees / Ground Level
- Each mesh represents a single hop on the route to a given root.
- Sibling nodes maintain pointers to each other.
- (optional) Each referrer has pointers to the desired node’s siblings