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.


Contact Us!

realcode4you@gmail.com



1 view0 comments