written 7.8 years ago by | modified 2.8 years ago by |
Mumbai University > Information Technology > Sem 5 > Advanced Database Management System
Marks: 5M
Year: Dec 2014
written 7.8 years ago by | modified 2.8 years ago by |
Mumbai University > Information Technology > Sem 5 > Advanced Database Management System
Marks: 5M
Year: Dec 2014
written 7.8 years ago by |
Multilevel indexing improve the efficiency of searching an index file in following way:
1) A multilevel index reduces the number of blocks accessed when searching for a record, given its indexing field value.
2) To retain the benefits of using multilevel indexing while reducing index insertion and deletion problems,
3) Designers adopted a multilevel index that leaves some space in each of its blocks for inserting new entries. This is called a dynamic multilevel index and is often implemented by using data structures called B-trees and B+-trees.
B+ Tree
A B+ tree is a balanced binary search tree that follows a multi-level index format. The leaf nodes of a B+ tree denote actual data pointers. B+ tree ensures that all leaf nodes remain at the same height, thus balanced. Additionally, the leaf nodes are linked using a link list; therefore, a B+ tree can support random access as well as sequential access.
Structure of B+ Tree
Every leaf node is at equal distance from the root node. A B+ tree is of the order n where nis fixed for every B+ tree.
Internal nodes
Leaf nodes
B+ Tree Insertion
B+ Tree Deletion
The target entry is searched and deleted.
If it is an internal node, delete and replace with the entry from the left position.
After deletion, underflow is tested,
If distribution is not possible from left, then
Distribute from the nodes right to it.
If distribution is not possible from left or from right, then
Merge the node with left and right to it.