B-tree

B-tree
Type	Tree (data structure)
Invented	1970
Invented by	Rudolf Bayer, Edward M. McCreight
Complexities in big O notation
Space complexity Space ${\displaystyle O(n)}$ Time complexity Function Amortized Worst case Search ${\displaystyle O(\log n)}$ ${\displaystyle O(\log n)}$ Insert ${\displaystyle O(\log n)}$ ${\displaystyle O(\log n)}$ Delete ${\displaystyle O(\log n)}$ ${\displaystyle O(\log n)}$

In computer science, a B-tree is a self-balancing tree data structure that maintains sorted data and allows searches, sequential access, insertions, and deletions in logarithmic time. The B-tree generalizes the binary search tree, allowing nodes to have more than two children.

By allowing more children under one node than a regular self-balancing binary search tree, the B-tree reduces the height of the tree and puts the data in fewer separate blocks. This is especially important for trees stored in secondary storage (e.g., disk drives), as these systems have relatively high latency and work with relatively large blocks of data, hence the B-tree's use in databases and file systems. This remains a major advantage when the tree is stored in memory, as modern computer systems rely heavily on CPU caches. Compared to reading from the cache, reading from memory after a cache miss costs significant time.