B- Trees
Prepared By
Biddut Kumar
Lecturer in CSE Dept.
Shyamoli Textile Engineering College (STEC)
What is B- tree?
A B-tree is a specialized multi way tree designed especially for use
on disk.
A B- tree is a balanced tree in which B-Tree consists of a root
node, branch nodes and leaf nodes containing the indexed field
values in the ending (or leaf) nodes of the tree.
They are general form of a Binary Search Tree as it holds more than one
key and two children.
Properties of B trees :-
The various properties of B trees include −
Every node in a B Tree will hold a maximum of m children and (m-
1) keys, since the order of the tree is m.
Every node in a B tree, except root and leaf, can hold at least m/2
children
The root node must have no less than two children.
All the paths in a B tree must end at the same level, i.e. the leaf
nodes must be at the same level.
A B tree always maintains sorted data.
B trees are also widely used in disk access, minimizing the disk access
time since the height of a b tree is low.
Note − A disk access is the memory access to the computer disk where
the information is stored and disk access time is the time taken by the
system to access the disk memory.
Basic Operations of B Trees
The operations supported in B trees are Insertion, deletion and searching
with the time complexity of O(log n) for every operation.
Insertion
The insertion operation for a B Tree is done similar to the Binary Search
Tree but the elements are inserted into the same node until the
maximum keys are reached. The insertion is done using the following
procedure −
Step 1 − Calculate the number of keys a node can hold, where m is
denoted by the order of the B Tree.
Step 2 − The data is inserted into the tree using the binary search
insertion and once the keys reach the maximum number, the node is split
into half and the median key becomes the internal node while the left
and right keys become its children.
Step 3 − All the leaf nodes must be on the same level.
The keys, 5, 3, 21, 9, 13 are all added into the node according to the
binary search property but if we add the key 22, it will violate the
maximum key property. Hence, the node is split in half, the median key
is shifted to the parent node and the insertion is then continued.
Another hiccup occurs during the insertion of 11, so the node is split and
median is shifted to the parent.
While inserting 16, even if the node is split in two parts, the parent node
also overflows as it reached the maximum keys. Hence, the parent node
is split first and the median key becomes the root. Then, the leaf node is
split in half the median of leaf node is shifted to its parent.
The final B tree after inserting all the elements is achieved.
Math :
Consider a B- tree with key size =10 bytes, block size=512 bytes, data
pointer=8 bytes and block pointer=5 bytes. What is the order of B-
tree?
Suppose,
order of b-tree is= n
Block pointer=Bp
Data pointer=Dp
n * Bp + (n-1)*key+(n-1)*Dp ≤ Block size
n*5+(n-1)*(key+Dp) ≤ Block size
5n+(n-1)*(10+8) ≤ 512
5n+(n-1)*18 ≤ 512
5n+18n-18 ≤ 512
23n ≤ 512+18
n ≤ 530/23
n ≤ 23.04
The order of B- tree is = 23
Difference Between B- tree and B+ tree :-
S.L B- tree B+ -tree
1 Data is stored in leaf as will as internal Data is stored only in in
node. leaf nodes.
2 Searching is slower, deletion complex. Searching is faster,
deletion easy.
3 No redundant search key present. Redundant search key
may present.
4 Leaf nodes not linked together. Linked together the
linked list.
5 All internal and leaf nodes have data Only leaf nodes have
pointers. data pointers.
6 Sequential access to nodes is not Sequential access is
possible. possible just like linked
list.
7 B-Trees used in Databases, Search B+ Trees used in
engines. Multilevel Indexing,
Database indexing.
