B Tree Index Files

B Tree Index Files

AU: Dec.-12,14, May-08, Marks 16

• B-tree indices are similar to B+-tree indices.

• The primary distinction between the two approaches is that a B-tree eliminates the redundant storage of search-key values.

• B-tree is a specialized multiway tree used to store the records in a disk.

• There are number of subtrees to each node. So that the height of the tree is relatively small. So that only small number of nodes must be read from disk to retrieve an item. The goal of B-trees is to get fast access of the data.

• A B-tree allows search-key values to appear only once (if they are unique), unlike a B+-tree, where a value may appear in a nonleaf node, in addition to appearing in a leaf node.

Example 4.9.1 Create B tree of order 3 for following data: 20,10,30,15,12,40,50. Solution: The B tree of order 3 means at the most two key values are allowed in each node of B-Tree.

Step 1: Insert 20,10 in ascending order

Step 2: If we insert the value 30. The sequence becomes 10,20,30. As only two key values are allowed in each node (being order 3), the 20 will go up.

Step 3: Now insert 15.

Step 4: Insert 12. The sequence becomes 10, 12, 15. The middle element 12 will go up.

Step 5: Insert 40

Step 6: Insert 50. The sequence becomes 30,40,50. The 40 will go up. But again it forms 12,20,40 sequence and then 20 will go up. Thus the final B Tree will be,

This is the final B-Tree

Difference between B Tree and B+ Tree

Review Questions

1. Explain detail about i) B+ tree index ii) B tree index files

AU: Dec.-14, Marks 16, May-08, Marks 10

2. Write down detailed notes on ordered indices and B-tree index files. AU: Dec.-12, Marks 16