...
We need to allocate to b+ tree nodes in the master server. B+ tree is represented by B+ tree nodes linked with pointers. A general structure of a B+ tree node is as follows:
struct node
node {
int key;
int primary_keukey; // only for leaf nodes
node* left_child;
node* right_child;
}
...
2) Indirection: Another approach is to create a level of indirection between the parent's child pointers and child nodes i.e instead of accessing child nodes in single step through pointers, we will go through a hash table to find the corresponding child location. This leads to easier cleaning mechanism where we need to only update the hash table corresponding to a node, when a node is moved. We can use the existing hash table in the master server to store the index node information. The goal is to create a pseudo-table 'Index Table' which will not be accessible to the client sides, but will be handled by the sever. The table will be handled by RamCloud memory management like an usual table, which is responsible for cleaning and recovery.The trade-off is the general tree traversal operations will now be expensive, since each child access will have to go through the hash table. The computations will increase by atmost 2x (1us -> 2us). The new structure of a B+ tree node will be
struct node
node {
int key;
int primary_key; // only for leaf node
int left_child_key; // index table key
int right_child_key; // index table key
}
...