- Trending Categories
- Data Structure
- Networking
- RDBMS
- Operating System
- Java
- iOS
- HTML
- CSS
- Android
- Python
- C Programming
- C++
- C#
- MongoDB
- MySQL
- Javascript
- PHP

- Selected Reading
- UPSC IAS Exams Notes
- Developer's Best Practices
- Questions and Answers
- Effective Resume Writing
- HR Interview Questions
- Computer Glossary
- Who is Who

Let us first try to understand why we are using B-tree. Then, we will get a clarity on the definition of B-tree.

The reasons for using B-tree are as follows −

When searching tables on disc, the cost of accessing the disk is high but it doesn’t bother about the amount of data transferred. So our aim is to minimize disc access.

We know that we cannot improve the height of trees. So, we wish to make the height of the tree as small as possible.

The solution for this is to use a B-tree, it has more branches and thus less height. As branching increases, depth decreases so does access time.

In a B-tree, one node can hold many elements or items.

Assume that if we want to access one node of B tree, we need one disc read operation. A B tree of order 101 and height 3 can hold 101^{4}-1 items approximately 100 million. So, any item can be accessed with max^{3} 3 disc reads.

B tree are called balanced stored trees, since all the leaves are at the same level, it is also called a multi-way search tree, it is a form of multilevel indexing.

B tree grow towards root not towards leaf.

Now let us try to understand the definition of B-tree, which is explained below −

**Definition** − A B-tree of order m is an m-way tree that means a node can have maxm m children.

B-tree satisfies the following properties −

The number of keys in a node (non leaf node) is one less than the number of its children (and these keys partition the keys of children like a binary search tree).

The root has a minimum one key to maximum (m-1) keys. So, root has minimum two children to maximum m children.

Any node (non-leaf node) except the root has min

^{m}([m/2]-1) to max^{m}(m-1) keys. So, they have min^{m}[ m/2 ] children to max^{m}m children.All leaf nodes are on the same level.

**Note** − Non-leaf nodes are called internal nodes (nodes having child). Leaf nodes are called external nodes (nodes having no child).

A B-tree of order 3 (i.e a node can have maxm 3 children) satisfy following properties −

The root has minimum one key to maximum 2 keys. So root has minimum two children to maximum 3 children.

Any node (non-leaf node) except the root has min

^{m}1 to max^{m}2 keys. So, they have min^{m}2 children to max^{m}3 children.

**Note** − Duplicate key values are not allowed.

Given below is the diagram of a B-tree −

- Related Questions & Answers
- How to create a B-Tree in DBMS?
- What is an expression tree in DBMS?
- What is query optimization and explain its two forms(DBMS)?
- Difference Between B-tree and Binary tree
- What is an A-B Trust and how does it work?
- What is transaction processing? Explain the properties of the transaction(DBMS)
- What is 1NF in DBMS? Explain with examples
- What is an array and what is it used for?
- What are the reasons for Gorkhaland agitation in Darjeeling?
- Explain the advantages and disadvantages of DBMS?
- The Best Reasons for Facebook Passion
- What is a parallel database and explain how it works?
- Explain the inference rules for functional dependencies in DBMS
- Explain the precedence graph for testing conflict serializability(DBMS)
- What are the capabilities of DBMS and why relational DBMS is powerful?

Advertisements