B-Tree

This app demonstrates the data structure B-Tree and BPlus-Tree.

About Me:

Tauqueer Ahmad,

B.Tech Student,

Computer Science and Engineering,

IIT Roorkee.

This project was made during Winter 2014 at IIT Roorkee under the guidance of:

Dr. Balasubramanian Raman,

Professor,

Computer Science and Engineering,

IIT Roorkee.

In the emerging field of computer science, this app is useful for the learners. It’s an open source application anyone can check out the source and develop it accordingly.

This app demonstrates insertion, deletion and search operations for the data structure B-Tree and B+ -Tree.

This is the updated version of the app. In contrast to the previous version this version gives you choice between the two slightly different definitions of B-Tree:

1. B-Tree defined in terms of Maximum degree.

2. B-Tree defined in terms of Minimum degree.

The previous version only had the minimum degree alternative.

One more difference that you will encounter is that in the second definition I used preemptive splitting, that is the algorithm first checks whether the node has got maximum keys or not. If it does then before inserting the new key it first splits the node. Whereas in the first one the algorithm first inserts one more than the maximum number of elements and then splits the node.

B-Tree and B+-Trees are extensively used in computer science and to understand the concept of these data structures this app is quite useful. It demonstrates how the various operation are performed on them.

A B-tree is a tree data structure that keeps data sorted and allows searches, sequential access, insertions, and deletions in logarithmic time. The B-tree is a generalization of a binary search tree in that a node can have more than two children. 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 file systems.

In B-trees, internal (non-leaf) nodes can have a variable number of child nodes within some pre-defined range. When data is inserted or removed from a node, its number of child nodes changes. In order to maintain the pre-defined range, internal nodes may be joined or split. Because a range of child nodes is permitted, B-trees do not need re-balancing as frequently as other self-balancing search trees, but may waste some space, since nodes are not entirely full. The lower and upper bounds on the number of child nodes are typically fixed for a particular implementation.

Properties of B-Trees:

• keeps keys in sorted order for sequential traversing

• uses a hierarchical index to minimize the number of disk reads

• uses partially full blocks to speed insertions and deletions

• keeps the index balanced with an elegant recursive algorithm

B+-Tree is a modification to B-Trees.

A B+ tree can be viewed as a B-tree in which each node contains only keys (not key-value pairs), and to which an additional level is added at the bottom with linked leaves.

The primary value of a B+ tree is in storing data for efficient retrieval in a block-oriented storage context — in particular, file systems. This is primarily because unlike binary search trees, B+ trees have very high fanout (number of pointers to child nodes in a node typically on the order of 100 or more), which reduces the number of I/O operations required to find an element in the tree.

Contact Details:

Skype: tauqueer.iit

+919013965427

[email protected]