program of insertion and deletion in b tree

The B tree is perfectly balanced so that the number of nodes accessed to find a key becomes less. Considering the order of the tree of 4, so each node (except root) has at least 1 key.įrom the properties, we can conclude that any node (except the root) in B tree is at least half full and this avoids wastage of space. Eg: In the figure given, the keys are stored as (ascending order). Each node doesn't have multiple values mandatorily, but if it does, then they will be stored in ascending order. As you can see, all the leaf nodes are at the same height.

Re-read the given points while checking out the above image. A non-leaf node with n-1 key values should have n non NULL children.If the root node is a non-leaf node, then it will have at least 2 children and at least one key. If the root node is a leaf node (only node in the tree), then it will have no children and will have at least on ekey.All nodes (except root node) should have at least m/2 - 1 keys.In a B tree, all non-leaf nodes (except root node) should have at least m/2 children.The keys of each node of a B tree (in case of multiple keys), should be stored in the ascending order.they have the same depth (height of the tree). All leaf nodes of a B tree are at the same level, i.e.Important Property of B TreeĪ B Tree of order m can be defined as an m-way search tree which is either empty, ot satisfies the following properties: The same process follows as we go down the tree. that are greater than 17 are the rightmost child. 12 being lesser than 17 and greater than 6 is the middle child. 4 that is lesser than 6 falls in the left child. The figure above is an example of a B Tree of order 5.

Program of insertion and deletion in b tree