Computer Notes

Header Right

Home » DS » Trees

What is b-tree?

By Dinesh Thakur

The term b-tree refers to a way of organizing database information so that you can quickly search through it to find exactly what you’re looking for. B-tree is a way of organizing database keys so you can quickly search them on disk.

A database contains collections of related information, similar to file cards. Each record contains several fields, such as name, address, date of birth, etc. We want to find something based on one of those pieces of information. We could search sequentially through the whole file, but imagine if you had to search through the entire database of California social security numbers one by one. A b-tree allows you to search efficiently for specific names or numbers even as you are adding or deleting from the database. It dynamically grows and shrinks and maintains an up-to-date index stored as a tree, hence the name. (The letter “b” is to differentiate from other types of previously existing trees.)

What is Tree ? Explian Binary Tree.

By Dinesh Thakur

An important class of digraph, which involves for the description of hierarchy. A directed tree is an acyclic digraph which has one node called root with in degree 0, while other nodes have in degree Every directed tree must have at least one node.

An isolated node is also called as directed tree. The node with out degree as 0 is called as leaf. The length of the path from root to particular node level of the node. If the ordering of the node at each level is prescribed then the tree is called as ordered tree.            

Binary Tree

            If a tree has at most of two children, then such tree is called as Binary tree. If the elements in the binary tree are arranged in the following order

            Left element is lesser than the root

            Right element is greater then the root

            No duplication of elements

Then such binary tree is called as Binary Search Tree

           

Operations performed in a binary tree are:

 

    • Inserting a node
    • Deleting a node
    • Traversing the tree
    •  

Traversing Methods

 

1.      Pre – order method

2.      In – order method

3.      Post – order method

4.      Converse Pre – order method

5.      Converse In – order method

6.      Converse post – order method

Pre – order method

            This method gives the tree key value in the following manner: –

1.      Process the root

2.      Traverse the left sub tree

3.      Traverse the right Sub tree

In – order method

            This method gives the tree key value in the following manner: –

1.      Traverse the left sub tree

2.      Process the root

3.      Traverse the right Sub tree

Post – order method

            This method gives the tree key value in the following manner: –

1.      Traverse the left sub tree

2.      Traverse the right Sub tree

3.    Process the root