B‐Tree

B-Tree

Unlike AVL Tree, Red-Black Tree etc, where every node can have only one value(key) and a maximum of two children, B-Tree is a type of search tree in which a node can store more than one value(key) and it can have 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.

In a B-Tree, the number of keys in a node and the number of children for a node depends upon the order of the B-Tree. Every B-Tree has its order. A B-Tree of order m has the following properties:

• All the leaf nodes must be at same level.
• All nodes except root must have at least [m/2]-1 keys and maximum of m-1 keys.
• All non leaf nodes except root (i.e. all internal nodes) must have at least m/2 children.
• If the root node is a non leaf node, then it must have at least 2 children.
• A non leaf node with n-1 keys must have n number of children.
• All the keys values within a node must be arranged in Ascending Order.

Example:

Analysis of B-Trees

• The maximum number of items in a B-Tree of order m and height h:

root m-1

level 1 m(m-1)

level 2 m²(m-1)

. . .

level h m^h(m-1)

• So, the total number of items is : (1+m+m²+m³+ . . . + m^h)(m-1) = m^h+1 - 1
• When m = 5 and h = 2, 5³ - 1 = 124

Insertion in B-Tree

The new element in a B-Tree must be added only at the leaf node. That means, the new KeyValue is attached to the leaf node only. The algorithm is as follows:

1. Check whether the tree is Empty
2. If the tree is Empty, then create a new node with the new key value and insert into the tree as a root node
3. If the tree is Not Empty, find a leaf node to which the new key value can be added using Binary Search Tree method
4. If that leaf node has an empty position, then add the new key value to that node by maintaining ascending order of key value within the node
5. If that leaf node is already full, then split that leaf node by sending middle valude to its parent node. Repeat the same process until sending values is fixed into a node
6. If the splitting is occuring to the root node, then the middle value becomes new root node for the tree and the height of the tree is increased by one

Example:

Construct B-tree of order 5 and keys arrive in the following order:1 12 8 2 25 5 14 28 17 7 52 16 48 68 3 26 29 53 55 45

• The first four items go into the root

• To put the fifth item in the root would violate the rule. Therefore, when 25 arrives, pick the middle key to make a new root

• 6, 14 and 28 are added to the leaf nodes

• Adding 17 to the right leaf node would over-fill it, so we take the middle key, promote it (to the root) and split the leaf

• 7, 52, 16, 48 get added to the leaf nodes

• Adding 68 causes us to split the right most leaf, promoting 48 to the root, and adding 3 causes us to split the left most leaf, promoting 3 to the root; 26, 29, 53, 55 then go into the leaves

• Adding 45 causes a split of

and promoting 28 to the root then causes the root to split.

Reasons for using B-Trees

• When searching tables held on disc, the cost of each disc transfer is high but doesn't depend much on the amount of data transferred, especially if consecutive items are transferred

- If we use a B-tree of order 101, say, we can transfer each node in one disc read operation

- A B-tree of order 101 and height 3 can hold 10¹⁴ – 1 items (approximately 100 million) and any item can be accessed with 3 disc reads (assuming we hold the root in memory)

• If we take m = 3, we get a 2-3 tree, in which non-leaf nodes have two or three children (i.e., one or two keys)

- B-Trees are always balanced (since the leaves are all at the same level), so 2-3 trees make a good type of balanced tree

References

1. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, “Introduction toAlgorithms”
2. G. Brassard and P. Bratley, “Fundamentals of Algorithms”
3. R. L. Kruse, B. P. Leung, C. L. Tondo, “Data Structure and Program designin C”