B-tree is a tree data structure that keeps data always in the sorted order. The time complexity for the operations like searching, insertions, deletions, and sequential access is logarithmic amortized time. In other way, B-tree is a generalization of a binary search tree in which more than two paths may diverge from a single node and all leaf nodes must be at the same level. B-trees are most commonly used in databases and filesystems. B Trees are balanced search tree which are designed to work on secondary storage devices like magnetic disks, hard disks etc. As branchimg factor of Btress can be very large so they can store large amount of data easily. Some algorithms are being implemented to copy the fixed number of pages from disk in to the primary memory like RAM and also write down on to the disks those pages which have been altered. Generally branching factor in between 50 and 2000 are being used to store a large B Tree on disks. If a database contains n key values then worst case running time of searching an un indexed and unsorted key value will be of order of n that is O(n) but if the same data is indexed with a B-tree, the same search operation will run in O(log n) which is always asymptotic less than O(n). To perform a search for a single key on a set of one million keys (1,000,000), As it is well known fact that a linear search will require at most 1,000,000 comparisons but If the same data is indexed with a B-tree of minimum degree (10), then only 114 comparisons will be required in the worst case. So indexing large amounts of data can significantly improve search performance. Although other balanced tree structures can be used, a B-tree also optimizes costly disk accesses that are of concern when dealing with large data sets and operation of searching, inserting, deleting etc. is being done rapidly. In this paper, the mathematical derivation of the maximum number of keys in B Tree of height k and minimum degree m is described, tested and found to be absolutely correct. ...
Read more