# A Dynamic Distributed Deterministic Load-Balancer for Decentralized Hierarchical Infrastructures
## 5 The \(D^{3}\)-Tree
### The Structure  
Let \(N\) be the number of nodes present in the network and let \(n\) denote the size of data (\(N\ll n\)). The structure consists of two levels. The upper level is a Perfect Binary Tree (PBT) of height \(O(\log N)\). The leaves of this tree are _representatives_ of the _buckets_ that constitute the lower level of the \(D^{3}\)-Tree. Each bucket is a set of \(O(\log N)\) nodes which are structured as a doubly linked list.  
The number of nodes of the PBT is not connected by any means to the number of elements stored in the structure. Each node \(v\) of the \(D^{3}\)-Tree maintains an additional set of links to other nodes apart from the standard links which form the tree.  
The first four sets are inherited from the \(D^{2}\)-Tree, while the fifth set is a new one that contributes to establishing a better fault-tolerance mechanism.  
1. Links to its father and its children.
2. Links to its adjacent nodes based on an in-order traversal of the tree.
3. Links to nodes at the same level as \(v\). The links are distributed in exponential steps; the first link points to a node (if there is one) \(2^{0}\) positions to the left (right), the second \(2^{1}\) positions to the left (right), and the \(i\)-th link \(2^{i-1}\) positions to the left (right). These links constitute the _routing table_ of \(v\) and require \(O(\log N)\) space per node.
4. Links to leftmost and rightmost leaf of its subtree. These links accelerate the search process and contribute to the structure's fault tolerance when a considerable number of nodes fail.
5. For leaf nodes only, links to the buckets of the nodes in their routing tables. The first link points to a bucket \(2^{0}\) positions left (right), the second \(2^{1}\) positions to the left (right) and the \(i\)-th link \(2^{i-1}\) positions to the left (right). These links require \(O(\log N)\) space per node and keep the structure fault-tolerant since each bucket has multiple links to the PBT.  
The next lemma captures some important properties of the routing tables.  
**Lemma 1**.: _(i) If a node \(v\) contains a link to node \(u\) in its routing table, then the parent of \(v\) also contains a link to the parent of \(u\), unless \(u\) and \(v\) have the same father. (ii) If a node \(v\) contains a link to node \(u\) in its routing table, then the left (right) sibling of \(v\) also contains a link to the left (right) sibling of \(u\), unless there are no such nodes. (iii) Every non-leaf node has two adjacent nodes in the in-order traversal, which are leaves._  
Regarding the index structure of the \(D^{3}\)-Tree, the range of all values stored in it is partitioned into sub-ranges each one of which is assigned to a node of the overlay.  
An internal node \(v\) with range \([x_{v},x_{v}^{\prime}]\) may have a left child \(u\) and a right child \(w\) with ranges \([x_{u},x_{u}^{\prime}]\) and \([x_{w},x_{w}^{\prime}]\) respectively such that \(x_{u}<x_{u}^{\prime}<x_{v}<x_{v}^{\prime}<x_{w}<x_{w}^{\prime}\). Ranges are dynamic in the sense that they depend on the values maintained by the node.