B-tree

B-tree
TypeTree (data structure)
Invented1970[1]
Invented byRudolf Bayer, Edward M. McCreight
Time complexity in big O notation
Operation Average Worst case
Search O(log n) O(log n)
Insert O(log n) O(log n)
Delete O(log n) O(log n)
Space complexity
Space O(n) O(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 for nodes with more than two children.[2] Unlike other self-balancing binary search trees, the B-tree is well suited for storage systems that read and write relatively large blocks of data, such as databases and file systems.

  1. ^ Bayer, R.; McCreight, E. (July 1970). "Organization and maintenance of large ordered indices" (PDF). Proceedings of the 1970 ACM SIGFIDET (Now SIGMOD) Workshop on Data Description, Access and Control - SIGFIDET '70. Boeing Scientific Research Laboratories. p. 107. doi:10.1145/1734663.1734671. S2CID 26930249.
  2. ^ Comer 1979.