1
Winter 2003 1
• B+ Trees. Section 10.3-10.6, 10.8
• Static and Extendible Hashing. Section 11.1 and 11.2
Winter 2003 2
• Inserts and deletes affect only the leaf pages. As a
consequence, long overflow chains at the leaf pages
may result
• Long overflow chains may significantly slow down the
time to retrieve a record (all overflow pages have to be
searched)
• Overflow pages are not sorted. Therefore, lookup is
slow. Possible to keep overflow pages sorted also but
inserts will be slow
• Overflow pages do not go away unless all records in the
overflow pages are deleted, or a complete reorganization
is performed
2
Winter 2003 3
• A dynamic index structure that adjusts gracefully to
inserts and deletes
• A balanced tree
• Leaf pages are not allocated sequentially. They are
linked together through pointers (a doubly linked list).
Index Entries
Data Entries
("Sequence set")
(Direct search)
Winter 2003 4
• Main characteristics:
– Insert/delete at logFN cost; keep tree height-balanced.
(F = fanout, N = # leaf pages)
– Minimum 50% occupancy (except for root). Each
node contains d <= m <= 2d entries. The parameter
d is called the order of the tree.
– Supports equality and range-searches efficiently.
3
Winter 2003 5
! "
• Same as that of ISAM
• Non-leaf nodes with m index entries contain m+1
pointers to children
• Pointer Pi points to a child with key values k such that ki k <>
• P0 points to a child whose key values are less than k1
Winter 2003 6
# $
• Search begins at root, and key comparisons direct it to a
leaf. At each node, a binary search or linear search can
be performed
• Search for 5*, 15*, all data entries >= 24* ...
• Based on the search for 15*, we know it is not in the tree!
Root
17 24 30
2* 3* 5* 7* 14* 16* 19* 20* 22* 24* 27* 29* 33* 34* 38* 39*
13
4
Winter 2003 7
% & #
• Find correct leaf L.
• Put data entry onto 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.
• Insert index entry pointing to L2 into parent of L.
• This can happen recursively
– To split index node, redistribute entries evenly, but
push up middle key. (Contrast with leaf splits.)
• Splits “grow” tree; root split increases height.
– Tree growth: gets wider or one level taller at top.
Winter 2003 8
% ' ( # $
• Observe how
minimum
occupancy is
guaranteed in both
leaf and index pg
splits.
• Note difference
between copy-up
and push-up; be
sure you
understand the
reasons for this.
2* 3* 5* 7* 8*
5
Entry to be inserted in parent node.
(Note that 5 is
continues to appear in the leaf.)
s copied up and
appears once in the index. Contrast
5 24 30
17
13
Entry to be inserted in parent node.
(Note that 17 is pushed up and only
this with a leaf split.)
5
Winter 2003 9
# $
"
% ' (
• Notice that root was split, leading to increase in height.
• In this example, we can avoid split by re-distributing
entries; however, this is usually not done in practice.
2* 3*
Root
17
24 30
14* 16* 19* 20* 22* 24* 27* 29* 33* 34* 38* 39*
13 5
7* 5* 8*
Winter 2003 10
# $
"
% ' (
2* 3*
Root
17
24 30
14* 16* 19* 20* 22* 24* 27* 29* 33* 34* 38* 39*
13 5
7* 5* 8*
• Notice that the value 5 occurs redundantly, once in a leaf
page and once in a non-leaf page. This is because
values in the leaf page cannot be pushed up, unlike the
value 17
6
Winter 2003 11
)
%
Root
17 24 30
2* 3* 5* 7* 14* 16* 19* 20* 22* 24* 27* 29* 33* 34* 38* 39*
13
Root
17 24 30
2* 3* 5* 7* 14* 16* 19* 20* 22* 24* 27* 29* 33* 34* 38* 39*
8
Insert 8*
8*
Winter 2003 12
)
%
• If a leaf node where insertion is to occur is full, fetch a
neighbour node (left or right).
• If neighbour node has space and same parent as full
node, redistribute entries and adjust parent nodes
accordingly
• Otherwise, if neighbour nodes are full or have a different
parent (i.e., not a sibling), then split as before.
7
Winter 2003 13
&
% & # "
• Start at root, find leaf L where entry belongs.
• Remove the entry.
– If L is at least half-full, done!
– If L has only d-1 entries,
• Try to re-distribute, borrowing from sibling (adjacent
node with same parent as L).
• If re-distribution fails, merge L and sibling.
• If merge occurred, must delete entry (pointing to L or
sibling) from parent of L.
• Merge could propagate to root, decreasing height.
Winter 2003 14
# $
"
*
% ' ( +
, &
% - . ( / 0 ( 1 1
• Deleting 19* is easy.
• Deleting 20* is done with re-distribution. Notice how
middle key is copied up.
2* 3*
Root
17
30
14* 16* 33* 34* 38* 39*
13 5
7* 5* 8* 22* 24*
27
27* 29*
8
Winter 2003 15
1 1
&
% / 2 (
• Must merge.
• Observe `toss’ of index
entry (on right), and `pull
down’ of index entry
(below).
30
22* 27* 29* 33* 34* 38* 39*
2* 3* 7* 14* 16* 22* 27* 29* 33* 34* 38* 39* 5* 8*
Root
30 13 5 17
Winter 2003 16
&
/ 2 (
2* 3*
Root
22
30
14* 16* 33* 34* 38* 39*
13 5
7* 5* 8* 22* 24*
27
27* 29*
17 20
17* 18* 20* 21*
9
Winter 2003 17
# $
" 3 4
" )
4
• Tree is shown below during deletion of 24*. (What could
be a possible initial tree?)
• In contrast to previous example, can re-distribute entry
from left child of root to right child.
Root
13 5 17 20
22
30
14* 16* 17* 18* 20* 33* 34* 38* 39* 22* 27* 29* 21* 7* 5* 8* 3* 2*
Winter 2003 18
"
)
4
• Intuitively, entries are re-distributed by `pushing through’
the splitting entry in the parent node.
• It suffices to re-distribute index entry with key 20; we’ve redistributed
17 as well for illustration.
14* 16* 33* 34* 38* 39* 22* 27* 29* 17* 18* 20* 21* 7* 5* 8* 2* 3*
Root
13 5
17
30 20 22
10
Winter 2003 19
5 % "
• If we have a large collection of records, and we want to
create a B+ tree on some field, doing so by repeatedly
inserting records is very slow.
• Bulk Loading for creating a B+ tree index on existing
records is much more efficient
Winter 2003 20
5 %
• Sort all data entries
– If data entries are (key, pointer) pairs, sort these pairs
according to key values and not the actual data
records
• Allocate an empty page to be the root. Insert pointer to
first (leaf) page in root page
3* 4* 6* 9* 10* 11* 12* 13* 20* 22* 23* 31* 35* 36* 38* 41* 44*
Sorted pages of data entries; not yet in B+ tree
Root
11
Winter 2003 21
5 %
• Add entry into root page for each page of sorted data
entries. Doubly linked data entry pages. Proceed until
root page is filled or no more data entry pages
3* 4* 6* 9* 10* 11* 12* 13* 20* 22* 23* 31* 35* 36* 38* 41* 44*
Root
6 10
Sorted pages of data entries; not yet in B+ tree
Winter 2003 22
5 %
• If root page is filled and to insert one more page of data
entries, split the root and create a new root page
3* 4* 6* 9* 10* 11* 12* 13* 20* 22* 23* 31* 35* 36* 38* 41* 44*
Root
6
Sorted pages of data entries; not yet in B+ tree
12
10
12
Winter 2003 23
5 %
• Index entries for leaf
pages always entered
into right-most index
page just above leaf
level. When this fills
up, it splits. (Split
may go up right-most
path to the root.)
• Much faster than
repeated inserts,
especially when one
considers locking!
3* 4* 6* 9* 10*11* 12*13* 20*22* 23* 31* 35*36* 38*41* 44*
Root
Data entry pages
not yet in B+ tree 35 23 12 6
10 20
3* 4* 6* 9* 10* 11* 12*13* 20*22* 23* 31* 35*36* 38*41* 44*
6
Root
10
12 23
20
35
38
not yet in B+ tree
Data entry pages
Winter 2003 24
"
5 %
• Option 1: multiple inserts.
– Slow.
– Does not give sequential storage of leaves.
• Option 2: Bulk Loading
– Has advantages for concurrency control.
– Fewer I/Os during build.
– Leaves will be stored sequentially (and linked, of
course).
– Can control “fill factor” on pages.
13
Winter 2003 25
• Many alternative file organizations exist, each
appropriate in some situation.
• If selection queries are frequent, sorting the file or
building an index is important.
– Hash-based indexes only good for equality
search.
– Sorted files and tree-based indexes best for range
search; also good for equality search. (Files rarely
kept sorted in practice; B+ tree index is better.)
• Index is a collection of data entries plus a way to
quickly find entries with given key values.
Winter 2003 26
• Data entries can be actual data records,
pairs, or pairs.
– Choice orthogonal to indexing technique used to
locate data entries with a given key value.
• Can have several indexes on a given file of data
records, each with a different search key.
• Indexes can be classified as clustered vs.
unclustered, primary vs. secondary, and dense vs.
sparse. Differences have important consequences
for utility/performance.
14
Winter 2003 27
• Tree-structured indexes are ideal for range-searches, also
good for equality searches.
• ISAM is a static structure.
– Only leaf pages modified; overflow pages needed.
– Overflow chains can degrade performance unless size
of data set and data distribution stay constant.
• B+ tree is a dynamic structure.
– Inserts/deletes leave tree height-balanced; logFN cost.
– High fanout (F) means depth rarely more than 3 or 4.
– Almost always better than maintaining a sorted file.
Winter 2003 28
• Recall that for any index, there are 3 alternatives for data
entries k*:
– Data record with key value k
–
–
– Choice orthogonal to the indexing technique
• Hash-based indexes are best for equality selections.
Cannot support range searches.
• Static and dynamic hashing techniques exist; trade-offs
similar to ISAM vs. B+ trees.
15
Winter 2003 29
6 %
• h(k) mod N returns the bucket to which data entry with
key k belongs. (N = # of buckets)
• We refer to the above as the hash function which maps
values into a range of buckets
h(key) mod N
h
key
Primary bucket pages Overflow pages
2
0
N-1
Winter 2003 30
6 %
• # primary pages fixed (which is N), allocated
sequentially, never de-allocated; overflow pages if
needed.
• Buckets contain data entries, which can be in any of the
three alternatives discussed earlier
• Hash function works on search key field of record r.
Must distribute values over range 0 ... N-1.
– Typically, h(key) = (a * key + b) for some constants a
and b
– lots known about how to tune h.
16
Winter 2003 31
6 %
• Search for data entry k: Apply hash function h on k to
obtain the bucket number. Then, search the bucket for k.
– Data entries in each bucket are typically maintained in
sorted order to speed up the search
• Insert a data entry k: Apply hash function h on k to
obtain the bucket number. Place data entry in that
bucket. If no space left, allocate a new overflow page and
place data entry in the overflow page. Chain up the
overflow page.
• Delete a data entry k: Search k and delete
Winter 2003 32
6 % 4 # $
• Assume 2 data entries per bucket and we have 5 buckets
• Insert key values a,b,c,d,e,f,g where h(a)=1, h(b)=2, h(c)=3, … h(g)=7
e
d
c
b,g
a,f
Insert z,x where
h(z)=1 and h(x)=5
1
2
3
4
5 e,x
d
c
b,g
a,f 1
2
3
4
5
z
e,x
d
c
b,g
a,f 1
2
3
4
5
z,p
Insert p,q,r where h(p)=1,
h(q)=5, and h(r)=1
r
q
17
Winter 2003 33
6 %
• Long overflow chains can develop and degrade
performance.
• Number of buckets is fixed. What if file shrinks
significantly through deletions?
– Extendible and Linear Hashing: Dynamic techniques
to fix this problem.
Winter 2003 34
#
6 %
• Situation: Bucket (primary page) becomes full. Why not reorganize
file by doubling number of buckets?
– Reading and writing all pages is expensive!
– Idea: Use directory of pointers to buckets, double # of
buckets by doubling the directory, splitting just the
bucket that overflowed!
– Directory much smaller than file, so doubling it is much
cheaper. Only one page of data entries is split. No
overflow page!
– Trick lies in how hash function is adjusted!
18
Winter 2003 35
# $
• Directory is array of
size 4.
• Search: To find bucket
for r, take last `global
depth’ # bits of h(r);
• If h(r) = 5 = binary 101,
it is in bucket pointed
to by 01.
13* 00
01
10
11
2
2
2
2
2
LOCAL DEPTH
GLOBAL DEPTH
DIRECTORY
Bucket A
Bucket B
Bucket C
Bucket D
DATA PAGES
10*
1* 21*
4* 12* 32* 16*
15* 7* 19*
5*
Winter 2003 36
No comments:
Post a Comment