B Tree

• In a binary search tree, AVL Tree, Red-Black tree etc., every node can have only one value (key) and maximum of two children but there is another type of search tree called B-Tree in which a node can store more than one value (key) and it can have more than two children.

• B-Tree can be defined as a self-balanced search tree with multiple keys in every node and more than two children for every node.Here, number of keys in a node and number of children for a node is depend on the order of the B-Tree. Every B-Tree has order.

B-Tree of Order m has the following properties...

• Property #1 - All the leaf nodes must be at same level.
• Property #2 - All nodes except root must have at least [m/2]-1 keys and maximum of m-1 keys.
• Property #3 - All non leaf nodes except root (i.e. all internal nodes) must have at least m/2 children.
• Property #4 - If the root node is a non leaf node, then it must have at least 2 children.
• Property #5 - A non leaf node with n-1 keys must have n number of children.

• Property #6 - All the key values within a node must be in Ascending Order.

• For example, B-Tree of Order 4 contains maximum 3 key values in a node and maximum 4 children for a node.

• Example

  

B+ Tree

• A B+ tree is a data structure often used in the implementation of database indexes.

• Each node of the tree contains an ordered list of keys and pointers to lower level nodes in the tree. These pointers can be thought of as being between each of the keys.

• To search for or insert an element into the tree, one loads up the root node, finds the adjacent keys that the searched-for value is between, and follows the corresponding pointer to the next node in the tree. Recursing eventually leads to the desired value or the conclusion that the value is not present..

• Following are the properties of B+ trees

  a. The root node points to at least two nodes.

  b. All non-root nodes are at least half full.

  c. For a tree of order m, all internal nodes have m-1 keys and m pointers.

  d. A B+-Tree grows upwards.

  e. A B+-Tree is balanced.

  f. Sibling pointers allow sequential searching.

• Example