B-Tree Data Structure

Explanation

B-Tree is self-balancing tree data structure that maintains sorted data and allows function of search, insert, and delete. B-tree can have multiple key per node, which make it different from other binary search tree.

Key Properties

• All leaf nodes of a B tree are at the same level, i.e. they have the same depth
• The keys of each node of a B tree (in case of multiple keys), should be stored in the ascending order.
• In a B tree, all non-leaf nodes (except root node) should have at least m/2 children.
• All nodes (except root node) should have at least m/2 - 1 keys.
• If the root node is a leaf node (only node in the tree), then it will have no children and will have at least one key. If the root node is a non-leaf node, then it will have at least 2 children and at least one key.
• A non-leaf node with n-1 key values should have n non NULL children.