B-tree

B-tree
Type	tree
Invented	1971
Invented by	Rudolf Bayer, Edward M. McCreight
Time complexity in big O notation
Algorithm Average Worst Case Space O(n) O(n) Search O(log n) O(log n) Insert O(log n) O(log n) Delete O(log n) O(log n)

Algorithm		Average	Worst Case
Space		O(n)	O(n)
Search		O(log n)	O(log n)
Insert		O(log n)	O(log n)
Delete		O(log n)	O(log n)

In computer science, a B-tree is a self-balancing tree data structure that keeps data sorted and allows searches, sequential access, insertions, and deletions in logarithmic time. The B-tree is a generalization of a binary search tree in that a node can have more than two children (Comer 1979, p. 123). Unlike self-balancing binary search trees, the B-tree is optimized for systems that read and write large blocks of data. B-trees are a good example of a data structure for external memory. It is commonly used in databases and filesystems.

In B-trees, internal (non-leaf) nodes can have a variable number of child nodes within some pre-defined range. When data is inserted or removed from a node, its number of child nodes changes. In order to maintain the pre-defined range, internal nodes may be joined or split. Because a range of child nodes is permitted, B-trees do not need re-balancing as frequently as other self-balancing search trees, but may waste some space, since nodes are not entirely full. The lower and upper bounds on the number of child nodes are typically fixed for a particular implementation. For example, in a 2-3 B-tree (often simply referred to as a 2-3 tree), each internal node may have only 2 or 3 child nodes.

Each internal node of a B-tree will contain a number of keys. The keys act as separation values which divide its subtrees. For example, if an internal node has 3 child nodes (or subtrees) then it must have 2 keys: a₁ and a₂. All values in the leftmost subtree will be less than a₁, all values in the middle subtree will be between a₁ and a₂, and all values in the rightmost subtree will be greater than a₂.

Usually, the number of keys is chosen to vary between ${\displaystyle d}$ and ${\displaystyle 2d}$, where ${\displaystyle d}$ is the minimum number of keys, and ${\displaystyle d+1}$ is the minimum degree or branching factor of the tree. In practice, the keys take up the most space in a node. The factor of 2 will guarantee that nodes can be split or combined. If an internal node has ${\displaystyle 2d}$ keys, then adding a key to that node can be accomplished by splitting the hypothetical ${\displaystyle 2d+1}$ key node into two ${\displaystyle d}$ key nodes and moving the key that would have been in the middle to the parent node. Each split node has the required minimum number of keys. Similarly, if an internal node and its neighbor each have ${\displaystyle d}$ keys, then a key may be deleted from the internal node by combining it with its neighbor. Deleting the key would make the internal node have ${\displaystyle d-1}$ keys; joining the neighbor would add ${\displaystyle d}$ keys plus one more key brought down from the neighbor's parent. The result is an entirely full node of ${\displaystyle 2d}$ keys.

...
Wikipedia