Search for notes by fellow students, in your own course and all over the country.
Browse our notes for titles which look like what you need, you can preview any of the notes via a sample of the contents. After you're happy these are the notes you're after simply pop them into your shopping cart.
Document Preview
Extracts from the notes are below, to see the PDF you'll receive please use the links above
Multilevel Indexing and B-Trees
Why B-Tree for multilevel indexing?
1
...
Small parts of it can be kept in main store at
one time, bulk of the index must be kept on back up store
...
Index on secondary storage leads to slow access as accessing
secondary storage is slow
...
Searching the index must be faster then binary searching
4
...
Seeking is slow and expensive operation
...
Insertion and deletion must be as fast as search
...
6
...
7
...
8
...
Binary search tree is not solution for
maintaining index why?
1
...
Hence searching process
becomes slow
...
BST is not balanced tree
...
• Binary trees grow from the top down: new nodes are added
as new leaves
...
• The imbalance of a binary tree depends on the order in which
nodes are added and deleted
...
AVL Tree
A binary tree which maintains height balance (to HB(1))
by means of localized reorganizations of the nodes
...
• AVL trees are not perfectly balanced
...
44 log (N + 2)
compares
...
• Balancing a paged binary tree can involve rotations
across pages, involving physical movement of nodes
...
M is the order
...
This is a good structure if much of the tree
is in slow memory (disk), since the height, and hence
the number of accesses, can be kept small, say one
or two, by picking a large m
...
B-trees
•
•
•
•
•
1
...
Disadvantages of multiway tree:
the height of a tree is more
...
What is B tree ?
It is an m-way search tree with additional properties :
The root is either a leaf or it has 2…m subtrees
...
3
...
4
...
5
...
A B-tree of order M with the following properties
• The data items are stored at leaves
• The nonleaf nodes store up to M-1 keys to guide
the searching; key I represents the smallest key in
subtree I +1
...
• All nonleaf nodes (except the root) have between
[M/2] and M children
• All leaves are at the same depth and have
between [L/2] and L children, for some L (the
determination of L is described shortly)
...
• File
...
Creation of B-Tree
1
...
2
...
3
...
4
...
Specialization
• 2-3-4 tree
A B-tree of order 4, that is, internal nodes have
two, three, or four children
...
2-3 tree
A B-tree of order 3, that is, internal nodes have
two or three children
...
If n has more than the minimum number of keys and the k is
not the largest in n, simply delete k from n
...
If n has more than the minimum number of keys and the k is
the largest in n, delete k and modify the higher level indexes
to reflect the new largest key in n
...
If n has exactly the minimum number of keys one of the
siblings of n has few enough keys, merge n with its sibling
and delete a key from the parent node
...
If n has exactly the minimum number of keys and one of the
siblings of n has extra keys, redistribute by moving some
keys from a siblings to n, and modify the higher level indexes
to reflect the new largest keys in the affected nodes
...
If the key to be deleted is not in a leaf,
swap it with its immediate successor, which is in a leaf
(might be redistributed or concatenated!)
– 2
...
If underflow occurs
(the leaf now contains one too few keys),
3
...
2 Otherwise, concatenate the two leaves and the
median key from the parent into one leaf
3
...
Redistribution during insertion
• Find correct leaf L
...
–
–
If L has enough space, done!
Else, must split L (into L and a new node L2)
• Redistribute entries evenly, copy up middle key
...
• This can happen recursively
–
To split index node, redistribute entries evenly, but push up
middle key
...
)
• Splits “grow” tree; root split increases height
...
• Diagram for explanation
...
• Remove the entry
...
• If re-distribution fails, merge L and sibling
...
• Merge could propagate to root, decreasing height
...
12 Deletion, Merging, and Redistribution
Concatenation(merge)
• Occur in case of underflow
• Combining the two pages and the key from the parent page
==> make a single full page
• Reverse the splitting
• Concatenation must involve demotion of keys : may cause
underflow in the parent page
• The effects propagate upward
Redistribution during insertion: a way to
improve storage utilization
• Redistribution during insertion is a way of
avoiding or at least postponing the creation of
new pages
...
The use
of redistribution in place of splitting should
therefore tend to make a B tree more efficient
in its utilization of space
...
In this method delay splitting a node when it overflows
...
• A B-tree in which nodes are kept 2/3 full by
redistributing keys to fill two child nodes, then splitting
them into three nodes
...
f
...
• Every page except for the root has at least
(2m-1)/3 descendants
...
The main difference between a B-Tree and a B*
Tree is in the second rule
...
Insert 14
Example of B* tree of order 4
10,15, 20
5, 6, 8,10
full
After inserting 14
11,14,15
¾ full
17,20
half full
Example of B* tree of order 4
8,14, 20
5, 6, 8
10,11,14
15, 17,20
¾ full
¾ full
¾ full
The above diagram is B* tree
B+ - Tree Structure
• A B+ - Tree is in the form of a balanced tree in which
every path from the root of the tree to a leaf of the
tree is the same length
...
• Each leaf node has one additional pointer which is
used to move to the next leaf node in sequence
...
33
Example B+ Tree
• Search begins at root, and key comparisons direct it to a leaf
...
Root
13
2*
3*
5*
7*
14* 16*
17
24
19* 20* 22*
30
24* 27* 29*
33* 34* 38* 39*
Based on the search for 15*, we know it is not in the tree!
Example of B-Trees
This table shows a B+ tree
...
(We have room for one more key and pointer in
the root page
...
The leaf pages are
maintained in sequential order AND a doubly
linked list (not shown) connects each leaf page
with its sibling page(s)
...
• The following examples illustrate each of
the insert scenarios
...
Since only the leaf
node containing 25 and 30 contains
expansion room, we're going to insert a
record with a key value of 28 into the B+
tree
...
Add to a non-full tree
• Add Record with Key 28
Adding a record when the leaf page is full
but the index page is not
• we're going to insert a record with a key value of 70 into
our B+ tree
...
Unfortunately this page is
full
...
The following table shows the B+ tree after
the addition of 70
...
This record belongs in the page
containing 75, 80, 85, and 90
...
Unfortunately, the index page is also full, so
we split the index page:
• Left Index Page Right Index Page New Index Page
• 25 50
75 85
60
The following table illustrates the addition of the record containing 95 to
the B+ tree
...
As a refresher this tree is
printed in the following table
...
This record is in a leaf page
containing 60, 65 and 70
...
Since
our fill factor is 50% or (2 records) we simply
delete 70 from the leaf node
...
Delete Record with Key 70
Delete 25 from the B+ tree
Next, we delete the record containing 25 from the B+
tree
...
The fill factor will be 50% after the
deletion; however, 25 appears in the index page
...
Delete 25 from the B+ tree
Delete 60 from the B+ tree
• As our last example, we're going to delete 60
from the B+ tree
...
The leaf page containing 60 (60 65) will be below
the fill factor after the deletion
...
2
...
Hence, it will also fall below
the fill factor
...
3
...
Obviously, it will be removed with the
deletion
...
Notice that the
tree contains a single index page
...
it is not a binary tree