B-Tree is a specialized m-way tree that can be widely used for disk access. A B-Tree of order m can have at most m-1 keys and m children. One of the main reason of using B-Tree is its capability to store large number of keys in a single node and large key values by keeping the height of the tree relatively small.
Properties of B-Tree –
- A B-Tree is defined by the term minimum degree ‘t’
- Every node except root must contain at least (t – 1) keys. Root may contain minimum 1 key.
- All nodes (including root) may contain at most (2t – 1) keys.
- Number of children of a node is equal to the number of keys in it plus 1.
- All keys of a node are sorted in increasing order. The child between two keys k1 and k2 contains all keys in the range from k1 and k2.
B-Tree Insertion
Let us understand the algorithm with an example tree of minimum degree ‘t’ as 3 and a sequence of integers 10, 20, 30, 40, 50, 60, 70, 80 and 90 in an initially empty B-Tree.
Initially root is NULL. Let us first insert 10.
![](https://i0.wp.com/1.bp.blogspot.com/-n8Qz0K2IyWw/YB0E49pQOqI/AAAAAAAAAXI/pjX5GVDXBgc09g2MxX2bRxPewh4sSZxowCLcBGAsYHQ/s320/B-Tree-InsertOperation-1.jpg?w=895&ssl=1)
Let us now insert 20, 30, 40 and 50. They all will be inserted in root because maximum number of keys a node can accommodate is 2*t – 1 which is 5.
![](https://i0.wp.com/1.bp.blogspot.com/-oLKcs9sBiD4/YB0DlpSbrmI/AAAAAAAAAWM/4CoaIb-7dhQWrtiYukHVrvVhqfLzu63mQCLcBGAsYHQ/s320/B-Tree-InsertOperation-2.jpg?w=895&ssl=1)
Let us now insert 60. Since root node is full, it will first split into two, then 60 will be inserted into the appropriate child.
![](https://i2.wp.com/1.bp.blogspot.com/-NlLZ_WT-TDs/YB0DyHxThzI/AAAAAAAAAWQ/PpOl5yal_fI0U2lgPKW1wyuJsopPA1GXgCLcBGAsYHQ/s320/B-Tree-InsertOperation-3.jpg?w=895&ssl=1)
Let us now insert 70 and 80. These new keys will be inserted into the appropriate leaf without any split.
![](https://i0.wp.com/1.bp.blogspot.com/--2_guIgRVCs/YB0D8JHB4XI/AAAAAAAAAWY/gSyBZAnrfKcqPMeoQlpns0HxUX0r2kOqwCLcBGAsYHQ/s320/B-Tree-InsertOperation-4.jpg?w=895&ssl=1)
Let us now insert 90. This insertion will cause a split. The middle key will go up to the parent.
![](https://i2.wp.com/1.bp.blogspot.com/-MKOQE2XZKw8/YB0EF-HGgRI/AAAAAAAAAWg/EoCaIdGwU4Uda6skm3gOj5-Czm8sRd-4wCLcBGAsYHQ/s320/B-Tree-InsertOperation-5.jpg?w=895&ssl=1)
Initial Tree
![](https://i1.wp.com/1.bp.blogspot.com/-qhrk91OxmPA/YB0ETf8kIrI/AAAAAAAAAWo/EDYIovQ1TfQtXHJkIhDSMP9R5ovwyN8_gCLcBGAsYHQ/s320/B-Tree-DeleteOperation-1.jpg?w=895&ssl=1)
After delete 60 the Tree will be
![](https://i1.wp.com/1.bp.blogspot.com/-1GWbqRMkuj4/YB0Eckme2rI/AAAAAAAAAWw/C4rynEPHKZUxv3tmiohV86mvBvnkX4usgCLcBGAsYHQ/s320/B-Tree-DeleteOperation-2.jpg?w=895&ssl=1)
After delete 20 the Tree will be
![](https://i1.wp.com/1.bp.blogspot.com/-IAFB4sFDuIc/YB0EoQZDisI/AAAAAAAAAW4/hMf-wRi9Beg1wyWFG7GAh9ajhMb-SQaBwCLcBGAsYHQ/s320/B-Tree-DeleteOperation-3.jpg?w=895&ssl=1)
After delete 30 the Tree will be
![](https://i2.wp.com/1.bp.blogspot.com/-NPGVgUBDsEg/YB0Ex3bC_SI/AAAAAAAAAXA/PLdlQ7X5kBEV75hCsy69DJ9-IeX_klbKgCLcBGAsYHQ/s320/B-Tree-DeleteOperation-4.jpg?w=895&ssl=1)
0 टिप्पणियाँ:
Post a Comment