...

The properties of the B+ tree is summarized below -

• Keys in the system are (Secondary Key Blob) to (Primary Key Hash) mappings called

...

• BtreeEntry's

...

• Smallest non-Root node contains at least mininnerslots entries

...

• (4)
• Largest node contains at most innerslotmax entries

...

• (8)
• Nodes are allocated as RAMCloud

...

• objects 
• Keys are sorted within a

...

• nodes 
• Inner Node Keys refer to the rightmost leaf key when traversing the subtree NodeId pointer.

Variable-Sized Nodes

IndexBtree::Node implements the base class for the inner and leaf nodes of the B+ tree. The main responsibility of the base class is to abstract the complexity of storing variable-sized blobs in a RAMCloud Buffer and provide a vector-like API with set/insert/get/erase operations. The semantics of the data and how to arrange the items within the logical array are determined by the IndexBtree class.

...

The important thing to note is that the Node will ALWAYS append a copy (either virtual if it's part of the old keys or hard if it's passed in during an insert) of the keys to the end of the Buffer. This provides two useful properties. The first is that the contents of any pointer (such as a secondary key pointer) returned by the node during its lifetime will remain valid during its lifetime, even if the entry has been 'erased'. Here lifetime means from the time that the local copy is created/read from RAMCloud to the time that the local copy is garbage collected. The second useful property is this allows multiple nodes to be use the same buffer, saving on stack space. So it is also not uncommon to see a buffer layout such as

...