B-tree

http://en.wikipedia.org/wiki/B-tree

Not to be confused with Binary tree.

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

Contents

[hide]

• 1 Overview
  • 1.1 Variants
  • 1.2 Etymology unknown
• 2 The database problem
  • 2.1 Time to search a sorted file
  • 2.2 An index speeds the search
  • 2.3 Insertions and deletions cause trouble
  • 2.4 The B-tree uses all those ideas
• 3 Technical description
  • 3.1 Terminology
  • 3.2 Definition
• 4 Best case and worst case heights
• 5 Algorithms
  • 5.1 Search
  • 5.2 Insertion
  • 5.3 Deletion
    • 5.3.1 Deletion from a leaf node
    • 5.3.2 Deletion from an internal node
    • 5.3.3 Rebalancing after deletion
  • 5.4 Initial construction
• 6 B-trees in filesystems
• 7 Variations
  • 7.1 Access concurrency
• 8 See also
• 9 Notes
• 10 References
  • 10.1 Original papers
• 11 External links

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

A B-tree of order 2 (Bayer & McCreight 1972) or order 5 (Knuth 1997).