Designing an efficient key-value store using B-trees

B-trees are commonly used in databases and filesystems, thanks to their inherent capability of manipulating large blocks of data. In contrast to a classical binary search tree, a B-tree is a tree data structure whose nodes can refer to more than two children nodes, and as such, traversing it permits us to access efficient block-oriented data. Besides, B-trees are self-balanced and designed in such a way that they grow very gracefully.

B-tree nodes are commonly called as keys. This is to refer to the fact that they hold values that act as separators. Indeed, for each node holding one particular key value, we find to its left, children that hold the keys of inferior value and to its right, a set of children with superior values. Although the values that B-tree nodes hold are labeled as keys, they still are values and can, besides acting as separators, represent actual data.(These keys are not to be confused with the keys of the key-value...