Search tree

Various search-tree data structures exist, several of which also allow efficient insertion and deletion of elements, which operations then have to maintain tree balance.

A Binary Search Tree is a node-based data structure where each node contains a key and two subtrees, the left and right.

B-trees are generalizations of binary search trees in that they can have a variable number of subtrees at each node.

While child-nodes have a pre-defined range, they will not necessarily be filled with data, meaning B-trees can potentially waste some space.

The advantage is that B-trees do not need to be re-balanced as frequently as other self-balancing trees.

Due to the variable range of their node length, B-trees are optimized for systems that read large blocks of data, they are also commonly used in databases.