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.

Contact Us!