Clojure Data Structures and Algorithms Cookbook

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 ...