B-tree

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 for nodes with more than two children.^[2]

By allowing more children under one node than a regular self-balancing binary search tree, the B-tree reduces the height of the tree, hence put 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 its use in databases and file systems. This remains a major benefit when the tree is stored in memory, as modern computer systems rely on CPU caches heavily: compared to reading from the cache, reading from memory in the event of a cache miss also takes a long time.^[3][4]