BTree

B-Tree is generalization of Binary Search Tree, but node could have more than 2 children.

The biggest advantage comes for B-Tree when one node of tree contains keys equal to the physical page size. Thus in case of searching the search complexity would be O(log_{noofNodesInAPage}n). Thus for example, one node of B-Tree stores 1000 Elements, and the complexity would become: log₁₀₀₀n which, for 1,000,000 is just 2. Thus only in 2 physical page loads, index is searched.

b tree is generalization of a-b tree, with b = 2a. Also b-tree is disk based data structure, thus a is generally large (range of 1000) depending upon size of page.