top of page
Search

# What Is B-Tree? Hire Data Structure Expert

B-Trees: Why?

Best tree discussed so far – AVL Tree:

• Important operation Findkey() can be implemented in O(logn) time.

AVL Tree has problems for large data

• The size of the AVL tree increases and may not fit in the system’s main memory.

• The height of the AVL tree also increases – Findkey() operation no more efficient.

To overcome these problems, m-way trees have been created.

M-way tree allows:

• Each node to have at the most m children (or sub-trees)

• Each non-leaf node has (k-1) keys if it has k children.

• M-way tree is ordered and could be balanced like an AVL tree

• Because in a m-way tree, a node can have more than two children and more than one data element in it, the overall size (i.e. number of nodes) decreases à height decreases.

• Also, at any time only a part of the tree can be loaded into the main memory à the rest of the tree can remain in disk storage.

• B-trees are a kind of m-way trees.

Special types of B-trees:

• B+ Tree.

• B* Tree.

Database files are represented as B-trees.

B+ Tree: Properties

Tree of order M has following properties

1. Root is either a leaf or has 2 to M children.

2. Non-leaf nodes (except the root)

• have [M/2]to M children

• -->which means they can have from [M/2]-1 to M-1 keys stored in them.

3.Non-leaf store at the most M-1 keys to guide search; key i represents the smallest key in the subtree i + 1.

4. All leaves are at the same depth or level

5. Data elements are stored in the leaves only and have between [M/2] and M data elements.

Notes:

• Actually leaf nodes can have up to L data elements. To simplify we assume L is equal to M.

• Choice of parameters L and M depends on the data being stored in the B+ Tree.

B+ Tree: Example 1

B+ Tree: Example 2

B+ Tree: Search

• How is FindKey operation performed in a B+ Tree?

• Almost as in a BST

• The keys in the non-leaf node are used for guidance.

• The data element is always in the leaves.

• Search path gets traced from the root to the leave, where data element is found or not found.

B+ Tree: Insert

1. Search for a leaf node N into which new data element D will be inserted.

2. Insert D in N in sorted order.

• If N has space for D, insert is complete.

• Otherwise, if there is no space in N “overflow” takes place.

B+ Tree: Delete

1. Search for a leaf node N from which data with key K is to be deleted.

2. Delete K from N.

• If N has minimum number of data elements, delete is complete.

• Otherwise, if there are fewer data elements “underflow” takes place. Underflow is dealt with by:

---> Borrowing a datum (or a subtree) from one of the close sibling nodes.

--->Or, by merging N with one of its close siblings.

Example: Insert

Insert 10

Insert 4

Insert 90

Insert 8 (Overflow)

Insert 8 (Split)

Insert 8 (Update)

Insert 1

Insert 6(overflow)

Insert 6 (Transfer)

Insert 6 (Update)

I hope this may help you to understand the flow of B-tree. If you need any other help related to B-tree then send your request and get instant help with an affordable price.