B-Tree
In search trees like binary search tree, AVL Tree, Red-Black tree, etc., every node contains only one value (key) and a maximum of two children. But there is a special type of search tree called B-Tree in which a node contains more than one value (key) and more than two children. B-Tree was developed in the year 1972 by Bayer and McCreight with the name Height Balanced m-way Search Tree. Later it was named as B-Tree.
B trees are extended binary search trees that are specialized in m-way searching, since the order of B trees is 'm'. Order of a tree is defined as the maximum number of children a node can accommodate. Therefore, the height of a b tree is relatively smaller than the height of AVL tree and RB tree.
They
are general form of a Binary Search Tree as it holds more than one key and two
children.
The
various properties of B trees include −
B-Tree
of Order m has the following properties...
Property
#1 - All leaf nodes must be at same level.
Property
#2 - All nodes except root must have at least [m/2]-1 keys and maximum of m-1
keys.
Property
#3 - All non leaf nodes except root (i.e. all internal nodes) must have at
least m/2 children.
Property
#4 - If the root node is a non leaf node, then it must have atleast 2 children.
Property
#5 - A non leaf node with n-1 keys must have n number of children.
Property
#6 - All the key values in a node must be in Ascending Order.
For example:
B-Tree of Order 4 contains a maximum of 3 key values in a node and
maximum of 4 children for a node.
order (m)=4
max key (m-1)= 3
Min Key( [m/2] - 1) =1
max Children =4
Min children (m/2) = 2
Construct a B-Tree of Order 3 by inserting numbers from 1 to 10.
order (m)=3
max key (m-1)= 2
Min Key( [m/2] - 1) =1
max Children =3
Min children (m/2) = 2
Insert 1:
Insert 2:
Element '2'is added to existing leaf node. Here, we have only one node and that node acts as root and also leaf. This leaf node has an empty position. So, new element (2) can be inserted at that empty position.
Insert 3:
Element '3'is added to existing leaf node. Here, we have only one node and that node acts as root and also leaf. This leaf node doesn't has an empty position. So, we split that node by sending middle value (2) to its parent node. But here, this node doesn't has parent. So, this middle value becomes a new root node for the tree.
insert 4:
Insert 5:
Element '5 is larger than root node '2' and it is not a leaf node. So, we move to the right of'2. We reach to a leaf node and it is already full. So, we split that node by sending middle value (4) to its parent node (2). There is an empty position in its parent node. So, value '4'is added to node with value'2' and new element '5' added as new leaf node.
Insert 6:
Element '6'is larger than root node'2'&'4' and it is not a leaf node. So, we move to the right of '4. We reach to a leaf node with value '5' and it has an empty position. So, new element (6) can be inserted at that empty position.
Insert 7:
Element '7'is larger than root node'2'&'4' and it is not a leaf node. So, we move to the right of '4. We reach to a leaf node and it is already full. So, we split that node by sending middle value (6) to its parent node (2&4). But the parent (284) is also full. So, again we split the node (284) by sending middle value '4' to its parent but this node doesn't have parent, so element 4 become the new root node of tree.
Insert 8:
Element '8'is larger than root node '4' and it is not a leaf node. So, we move to the right of '4. We reach to a node with value '6' '8' is larger than '6' and it is also not a leaf node. So, we move to the right of '6. We reach to a leaf node (7) and it has an empty position. So, new element (8) can be inserted at that empty position.
Insert 9:
Insert 10 :
order (m)=5
max key (m-1)= 4
Min Key( [m/2] - 1) =2
max Children =5
Min children (m/2) = 3
step 1:
take root node with 4 keys and start inserting 1,2,3,4
step 3:
after spliting key 9 will be root node.
step 5:
similarly 12,13 will be inserted at leaf node. when 13 being inserted, we have already 4 keys in this node so we cannot insert 13 so what we have to split this node.
after spliting key 12 will be root node.
step 6:
similarly 15,16 will be inserted at leaf node.when 17 being inserted we have already 4 keys in this node so we cannot insert 17 so what we have to split this node.
so node key 15 has to move up to Root node,but root node is also filled ,so splitting in the root node will take place (so that key 9 will go one level up.)
(so that key 9 will go one level up.)
again finally 20 being inserted at leaf node.
key 18 has shifted to up, and splitting done on leaf node.
Construct a B-Tree of Order 5 with following set of data : D,H,Z,K,B,P,Q,E,A,S,W,T,C,L,N,Y,M
|
D |
H |
Z |
K |
B |
P |
Q |
E |
A |
S |
W |
T |
C |
L |
N |
Y |
M |
USE ORDER OF ALPHABETS:
A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z.
order (m)=5
max key (m-1)= 4
Min Key( [m/2] - 1) =2
max Children =5
Min children (m/2) = 3
STEP 1: FOLLOW ALPHABETICAL ORDER
INSERT FIRST 4 ELEMENTS
|
|
|
|
|
B |
P |
Q |
E |
A |
S |
W |
T |
C |
L |
N |
Y |
M |
|
P |
Q |
E |
A |
S |
W |
T |
C |
L |
N |
Y |
M |
|
Q |
E |
A |
S |
W |
T |
C |
L |
N |
Y |
M |
|
E |
A |
S |
W |
T |
C |
L |
N |
Y |
M |
|
A |
S |
W |
T |
C |
L |
N |
Y |
M |
STEP 6: next insert Key S
|
S |
W |
T |
C |
L |
N |
Y |
M |
|
W |
T |
C |
L |
N |
Y |
M |
|
T |
C |
L |
N |
Y |
M |
|
C |
L |
N |
Y |
M |
|
L |
N |
Y |
M |
|
N |
Y |
M |
|
Y |
M |
|
M |
No comments:
Post a Comment