B a z y d a n y c h - B D
I n d e k s y
W y k Ba d p r z y g o t o w a B:
R o b e r t W r e m b e l
B D w y k Ba d 7 ( 1 )
1
B a z y d a n y c h - B D
P l a n w y k Ba d u
" P r o b l e m a t y k a i n d e k s o w a n i a
" P o d z i a B i n d e k s w i i c h c h a r a k t e r y s t y k a
i n d e k s p o d s t a w o w y , z g r u p o w a n y , w t r n y
i n d e k s r z a d k i , g s t y
" I n d e k s w i e l o p o z i o m o w y s t a t y c z n y ( I S A M )
" I n d e k s w i e l o p o z i o m o w y d y n a m i c z n y ( B + - d r z e w o )
" A l g o r y t m w s t a w i a n i a d a n y c h d o i n d e k s u B + - d r z e w o
B D w y k Ba d 7 ( 2 )
C e l e m w y k Ba d u j e s t o m w i e n i e p o d s t a w o w y c h k o n c e p c j i i n d e k s o w a n i a d a n y c h i s t r u k t u r
i n d e k s o w y c h . W r a m a c h w y k Ba d u z o s t a n o m w i o n e :
- w p r o w a d z e n i e d o p r o b l e m a t y k i i n d e k s o w a n i a d a n y c h ,
- c h a r a k t e r y s t y k a r |n e g o r o d z a j u i n d e k s w ( p o d s t a w o w y , z g r u p o w a n y , w t r n y , r z a d k i i
g s t y ) ,
- i n d e k s w i e l o p o z i o m o w y s t a t y c z n y ( I S A M ) ,
- i n d e k s w i e l o p o z i o m o w y d y n a m i c z n y ( B + - d r z e w o ) ,
- a l g o r y t m w s t a w i a n i a d a n y c h d o i n d e k s u B + - d r z e w o .
2
B a z y d a n y c h - B D
W p r o w a d z e n i e ( 1 )
" P r o b l e m :
D a n y j e s t p l i k z a w i e r a j c y u p o r z d k o w a n e l u b
n i e u p o r z d k o w a n e r e k o r d y d a n y c h
W j a k i s p o s b e f e k t y w n i e z r e a l i z o w a w y s z u k a n i e
r e k o r d u l u b r e k o r d w z z a d a n e g o z a k r e s u w a r t o [c i
w y b r a n e g o p o l a ?
B D w y k Ba d 7 ( 3 )
R o z w a |m y p l i k z a w i e r a j c y u p o r z d k o w a n e l u b n i e u p o r z d k o w a n e r e k o r d y d a n y c h . J a k
p a m i t a m y z p o p r z e d n i e g o w y k Ba d u w y s z u k i w a n i e d a n y c h w p l i k a c h n i e j e s t e f e k t y w n e .
Z t e g o w z g l d u c h c i e l i b y [m y z n a l e z s p o s b e f e k t y w n e g o w y s z u k i w a n i a d a n y c h .
3
B a z y d a n y c h - B D
W p r o w a d z e n i e ( 2 )
" O d p o w i e d z:
U t w o r z y d r u g i p l i k , z d e f i n i o w a n y n a a t r y b u c i e
w y k o r z y s t a n y m d o s p e c y f i k a c j i k r y t e r i u m
p o s z u k i w a n i a
P l i k t e n z a w i e r a r e k o r d y o d p o w i a d a j c e
p o s z u k i w a n y m w a r t o [c i o m p i e r w s z y c h r e k o r d w w
p o s z c z e g l n y c h b l o k a c h p l i k u d a n y c h
R e k o r d y w d o d a t k o w y m p l i k u m a j p o s t a :
< p i e r w s z y k l u c z w b l o k u , w s k a zn i k d o b l o k u >
P l i k d o d a t k o w y j e s t u p o r z d k o w a n y w e d Bu g w a r t o [c i
p o s z u k i w a n y c h
B D w y k Ba d 7 ( 4 )
R o z w i z a n i e t e g o p r o b l e m u b a z u j e n a w y k o r z y s t a n i u d r u g i e g o p l i k u z d e f i n i o w a n e g o n a
a t r y b u c i e w y k o r z y s t a n y m d o s p e c y f i k o w a n i a k r y t e r i u m p r z e s z u k i w a n i a . P l i k t e n
z a w i e r a Bb y r e k o r d y o d p o w i a d a j c e p o s z u k i w a n y m w a r t o [c i o m p i e r w s z y c h r e k o r d w w
p o s z c z e g l n y c h b l o k a c h p l i k u d a n y c h . R e k o r d y w d o d a t k o w y m p l i k u m i a By b y p o s t a :
< p i e r w s z y k l u c z w b l o k u , w s k a zn i k d o b l o k u > , a p l i k d o d a t k o w y b y Bb y u p o r z d k o w a n y
w e d Bu g w a r t o [c i p o s z u k i w a n y c h .
T a k i p l i k d o d a t k o w y n a z y w a s i i n d e k s e m .
4
B a z y d a n y c h - B D
W p r o w a d z e n i e ( 3 )
" I n d e k s - d o d a t k o w a s t r u k t u r a f i z y c z n a
" C e l s t o s o w a n i a - p r z y [p i e s z e n i e d o s t p u d o d a n y c h
" Z a k Ba d a n e n a p o j e d y n c z y c h a t r y b u t a c h l u b z b i o r a c h
a t r y b u t w r e l a c j i
a t r y b u t y t e s n a z y w a n e i n d e k s o w y m i
" M o d e l f i z y c z n y i n d e k s u
u p o r z d k o w a n y p l i k r e k o r d w i n d e k s u ( a n g . d a t a
e n t r y ) o s t a Be j d Bu g o [c i
r e k o r d i n d e k s u z a w i e r a d w a p o l a
" k l u c z r e p r e z e n t u j c y j e d n z w a r t o [c i
w y s t p u j c y c h w a t r y b u t a c h i n d e k s o w y c h r e l a c j i
" w s k a zn i k d o b l o k u d a n y c h z a w i e r a j c y k r o t k ,
k t r e j a t r y b u t i n d e k s o w y r w n y j e s t k l u c z o w i
B D w y k Ba d 7 ( 5 )
I n d e k s z d e f i n i o w a n y n a p l i k u j e s t d o d a t k o w s t r u k t u r f i z y c z n , k t r e j c e l e m j e s t
p r z y s p i e s z e n i e w y k o n y w a n i a o p e r a c j i , k t r e n i e s w y s t a r c z a j c o e f e k t y w n i e w s p i e r a n e
p r z e z p o d s t a w o w e o r g a n i z a c j e p l i k w i s t r u k t u r y l o g i c z n e d a n y c h .
I n d e k s y s z a k Ba d a n e n a p o j e d y n c z y c h a t r y b u t a c h l u b z b i o r a c h a t r y b u t w r e l a c j i .
A t r y b u t y t e n o s z n a z w a t r y b u t w i n d e k s o w y c h .
I n d e k s j e s t u p o r z d k o w a n y m p l i k i e m r e k o r d w i n d e k s u ( a n g . d a t a e n t r y ) o s t a Be j
d Bu g o [c i . R e k o r d y i n d e k s u z a w i e r a j d w a p o l a : k l u c z r e p r e z e n t u j c y j e d n z w a r t o [c i
w y s t p u j c y c h w a t r y b u t a c h i n d e k s o w y c h r e l a c j i o r a z w s k a zn i k d o b l o k u d a n y c h
z a w i e r a j c y k r o t k , k t r e j a t r y b u t i n d e k s o w y r w n y j e s t k l u c z o w i .
5
B a z y d a n y c h - B D
W p r o w a d z e n i e ( 4 )
" R e k o r d i n d e k s u - k *
z a w i e r a d o s t a t e c z n i n f o r m a c j u m o |l i w i a j c
w y s z u k a n i e ( j e d n e g o l u b w i c e j ) r e k o r d w d a n y c h
o w a r t o [c i k l u c z a k
" P y t a n i e :
W j a k i s p o s b r e k o r d y i n d e k s u p o w i n n y b y
z o r g a n i z o w a n e , a b y e f e k t y w n i e w s p i e r a
w y s z u k i w a n i e r e k o r d w o d a n e j w a r t o [c i k l u c z a ?
C o p o w i n i e n z a w i e r a r e k o r d i n d e k s u ?
B D w y k Ba d 7 ( 6 )
K a |d y r e k o r d i n d e k s u , o z n a c z o n y k * , z a w i e r a d o s t a t e c z n i n f o r m a c j u m o |l i w i a j c
w y s z u k a n i e ( j e d n e g o l u b w i c e j ) r e k o r d w d a n y c h o w a r t o [c i k l u c z a k .
P r o j e k t u j c s t r u k t u r i n d e k s u n a l e |y o d p o w i e d z i e n a d w a p y t a n i a :
P o p i e r w s z e , w j a k i s p o s b r e k o r d y i n d e k s u p o w i n n y b y z o r g a n i z o w a n e , a b y
e f e k t y w n i e w s p i e r a w y s z u k i w a n i e r e k o r d w o d a n e j w a r t o [c i k l u c z a ? P o d r u g i e , c o
p o w i n i e n z a w i e r a r e k o r d i n d e k s u ?
6
B a z y d a n y c h - B D
R e k o r d y i n d e k s u
" T y p y r e k o r d w i n d e k s u :
1 . R e k o r d i n d e k s u k * j e s t r e k o r d e m d a n y c h ( o w a r t o [c i
k l u c z a k )
2 . R e k o r d i n d e k s u j e s t p a r < k , r i d > , g d z i e r i d j e s t
i d e n t y f i k a t o r e m r e k o r d u d a n y c h o w a r t o [c i k l u c z a k
3 . R e k o r d i n d e k s u j e s t p a r < k , r i d - l i s t > , g d z i e r i d - l i s t
j e s t l i s t i d e n t y f i k a t o r w r e k o r d w d a n y c h o w a r t o [c i
k l u c z a k
4 . R e k o r d i n d e k s u j e s t p a r < k , b i t m a p a > , g d z i e b i t m a p a
j e s t w e k t o r e m 0 i 1 r e p r e z e n t u j c y m z b i r r e k o r d w
d a n y c h
B D w y k Ba d 7 ( 7 )
R e k o r d i n d e k s u k * u m o |l i w i a w y s z u k a n i e r e k o r d w d a n y c h o w a r t o [c i k l u c z a k .
W y r |n i a s i c z t e r y t y p y r e k o r d w i n d e k s u :
1 . R e k o r d i n d e k s u k * j e s t r e k o r d e m d a n y c h ( o w a r t o [c i k l u c z a k ) .
2 . R e k o r d i n d e k s u j e s t p a r < k , r i d > , g d z i e r i d j e s t i d e n t y f i k a t o r e m r e k o r d u d a n y c h o
w a r t o [c i k l u c z a k .
3 . R e k o r d i n d e k s u j e s t p a r < k , r i d - l i s t > , g d z i e r i d - l i s t j e s t l i s t i d e n t y f i k a t o r w r e k o r d w
d a n y c h o w a r t o [c i k l u c z a k .
4 . R e k o r d i n d e k s u j e s t p a r < k , b i t m a p a > , g d z i e b i t m a p a j e s t w e k t o r e m 0 i 1
r e p r e z e n t u j c y m z b i r r e k o r d w d a n y c h .
7
B a z y d a n y c h - B D
R o d z a j e i n d e k s w - c h a r a k t e r y s t y k a
a t r y b u t u i n d e k s o w e g o
" I n d e k s p o d s t a w o w y ( p r i m a r y i n d e x )
z a Bo |o n y n a a t r y b u c i e p o r z d k u j c y m u n i k a l n y m
" I n d e k s z g r u p o w a n y ( c l u s t e r i n g i n d e x )
z a Bo |o n y n a a t r y b u c i e p o r z d k u j c y m n i e u n i k a l n y m
" I n d e k s w t r n y ( s e c o n d a r y i n d e x )
z a Bo |o n y n a a t r y b u c i e n i e p o r z d k u j c y m
B D w y k Ba d 7 ( 8 )
Z p u n k t u w i d z e n i a c h a r a k t e r y s t y k i a t r y b u t u i n d e k s o w e g o w y r |n i a s i t r z y r o d z a j e
i n d e k s w :
- i n d e k s p o d s t a w o w y ( a n g . p r i m a r y i n d e x )
- i n d e k s z g r u p o w a n y ( a n g . c l u s t e r i n g i n d e x )
- i n d e k s w t r n y ( a n g . s e c o n d a r y i n d e x ) .
I n d e k s p o d s t a w o w y j e s t z a Bo |o n y n a a t r y b u c i e p o r z d k u j c y m i n d e k s o w a n e g o p l i k u .
A t r y b u t p o r z d k u j c y o k r e [l a p o r z d e k r e k o r d w w p l i k u . D l a i n d e k s u p o d s t a w o w e g o
a t r y b u t p o r z d k u j c y p r z y j m u j e w a r t o [c i u n i k a l n e .
I n d e k s z g r u p o w a n y j e s t z a k Ba d a n y r w n i e | n a a t r y b u c i e p o r z d k u j c y m , a l e w t y m
p r z y p a d k u j e g o w a r t o [c i n i e s u n i k a l n e .
I n d e k s w t r n y j e s t z a k Ba d a n y n a a t r y b u c i e , k t r y n i e j e s t a t r y b u t e m p o r z d k u j c y m p l i k u .
8
B a z y d a n y c h - B D
R o d z a j e i n d e k s w - w s k a z a n i a d o p l i k u
d a n y c h
" I n d e k s g s t y ( d e n s e )
p o s i a d a r e k o r d i n d e k s u d l a k a |d e g o r e k o r d u
i n d e k s o w a n e g o p l i k u d a n y c h
" I n d e k s r z a d k i ( s p a r s e )
p o s i a d a r e k o r d y t y l k o d l a w y b r a n y c h r e k o r d w
i n d e k s o w a n e g o p l i k u d a n y c h
B D w y k Ba d 7 ( 9 )
Z p u n k t u w i d z e n i a l i c z b y w s k a z a D i n d e k s u d o p l i k u d a n y c h w y r |n i a s i i n d e k s y g s t e
( a n g . d e n s e ) i i n d e k s y r z a d k i e ( a n g . s p a r s e ) . I n d e k s g s t y p o s i a d a r e k o r d i n d e k s u d l a
k a |d e g o r e k o r d u i n d e k s o w a n e g o p l i k u d a n y c h . I n d e k s r z a d k i p o s i a d a r e k o r d y t y l k o d l a
w y b r a n y c h r e k o r d w i n d e k s o w a n e g o p l i k u d a n y c h .
9
B a z y d a n y c h - B D
R o d z a j e i n d e k s w - l i c z b a p o z i o m w
" I n d e k s y j e d n o p o z i o m o w e
j e d e n p l i k i n d e k s u d l a j e d n e g o p l i k u d a n y c h
" I n d e k s y w i e l o p o z i o m o w e
i n d e k s d o i n d e k s u
B D w y k Ba d 7 ( 1 0 )
Z p u n k t u w i d z e n i a l i c z b y p o z i o m w i n d e k s u w y r |n i a s i i n d e k s y j e d n o p o z i o m o w e i
w i e l o p o z i o m o w e . W p i e r w s z y m p r z y p a d k u , d l a p l i k u d a n y c h j e s t t w o r z o n y t y l k o j e d e n
i n d e k s ( p l i k i n d e k s u ) . W d r u g i m p r z y p a d k u , d l a p l i k u d a n y c h t w o r z y s i i n d e k s ( j a k w
p r z y p a d k u p i e r w s z y m ) . D o d a t k o w o , d o i n d e k s u t w o r z y s i d o d a t k o w y i n d e k s .
1 0
B a z y d a n y c h - B D
I n d e k s p o d s t a w o w y
. . .
B D w y k Ba d 7 ( 1 1 )
I n d e k s p o d s t a w o w y j e s t i n d e k s e m r z a d k i m p o n i e w a | n i e w s z y s t k i e r e k o r d y p l i k u d a n y c h
p o s i a d a j r e k o r d y i n d e k s o w e . R e k o r d i n d e k s o w y i n d e k s u p o d s t a w o w e g o d l a w a r t o [c i X
z a w i e r a a d r e s b l o k u d a n y c h , w k t r y m z n a j d u j e s i r e k o r d d a n y c h z w a r t o [c i a t r y b u t u
i n d e k s o w e g o r w n X .
P o g l d o w s t r u k t u r i n d e k s u p o d s t a w o w e g o p r z e d s t a w i a s l a j d . J a k w i d a , w s k a z a n i a z
r e k o r d w i n d e k s o w y c h p r o w a d z d o b l o k w d a n y c h .
1 1
B a z y d a n y c h - B D
I n d e k s z g r u p o w a n y
B D w y k Ba d 7 ( 1 2 )
I n d e k s z g r u p o w a n y j e s t r w n i e | i n d e k s e m r z a d k i m p o n i e w a | n i e w s z y s t k i e r e k o r d y
p l i k u d a n y c h p o s i a d a j r e k o r d y i n d e k s o w e . R e k o r d i n d e k s o w y i n d e k s u z g r u p o w a n e g o
d l a w a r t o [c i X z a w i e r a a d r e s b l o k u d a n y c h , w k t r y m z n a j d u j e s i p i e r w s z y r e k o r d
d a n y c h z w a r t o [c i a t r y b u t u i n d e k s o w e g o r w n X . W i d a t o w y r a zn i e d l a w a r t o [c i 2
r e k o r d u i n d e k s u . R e k o r d t e n p o s i a d a w s k a z a n i e d o p i e r w s z e g o b l o k u d a n y c h - w b l o k u
t y m z n a j d u j e s i p i e r w s z y r e k o r d z w a r t o [c i 2 i n d e k s o w a n e g o a t r y b u t u .
T a k a o r g a n i z a c j a p l i k u p o w o d u j e p r o b l e m y z w s t a w i a n i e m i r e k o r d w , p o n i e w a |
p o r z d e k r e k o r d w p o w s t a w i e n i u m u s i p o z o s t a z a c h o w a n y .
1 2
B a z y d a n y c h - B D
I n d e k s z g r u p o w a n y z
b l o k a m i n a d m i a r o w y m i
b l o k
n a d m i a r o w y
B D w y k Ba d 7 ( 1 3 )
R o z w i z a n i e m t e g o p r o b l e m u j e s t p o p i e r w s z e , z a r e z e r w o w a n i e c a Be g o b l o k u n a r e k o r d y
z t s a m ( j e d n ) w a r t o [c i . P o d r u g i e , z a s t o s o w a n i e b l o k w n a d m i a r o w y c h , j a k
p o k a z u j e s l a j d . W s t a w i a n e r e k o r d y s u m i e s z c z a n e w w o l n y c h s z c z e l i n a c h b l o k u
g B w n e g o , a p o j e g o z a p e Bn i e n i u - w o d p o w i e d n i m b l o k u n a d m i a r o w y m , d o k t r e g o
p r o w a d z i w s k a zn i k z b l o k u g B w n e g o .
W p r z y k Ba d z i e z e s l a j d u , r e k o r d z w a r t o [c i 3 n i e m i e [c i s i w b l o k u g B w n y m , w i c j e s t
s k Ba d o w a n y w b l o k u n a d m i a r o w y m . Z b l o k u g B w n e g o p r z e c h o w u j c e g o r e k o r d y z
w a r t o [c i a t r y b u t u i n d e k s o w e g o r w n 3 p r o w a d z i w s k a zn i k d o b l o k u n a d m i a r o w e g o .
1 3
B a z y d a n y c h - B D
I n d e k s w t r n y
B D w y k Ba d 7 ( 1 4 )
I n d e k s w t r n y j e s t r w n i e | u p o r z d k o w a n y . J e s t o n z a k Ba d a n y n a a t r y b u c i e i n d e k s o w y m
p l i k u d a n y c h , k t r y n i e j e s t a t r y b u t e m p o r z d k u j c y m t e g o p l i k u . K a |d y r e k o r d p l i k u
d a n y c h p o s i a d a s w j o d p o w i e d n i k w r e k o r d z i e i n d e k s u . S t d , i n d e k s w t r n y j e s t
i n d e k s e m g s t y m .
R e k o r d i n d e k s u w t r n e g o s k Ba d a s i z d w c h p l : w a r t o [c i p o l a i n d e k s o w e g o i
w s k a zn i k a a l b o d o r e k o r d u a l b o d o b l o k u d a n y c h z a w i e r a j c e g o t e n r e k o r d .
N a s l a j d z i e p r z e d s t a w i o n o g s t y i n d e k s w t r n y z a Bo |o n y n a p o l u n i e p o r z d k u j c y m ,
k t r e g o w a r t o [c i s u n i k a l n e . R e k o r d y i n d e k s u p o s i a d a j w s k a zn i k i d o b l o k w d a n y c h .
1 4
B a z y d a n y c h - B D
I n d e k s o k l u c z u z Bo |o n y m
" K l u c z i n d e k s u m o |e z a w i e r a k i l k a a t r y b u t w - k l u c z
z Bo |o n y
I n d e k s < w i e k ; p e n s j a > I n d e k s < w i e k >
I n d e k s < p e n s j a ; w i e k > I n d e k s < p e n s j a >
B D w y k Ba d 7 ( 1 5 )
K l u c z i n d e k s u m o |e z a w i e r a k i l k a a t r y b u t w t a k i k l u c z n a z y w a m y k l u c z e m
z Bo |o n y m . W p r z y k Ba d z i e z e s l a j d u z d e f i n i o w a n o c z t e r y r |n e i n d e k s y . P i e r w s z y n a
k l u c z u z Bo |o n y m < w i e k , p e n s j a > , d r u g i n a k l u c z u z Bo |o n y m < p e n s j a , w i e k > , t r z e c i n a
k l u c z u < w i e k > , a c z w a r t y n a k l u c z u < p e n s j a > .
I n d e k s y n a k l u c z a c h z Bo |o n y c h s t o s u j e s i d o w y s z u k i w a n i a r e k o r d w s p e Bn i a j c y c h
w a r u n k i r w n o [c i o w e ( t z w . z a p y t a n i a p u n k t o w e ) n a Bo |o n e j e d n o c z e [n i e n a p o l a
w y s t p u j c e w k l u c z u z Bo |o n y m .
I n d e k s < w i e k , p e n s j a > b d z i e p r z y d a t n y d o w y s z u k i w a n i a r e k o r d w s p e Bn i a j c y c h
w a r u n k i r w n o [c i o w e n a Bo |o n e j e d n o c z e [n i e n a p o l e w i e k i n a p o l e p e n s j a . M o |e t e |
z o s t a w y k o r z y s t a n y p r z y w a r u n k a c h n a Bo |o n y c h n a i n n e p o l a , r a z e m z w a r u n k a m i
n a Bo |o n y m i n a w i e k i p e n s j . P o n a d t o , i n d e k s < w i e k , p e n s j a > m o |e z o s t a w y k o r z y s t a n y
d o w y s z u k i w a n i a r e k o r d w z w a r u n k i e m n a Bo |o n y m t y l k o n a p o l e w i e k .
I n d e k s t e n b d z i e j e d n a k n i e p r z y d a t n y d o p o s z u k i w a n i a r e k o r d w z w a r u n k a m i
n a Bo |o n y m i n a a t r y b u t p e n s j a , p o n i e w a | a t r y b u t e m w i o d c y m t e g o i n d e k s u j e s t w i e k . W
t a k i m p r z y p a d k u , m g Bb y z o s t a w y k o r z y s t a n y i n d e k s < p e n s j a , w i e k > .
Z t y c h p o w o d w , b a r d z i e j u n i w e r s a l n e s i n d e k s y z a k Ba d a n e n a p o j e d y n c z y c h
a t r y b u t a c h . S o n e j e d n a k m n i e j e f e k t y w n e o d i n d e k s w z Bo |o n y c h w p r z y p a d k u
w a r u n k w p o s z u k i w a n i a j e d n o c z e [n i e n a Bo |o n y c h n a i n d e k s o w a n e a t r y b u t y .
1 5
B a z y d a n y c h - B D
I n d e k s w i e l o p o z i o m o w y - I S A M
" I S A M - I n d e x e d S e q u e n t i a l A c c e s s M e t h o d ( I B M )
p o z i o m p i e r w s z y :
" i n d e k s c y l i n d r w < k l u c z , a d r e s i n d e k s u [c i e |k i )
p o z i o m d r u g i :
" i n d e k s [c i e |k i < k l u c z , a d r e s [c i e |k i >
s t r u k t u r a s i l n i e z w i z a n a z e s p r z t e m
" V S A M - V i r t u a l S e q u e n t i a l A c c e s s M e t h o d
r o z w i n i c i e I S A M
n i e z a l e |n e o d s p r z t u
B D w y k Ba d 7 ( 1 6 )
W y s z u k a n i e d a n y c h z w y k o r z y s t a n i e m i n d e k s u j e d n o p o z i o m o w e g o w y m a g a
p r z e s z u k a n i a p l i k u i n d e k s u . Z w y k o r z y s t a n i e m z n a l e z i o n y c h r e k o r d w i n d e k s u n a s t p u j e
o d c z y t a n i e r e k o r d w d a n y c h . N a l e |y z w r c i u w a g n a f a k t , |e p l i k i n d e k s u j e s t
p r z e s z u k i w a n y a l g o r y t m e m p o Bo w i e n i a b i n a r n e g o p o n i e w a | j e s t t o p l i k u p o r z d k o w a n y .
A l g o r y t m t e n n i e n a l e |y d o e f e k t y w n y c h . Z t e g o w z g l d u w p r o w a d z o n o i n d e k s y
w i e l o p o z i o m o w e , k t r y c h e f e k t y w n o [ p r z e s z u k i w a n i a j e s t w i k s z a .
J e d n z f u n d a m e n t a l n y c h k o n c e p c j i i n d e k s u w i e l o p o z i o m o w e g o j e s t s t r u k t u r a I S A M
( a n g . I n d e x e d S e q u e n t i a l A c c e s s M e t h o d ) , o r y g i n a l n i e o p r a c o w a n a p r z e z I B M .
K o n c e p c y j n i e s t r u k t u r a t a j e s t z b u d o w a n a z d w c h p o z i o m w . P o z i o m p i e r w s z y
i n d e k s u j e c y l i n d r y . R e k o r d y i n d e k s u n a t y m p o z i o m i e z a w i e r a j p a r y w a r t o [c i :
p o s z u k i w a n y k l u c z i a d r e s d o i n d e k s u [c i e |k i d y s k o w e j . P o z i o m d r u g i i n d e k s u j e [c i e |k i .
J e g o r e k o r d y z a w i e r a j p a r y w a r t o [c i : p o s z u k i w a n y k l u c z i a d r e s [c i e |k i . J a k w i d a , j e s t
t o s t r u k t u r a s i l n i e z w i z a n a z z a s t o s o w a n y m s p r z t e m k o m p u t e r o w y m .
R o z w i n i c i e m s t r u k t u r y I S A M j e s t V S A M ( a n g . V i r t u a l S e q u e n t i a l A c c e s s M e t h o d ) .
V S A M j e s t j u | n i e z a l e |n a o d r o z w i z a D s p r z t o w y c h .
1 6
B a z y d a n y c h - B D
I n d e k s w i e l o p o z i o m o w y - k o n c e p c j a o g l n a
i n d e k s p i e r w s z e g o
p o z i o m u
i n d e k s d r u g i e g o
p o z i o m u
B D w y k Ba d 7 ( 1 7 )
O g l n k o n c e p c j i n d e k s u w i e l o p o z i o m o w e g o p r z e d s t a w i o n o n a s l a j d z i e . I n d e k s n a
p i e r w s z y m p o z i o m i e a d r e s u j e b l o k i d a n y c h . K a |d y r e k o r d t e g o i n d e k s u z a w i e r a w a r t o [
p o l a i n d e k s o w e g o i a d r e s b l o k u d a n y c h , w k t r y m t a w a r t o [ s i z n a j d u j e . R e k o r d y t e g o
i n d e k s u s p r z e c h o w y w a n e w p l i k u u p o r z d k o w a n y m z g o d n i e z w a r t o [c i a m i k l u c z a
i n d e k s u p i e r w s z e g o p o z i o m u . R e k o r d y i n d e k s u d r u g i e g o p o z i o m u z a w i e r a j a d r e s y
b l o k w i n d e k s u p i e r w s z e g o p o z i o m u .
1 7
p l i k d a n y c h
B a z y d a n y c h - B D
I S A M
" I n d e k s s t a t y c z n y
m o d y f i k o w a n i e z a w a r t o [c i p l i k u d e g e n e r u j e i n d e k s -
s p a d a e f e k t y w n o [ d o s t p u d o d a n y c h
p o w s t a j p u s t e o b s z a r y p o u s u n i t y c h r e k o r d a c h
w s t a w i a n e r e k o r d y t r a f i a j d o b l o k w n a d m i a r o w y c h
B D w y k Ba d 7 ( 1 8 )
I S A M j e s t i n d e k s e m s t a t y c z n y m , c o o z n a c z a , |e n i e p o s i a d a z a a w a n s o w a n y c h
m e c h a n i z m w m o d y f i k o w a n i a s t r u k t u r y w s y t u a c j i z m o d y f i k o w a n i a z a w a r t o [c i
i n d e k s o w a n e g o p l i k u ( d o d a n i e , z m o d y f i k o w a n i e , u s u n i c i e r e k o r d u ) . U s u n i c i e r e k o r d u
p o w o d u j e p o w s t a n i e p u s t e g o m i e j s c a w b l o k u i n d e k s u . N o w e r e k o r d y s d o d a w a n e d o
b l o k w p r z e p e Bn i e n i a . W k o n s e k w e n c j i s t r u k t u r a i n d e k s u t y p u I S A M s t a j e s i
n i e e f e k t y w n a .
R o z w i z a n i e m t e g o p r o b l e m u j e s t w p r o w a d z e n i e i n d e k s w d y n a m i c z n y c h .
N a j p o w s z e c h n i e j s t o s o w a n y m i i n d e k s a m i d y n a m i c z n y m i s i n d e k s y d r z e w i a s t e , S -
d r z e w a , B - d r z e w a , B + - d r z e w a .
1 8
B a z y d a n y c h - B D
S t r u k t u r a d r z e w i a s t a
k o r z e D
p o z i o m 0
A
p o d d r z e w o w z B
w e w n t r z n y
B C D p o z i o m 1
E F G H I p o z i o m 2
l i [
J l i [ K p o z i o m 3
B D w y k Ba d 7 ( 1 9 )
N a s l a j d z i e p r z e d s t a w i o n o o g l n s t r u k t u r d r z e w i a s t . W y r |n i a s i w n i e j t z w . k o r z e D,
b d c y w i e r z c h o Bk i e m ( p u n k t e m w e j [c i a ) c a Be j s t r u k t u r y . N a s l a j d z i e k o r z e n i e m j e s t
w z e B A . Z k o r z e n i a p r o w a d z Bu k i , c z y l i w s k a z a n i a a l b o d o w z B w w e w n t r z n y c h
( w z By B i D n a r y s u n k u ) a l b o d o l i [c i ( w z e B C ) . W z e B w e w n t r z n y p o s i a d a w s k a z a n i a
d o i n n y c h w z B w . L i [ n i e p o s i a d a w s k a z a D d o i n n y c h w z B w . J e s t w i c e l e m e n t e m
k o Dc o w y m c a Be j s t r u k t u r y . P r z y k Ba d o w y i n d e k s z e s l a j d u s k Ba d a s i z 4 p o z i o m w . P r z y
c z y m k o r z e D z n a j d u j e s i n a p o z i o m i e 0 .
1 9
B a z y d a n y c h - B D
I n d e k s B + - d r z e w o
" Z r w n o w a |o n a s t r u k t u r a d r z e w i a s t a
w i e r z c h o Bk i w e w n t r z n e s Bu | d o w s p o m a g a n i a
w y s z u k i w a n i a
w i e r z c h o Bk i l i [c i z a w i e r a j r e k o r d y i n d e k s u z e
w s k a zn i k a m i d o r e k o r d w d a n y c h
" W c e l u z a p e w n i e n i a o d p o w i e d n i e j e f e k t y w n o [c i
r e a l i z a c j i z a p y t a D p r z e d z i a Bo w y c h w i e r z c h o Bk i l i [c i
s t a n o w i l i s t d w u k i e r u n k o w
B D w y k Ba d 7 ( 2 0 )
N a j p o w s z e c h n i e j s t o s o w a n y m d r z e w i a s t y m i n d e k s e m d y n a m i c z n y m j e s t B + - d r z e w o . J e s t
o n i m p l e m e n t o w a n y w e w s z y s t k i c h k o m e r c y j n y c h i n i e k o m e r c y j n y c h S Z B D . P o n a d t o
s t a n o w i p o d s t a w i m p l e m e n t a c j i i n n y c h i n d e k s w , t j . i n d e k s w b i t m a p o w y c h i
p o Bc z e n i o w y c h .
I n d e k s B + - d r z e w o j e s t z r w n o w a |o n s t r u k t u r d r z e w i a s t , w k t r e j w i e r z c h o Bk i
w e w n t r z n e s Bu | d o w s p o m a g a n i a w y s z u k i w a n i a , n a t o m i a s t w i e r z c h o Bk i l i [c i z a w i e r a j
r e k o r d y i n d e k s u z e w s k a zn i k a m i d o r e k o r d w w p l i k a c h d a n y c h . Z r w n o w a |e n i e
s t r u k t u r y o z n a c z a , |e o d l e g Bo [ ( l i c z b a p o z i o m w ) o d k o r z e n i a d o d o w o l n e g o l i [c i a j e s t
z a w s z e t a k a s a m a .
W c e l u z a p e w n i e n i a o d p o w i e d n i e j e f e k t y w n o [c i r e a l i z a c j i z a p y t a D p r z e d z i a Bo w y c h
w i e r z c h o Bk i l i [c i s t a n o w i l i s t d w u k i e r u n k o w .
2 0
B a z y d a n y c h - B D
I n d e k s B + - d r z e w o - c h a r a k t e r y s t y k a
" O p e r a c j e w s t a w i a n i a i u s u w a n i a r e k o r d w i n d e k s u
p o z o s t a w i a j i n d e k s z r w n o w a |o n y
" K a |d y w i e r z c h o Be k j e s t w y p e Bn i o n y w c o n a j m n i e j
5 0 % ( z a w y j t k i e m k o r z e n i a )
u s u w a n i e r e k o r d w m o |e s k u t k o w a m n i e j s z y m
w y p e Bn i e n i e m n i | 5 0 %
" W y s z u k a n i e r e k o r d u w y m a g a p r z e j [c i a o d k o r z e n i a
d o l i [c i a
d Bu g o [ [c i e |k i o d k o r z e n i a d o d o w o l n e g o l i [c i a
n a z y w a m y w y s o k o [c i d r z e w a i n d e k s u
" I n d e k s z r w n o w a |o n y
B D w y k Ba d 7 ( 2 1 )
N a j w a |n i e j s z a c h a r a k t e r y s t y k a i n d e k s u B + - d r z e w o j e s t n a s t p u j c a :
P o p i e r w s z e , o p e r a c j e w s t a w i a n i a i u s u w a n i a r e k o r d w i n d e k s u p o z o s t a w i a j i n d e k s
z r w n o w a |o n y m .
P o d r u g i e , k a |d y w i e r z c h o Be k j e s t w y p e Bn i o n y w c o n a j m n i e j 5 0 % ( z a w y j t k i e m
k o r z e n i a ) . O d s t p s t w o o d t e j r e g u By m o |e b y s p o w o d o w a n e o p e r a c j a m i u s u w a n i a
r e k o r d w . D l a o p e r a c j i u s u w a n i a , r e k o r d i n d e k s u j e s t u s u w a n y z i n d e k s u a l e w o l n e
m i e j s c e p o z o s t a j e w l i [c i u . W k o n s e k w e n c j i , w i e r z c h o Bk i l i [c i m o g b y w y p e Bn i o n e w
m n i e j n i | 5 0 % .
P o t r z e c i e , w y s z u k a n i e r e k o r d u w y m a g a p r z e j [c i a o d k o r z e n i a d o l i [c i a . D Bu g o [ [c i e |k i
o d k o r z e n i a d o d o w o l n e g o l i [c i a n a z y w a m y w y s o k o [c i d r z e w a i n d e k s u .
P o c z w a r t e , j a k w s p o m n i a n o , B + - d r z e w o j e s t i n d e k s e m z r w n o w a |o n y m .
2 1
B a z y d a n y c h - B D
S t r u k t u r a i n d e k s u B + d r z e w a
k o r z e D
4
x > 4
x < = 4
w z e B w e w n t r z n y
2 6 8
x < = 2 2 < x < = 4 4 < x < = 6 6 < x < = 8 8 < x
l i [c i e
1 2 3 4 5 6 7 8 9 1 0
B D w y k Ba d 7 ( 2 2 )
P r z y k Ba d o w y i n d e k s B + - d r z e w o p r z e d s t a w i o n o n a s l a j d z i e . S k Ba d a s i o n z t r z e c h
p o z i o m w : k o r z e n i a , w z B w w e w n t r z n y c h i l i [c i . W k o r z e n i u j e s t p r z e c h o w y w a n a
p e w n a w a r t o [ g r a n i c z n a k l u c z a i n d e k s u i w s k a zn i k i d o w z B w w e w n t r z n y c h . W
n a s z y m p r z y k Ba d z i e w a r t o [c i g r a n i c z n j e s t 4 , a k o r z e D z a w i e r a w s k a zn i k i d o d w c h
w z B w w e w n t r z n y c h . W w z Ba c h w e w n t r z n y c h s p r z e c h o w y w a n e r w n i e | p e w n e
w a r t o [c i g r a n i c z n e k l u c z a i n d e k s u i w s k a zn i k i d o l i [c i . L i [c i e z k o l e i p r z e c h o w u j p a r y :
< w a r t o [ k l u c z a i n d e k s u , w s k a zn i k d o r e k o r d u n a d y s k u > .
2 2
B a z y d a n y c h - B D
W z e B w e w n t r z n y ( 1 )
" S t r u k t u r a w z Ba w e w n t r z n e g o i n d e k s u B + - d r z e w o
r z d u p j e s t n a s t p u j c a
1 . W z e B w e w n t r z n y m a p o s t a :
< P 1 , K 1 , P 2 , . . . , P Q - 1 , K Q - 1 , P Q >
2 . D l a k a |d e g o w i e r z c h o Bk a w e w n t r z n e g o z a c h o d z i
K 1 < K 2 < . . . < K Q - 1
P 1 K 1 P 2 K 2 . . . . . . K Q - 1 P Q
B D w y k Ba d 7 ( 2 3 )
S t r u k t u r a w z Ba w e w n t r z n e g o i n d e k s u B + - d r z e w o r z d u p j e s t n a s t p u j c a .
1 . W z e B w e w n t r z n y m a n a s t p u j c p o s t a : w s k a zn i k d o w z Ba , w a r t o [ k l u c z a
i n d e k s u , k o l e j n y w s k a zn i k , k o l e j n a w a r t o [, i t d . L i c z b a w s k a zn i k w j e s t o j e d e n w i k s z a
o d l i c z b y w a r t o [c i k l u c z a .
< P 1 , K 1 , P 2 , . . . , P Q - 1 , K Q - 1 , P Q >
g d z i e Q < = p ; P i j e s t w s k a zn i k i e m d o p o d d r z e w a ; K i j e s t
w a r t o [c i k l u c z a i n d e k s u .
M a k s y m a l n a l i c z b a w s k a zn i k w j a k a m o |e z o s t a z a p i s a n a w w zl e j e s t n a z y w a n a
r z d e m B + - d r z e w a i j e s t o z n a c z a n a j a k o p .
2 . D l a k a |d e g o w i e r z c h o Bk a w e w n t r z n e g o z a c h o d z i :
K 1 < K 2 < . . . < K Q - 1
O z n a c z a t o , |e w a r t o [c i k l u c z a i n d e k s o w e g o s u p o r z d k o w a n e ( o d l e w e j - w a r t o [c i
n a j m n i e j s z e d o p r a w e j - w a r t o [c i n a j w i k s z e ) .
2 3
B a z y d a n y c h - B D
W z e B w e w n t r z n y ( 2 )
3 . D l a d a n e j w a r t o [c i K i k l u c z a w w zl e z e w n t r z n y m
l e w y w s k a zn i k p r o w a d z i d o p o d d r z e w a
z a w i e r a j c e g o w a r t o [c i p o s z u k i w a n e < = K i
p r a w y w s k a zn i k p r o w a d z i d o p o d d r z e w a
z a w i e r a j c e g o w a r t o [c i p o s z u k i w a n e > K i
P 1 K 1 . . . P i - 1 K i P i . . . P Q
w a r t o [c i p o s z u k i w a n e x < = K i
w a r t o [c i p o s z u k i w a n e x > K i
B D w y k Ba d 7 ( 2 4 )
3 . D l a d a n e j w a r t o [c i K i k l u c z a w w zl e w e w n t r z n y m , l e w y w s k a zn i k p r o w a d z i d o
p o d d r z e w a z a w i e r a j c e g o w a r t o [c i p o s z u k i w a n e < = K i , a p r a w y w s k a zn i k p r o w a d z i d o
p o d d r z e w a z a w i e r a j c e g o w a r t o [c i p o s z u k i w a n e > K i , j a k p o k a z a n o n a s l a j d z i e .
2 4
B a z y d a n y c h - B D
W z e B w e w n t r z n y ( 3 )
4 . K a |d y w i e r z c h o Be k w e w n t r z n y p o s i a d a c o
n a j w y |e j p w s k a zn i k w d o p o d d r z e w
5 . K a |d y w i e r z c h o Be k w e w n t r z n y , z a w y j t k i e m
k o r z e n i a , p o s i a d a c o n a j m n i e j #( p / 2 ) # w s k a zn i k w
d o p o d d r z e w
" k o r z e D p o s i a d a c o n a j m n i e j 2 w s k a zn i k i d o
p o d d r z e w
6 . K a |d y w i e r z c h o Be k w e w n t r z n y o Q w s k a zn i k a c h
p o s i a d a Q - 1 w a r t o [c i k l u c z y
B D w y k Ba d 7 ( 2 5 )
4 . K a |d y w i e r z c h o Be k w e w n t r z n y p o s i a d a c o n a j w y |e j p w s k a zn i k w d o p o d d r z e w .
5 . D l a k a |d e g o w i e r z c h o Bk a w e w n t r z n e g o l i c z b a w s k a zn i k w d o p o d d r z e w j e s t
o k r e [l o n a j a k o n a j m n i e j s z a l i c z b a c a Bk o w i t a w i k s z a l u b r w n a p o Bo w i e r z d u d r z e w a .
K o r z e D p o s i a d a c o n a j m n i e j 2 w s k a zn i k i d o p o d d r z e w .
6 . K a |d y w i e r z c h o Be k w e w n t r z n y o Q w s k a zn i k a c h p o s i a d a Q - 1 w a r t o [c i k l u c z y .
2 5
B a z y d a n y c h - B D
W i e r z c h o Be k w e w n t r z n y ( 4 )
P 1 K 1 . . . K i - 1 P i K i K Q - 1 P Q
x < = K i K i - 1 < x < = K i K Q - 1 < x
B D w y k Ba d 7 ( 2 6 )
P o d s u m o w a n i e s t r u k t u r y w i e r z c h o Bk a w e w n t r z n e g o p r z e d s t a w i o n o n a s l a j d z i e .
2 6
B a z y d a n y c h - B D
L i [ ( 1 )
S t r u k t u r a l i [c i a i n d e k s u B + - d r z e w o r z d u p j e s t
n a s t p u j c a :
1 . L i [ m a p o s t a :
< < K 1 , P r 1 > , < K 2 , P r 2 > , . . . , < K k , P k > , P n e x t >
2 . D l a k a |d e g o w i e r z c h o Bk a l i [c i a z a c h o d z i :
K 1 < K 2 < . . . < K k
K 1 P 1 K 2 P 2 . . . K n P n P n e x t
B D w y k Ba d 7 ( 2 7 )
S t r u k t u r a l i [c i a i n d e k s u B + - d r z e w o r z d u p j e s t n a s t p u j c a :
1 . L i [ m a p o s t a :
- z b i r p a r : w a r t o [ k l u c z a i n d e k s u , w s k a zn i k d o r e k o r d u ( b l o k u d a n y c h ) z t w a r t o [c i
k l u c z a ( o z n a c z o n e j a k o K k , P k )
< K 1 , P 1 > , < K 2 , P 2 > , . . . , < K k , P k > , P n e x t >
K 1 , K 2 , . . . , K k s w a r t o [c i a m i k l u c z a i n d e k s u ;
P 1 , P 2 , . . . , P k s w s k a zn i k a m i d o r e k o r d w n a d y s k u l u b d o b l o k w d a n y c h ;
- w s k a zn i k d o n a s t p n e g o l i [c i a .
W i n d e k s a c h t y p u B * - d r z e w o , k a |d y l i [ m a d o d a t k o w o w s k a zn i k d o p o p r z e d n i e g o
l i [c i a .
2 . D l a k a |d e g o w i e r z c h o Bk a l i [c i a z a c h o d z i :
K 1 < K 2 < . . . < K Q - 1
O z n a c z a t o , |e w a r t o [c i k l u c z a i n d e k s o w e g o s u p o r z d k o w a n e ( o d l e w e j - w a r t o [c i
n a j m n i e j s z e d o p r a w e j - w a r t o [c i n a j w i k s z e ) .
2 7
B a z y d a n y c h - B D
L i [ ( 2 )
3 . K a |d y l i [ p o s i a d a c o n a j m n i e j #( p / 2 ) # w a r t o [c i k l u c z y
4 . W s z y s t k i e l i [c i e z n a j d u j s i n a t y m s a m y m p o z i o m i e
( t e j s a m e j w y s o k o [c i )
B D w y k Ba d 7 ( 2 8 )
3 . D l a k a |d e g o l i [c i a m i n i m a l n a l i c z b a w a r t o [c i k l u c z y i n d e k s u j e s t o k r e [l o n a j a k o
n a j w i k s z a l i c z b a c a Bk o w i t a m n i e j s z a l u b r w n a p o Bo w i e r z d u d r z e w a .
4 . W s z y s t k i e l i [c i e z n a j d u j s i n a t y m s a m y m p o z i o m i e ( t e j s a m e j w y s o k o [c i ) .
2 8
B a z y d a n y c h - B D
O b l i c z e n i e r z d u i n d e k s u
" D a n e : r o z m i a r k l u c z a V ; r o z m i a r w s k a zn i k a d o b l o k u
P ; r o z m i a r b l o k u B ; l i c z b a r e k o r d w w i n d e k s o w a n y m
p l i k u d a n y c h r ; l i c z b a b l o k w p l i k u b
" W z By w e w n t r z n e z a w i e r a j m a k s y m a l n i e p
w s k a zn i k w i p - 1 k l u c z y
" K a |d y z w z B w m u s i z m i e [c i s i w p o j e d y n c z y m
b l o k u d y s k o w y m - r z d B + - d r z e w a p j e s t n a j w i k s z
l i c z b c a Bk o w i t , d l a k t r e j s p e Bn i o n a j e s t n i e r w n o [:
1
( p "P ) + ( ( p - 1 ) "V ) ) d" B
2
" M i n i m a l n a w y s o k o [ i n d e k s u r z a d k i e g o : h = #l o g p b #
" M i n i m a l n a w y s o k o [ i n d e k s u g s t e g o : h = #l o g p r #
3
B D w y k Ba d 7 ( 2 9 )
P r z e d s t a w i o n y z o s t a n i e t e r a z t o k r o z u m o w a n i a p r o w a d z c y d o o b l i c z e n i a r z d u i n d e k s u .
P r z y p o m i n a m y , |e r z d i n d e k s u o z n a c z a m y j a k o p .
P r z y j m i j m y , |e : V o z n a c z a r o z m i a r k l u c z a i n d e k s u ; P o z n a c z a r o z m i a r w s k a zn i k a d o
b l o k u ; B o z n a c z a r o z m i a r b l o k u d a n y c h ( d y s k o w e g o ) ; r o z n a c z a l i c z b i n d e k s o w a n y c h
r e k o r d w w p l i k u d a n y c h ; b o z n a c z a l i c z b b l o k w p l i k u d a n y c h .
P a m i t a m y , |e w z By w e w n t r z n e z a w i e r a j m a k s y m a l n i e p w s k a zn i k w i p - 1 k l u c z y .
P o n i e w a | k a |d y w z e B m u s i s i z m i e [c i w p o j e d y n c z y m b l o k u d y s k o w y m , w i c r z d
B + - d r z e w a j e s t n a j w i k s z l i c z b c a Bk o w i t s p e Bn i a j c n i e r w n o [ z e s l a j d u ( o z n a c z o n
s y m b o l e m 1 ) .
Z i n n y c h p r z y d a t n y c h w z o r w w y m i e n i n a l e |y w z o r y o b l i c z a j c e m i n i m a l n w y s o k o [
i n d e k s u r z a d k i e g o ( w z r 2 ) i m i n i m a l n w y s o k o [ i n d e k s u g s t e g o ( w z r 3 ) ,
p r z e d s t a w i o n e n a s l a j d z i e .
2 9
B a z y d a n y c h - B D
O b l i c z e n i e r z d u i n d e k s u - p r z y k Ba d ( 1 )
D a n e :
R o z m i a r p l i k u : r = 3 0 0 0 0 r e k o r d w
R o z m i a r b l o k u : B = 1 0 2 4 B
R o z m i a r r e k o r d u : R = 1 0 0 b a j t w
R o z m i a r k l u c z a : V = 9
R o z m i a r w s k a zn i k a : P = 6
R e k o r d y m a j s t a B d Bu g o [ i n i e s d z i e l o n e m i d z y b l o k i
I n d e k s w t r n y 1
B 1 0 2 4
# # # #
L i c z b a r e k o r d w w b l o k u : r b l = = = 1 0
# # # #
R 1 0 0
# # # #
2
r 3 0 0 0 0
# # # #
b = = = 3 0 0 0
L i c z b a b l o k w d a n y c h :
#r b l # # #
1 0
# # # #
B D w y k Ba d 7 ( 3 0 )
R o z w a |m y n a s t p u j c y p r z y k Ba d i l u s t r u j c y s p o s b o b l i c z a n i a r z d u B + - d r z e w a .
N i e c h : l i c z b a i n d e k s o w a n y c h r e k o r d w d a n y c h w y n o s i r = 3 0 0 0 0 , r o z m i a r b l o k u w y n o s i
B = 1 k B , r o z m i a r r e k o r d u w y n o s i R = 1 0 0 B , r o z m i a r k l u c z a i n d e k s u w y n o s i V = 9 B i
r o z m i a r w s k a zn i k a w y n o s i P = 6 B .
P r z y j m u j e m y p o n a d t o , |e r e k o r d y m a j s t a B d Bu g o [ i n i e s d z i e l o n e m i d z y b l o k i . N a
p l i k u d a n y c h j e s t z a k Ba d a n y i n d e k s w t r n y .
P o n i e w a | r e k o r d y m a j s t a B d Bu g o [ i n i e s d z i e l o n e m i d z y b l o k i , l i c z b r e k o r d w w
b l o k u o b l i c z y m y z a p o m o c w z o r u 1 .
L i c z b b l o k w d a n y c h d o s k Ba d o w a n i a 3 0 0 0 0 r e k o r d w o b l i c z y m y z a p o m o c w z o r u 2 .
3 0
B a z y d a n y c h - B D
O b l i c z e n i e r z d u i n d e k s u - p r z y k Ba d ( 2 )
4
R z d w z Ba
3
V + B
( p * P ) + [ ( p - 1 ) * V ] d" B p d"
P + V
M i n i m a l n a w y s o k o [ i n d e k s u :
5
h = 9 + 1 0 2 4
#l o g r #
p
p d"
6 + 9
p = 6 8
h = = 3
#l o g 3 0 0 0 0 #
6 8
B D w y k Ba d 7 ( 3 1 )
R z d w z Ba o b l i c z a m y p r z e k s z t a Bc a j c w z r 3 z e s l a j d u d o w z o r u 4 . P o p o d s t a w i e n i u
w a r t o [c i d o w z o r u 4 o t r z y m u j e m y w y n i k : r z d w z Ba w e w n t r z n e g o p = 6 8 . Z
w y k o r z y s t a n i e m o b l i c z o n e j w a r t o [c i r z d u w z Ba m o |e m y n a s t p n i e o b l i c z y m i n i m a l n
w y s o k o [ i n d e k s u n i e z b d n d o p o i n d e k s o w a n i a 3 0 0 0 0 r e k o r d w d a n y c h .
W y k o r z y s t u j e m y d o t e g o c e l u w z r 5 . P o p o d s t a w i e n i u d a n y c h , o t r z y m u j e m y w y n i k -
i n d e k s m u s i m i e p r z y n a j m n i e j 3 p o z i o m y .
3 1
B a z y d a n y c h - B D
P r z y k Ba d
" K o s z t w y s z u k a n i a r e k o r d u b e z p o m o c y i n d e k s u
[r e d n i o : l i c z b a b l o k w d a n y c h / 2 = 1 5 0 0 d o s t p w
" K o s z t w y s z u k i w a n i a r e k o r d u z a p o m o c i n d e k s u t y p u
B + - d r z e w o :
r w n y : w y s o k o [ d r z e w a + 1 = 3 + 1 = 4 d o s t p y
B D w y k Ba d 7 ( 3 2 )
J a k Ba t w o d o w i e z a n a l i t y c z n i e , i n d e k s B + - d r z e w o z n a k o m i c i e p r z y s p i e s z a
w y s z u k i w a n i e r e k o r d u z p l i k u , w p o r w n a n i u z d o s t p e m d o p l i k u b e z i n d e k s u . J e |e l i w
p l i k u j e s t w y s z u k i w a n y r e k o r d z k r y t e r i u m n a Bo |o n y m n a a t r y b u t n i e p o r z d k u j c y ,
w w c z a s n a l e |y p r z e s z u k a c a By p l i k . Zr e d n i o b d z i e t o w y m a g a Bo o d c z y t a n i a p o Bo w y
b l o k w p r z e c h o w u j c y c h r e k o r d y d a n y c h , c z y l i w n a s z y m p r z y k Ba d z i e 1 5 0 0 .
W p r z y p a d k u i n d e k s u B + - d r z e w o n a l e |y z n a l e z o d p o w i e d n i l i [ i s i g n p o r e k o r d d o
d y s k u . Z n a l e z i e n i e l i [c i a w y m a g a o d c z y t a n i a 3 b l o k w i n d e k s u - k o r z e n i a , w z Ba
w e w n t r z n e g o i l i [c i a . K o r z y s t a j c z e w s k a zn i k a w l i [c i u , n a l e |y o d c z y t a j e d e n b l o k
d a n y c h z a w i e r a j c y p o s z u k i w a n y r e k o r d . Z n a l e z i e n i e r e k o r d u b d z i e w i c w y m a g a Bo 4
d o s t p w d o d y s k u .
3 2
B a z y d a n y c h - B D
W s t a w i a n i e d a n y c h d o i n d e k s u -
p r z y k Ba d ( 1 )
" Z a Bo |e n i a
i n d e k s B + - d r z e w o
r z d d r z e w a : 3
s e k w e n c j a d a n y c h w s t a w i a n y c h d o i n d e k s u :
" 8 , 5 , 1 , 7 , 3 , 1 2 , 9 , 6
5 8
" W s t a w i e n i e 8 i 5 d a j e l i [
5
1 5 8
5 8
w s t a w 1 p r z e p e Bn i e n i e , p o d z i a B,
1 5 8
p r o p a g a c j a
1
d o l e w e g o l i [c i a d o p r a w e g o l i [c i a B D w y k Ba d 7 ( 3 3 )
Z a r z d z a n i e s t r u k t u r i n d e k s u B + - d r z e w o w s y t u a c j a c h w s t a w i a n i a , u s u w a n i a i
m o d y f i k o w a n i a w a r t o [c i a t r y b u t u i n d e k s o w e g o r e k o r d w d a n y c h j e s t r e a l i z o w a n e z a
p o m o c s p e c j a l i z o w a n y c h a l g o r y t m w . N a k i l k u k o l e j n y c h s l a j d a c h p r z e d s t a w i m y i d e
d z i a Ba n i a a l g o r y t m u m o d y f i k o w a n i a s t r u k t u r y i n d e k s u n a s k u t e k w s t a w i a n i a r e k o r d w
d a n y c h .
D l a u p r o s z c z e n i a p r z y j m i j m y , |e i n d e k s j e s t r z d u 3 . O z n a c z a t o , |e k a |d y w z e B p o s i a d a
m i n i m a l n i e 2 i m a k s y m a l n i e 3 w s k a zn i k i . L i [ p o s i a d a o d 1 d o d w c h w a r t o [c i a t r y b u t u
i n d e k s o w e g o . D o i n d e k s u s w s t a w i a n e n a s t p u j c e w a r t o [c i w k o l e j n o [c i i c h
w y m i e n i e n i a : 8 , 5 , 1 , 7 , 3 , 1 2 , 9 , 6 .
W s t a w i o n e w a r t o [c i 8 i 5 m i e s z c z s i w j e d n y m b l o k u i n d e k s u , w i c w y s t a r c z y j e
p r z e c h o w a j a k o l i [.
W s t a w i e n i e w a r t o [c i 1 d o w z Ba s p o w o d o w a Bo b y j e g o p r z e p e Bn i e n i e . Z t e g o p o w o d u
w z e B j e s t r o z b i j a n y n a 2 . W t y m c e l u p o r z d k u j e m y w a r t o [c i i s t n i e j c e w w zl e i
w a r t o [ w s t a w i a n , o d l e w e j ( n a j m n i e j s z a ) d o p r a w e j ( n a j w i k s z a ) . W a r t o [ [r o d k o w ,
c z y l i 5 , p r z e n o s i m y d o p o z i o m u w y |s z e g o - s t a j e s i o n a w a r t o [c i w k o r z e n i u . W a r t o [c i
1 i 5 t r a f i a j d o l e w e g o l i [c i a , a 8 - d o p r a w e g o , j a k p o k a z a n o n a s l a j d z i e .
3 3
B a z y d a n y c h - B D
W s t a w i a n i e d a n y c h d o i n d e k s u -
p r z y k Ba d ( 2 )
5 5
1 5 8 1 5 7 8
w s t a w 7 p o s o r t u j w s t a w 3 p r z e p e Bn i e n i e ,
7 3
w a r t o [c i w t y m l i [c i u p o d z i a B, p r o p a g a c j a
1 3 5
3 5
d o l e w e g o
l i [c i a
1 3 5 7 8
d o p r a w e g o l i [c i a
B D w y k Ba d 7 ( 3 4 )
W a r t o [ 7 m u s i b y w s t a w i o n a d o p r a w e g o l i [c i a , k t r y p o s i a d a m i e j s c e n a j e d n
w a r t o [. W a r t o [c i w t y m l i [c i u n a l e |y p o s o r t o w a .
W a r t o [ 3 m u s i b y w s t a w i o n a d o l e w e g o l i [c i a . J e d n a k j e s t o n j u | w c a Bo [c i z a j t y . Z
t e g o p o w o d u w z e B j e s t r o z b i j a n y n a 2 . W t y m c e l u p o r z d k u j e m y w a r t o [c i i s t n i e j c e w
w zl e i w a r t o [ w s t a w i a n , o d l e w e j ( n a j m n i e j s z a ) d o p r a w e j ( n a j w i k s z a ) . W a r t o [
[r o d k o w , c z y l i 3 , p r z e n o s i m y d o k o r z e n i a . W a r t o [c i 1 i 3 t r a f i a j d o l e w e g o l i [c i a , a 5 -
d o p r a w e g o , j a k p o k a z a n o n a s l a j d z i e .
3 4
B a z y d a n y c h - B D
W s t a w i a n i e d a n y c h d o i n d e k s u - d o n o w e g o
k o r z e n i a
p r z y k Ba d ( 3 )
3 5 8
3 5
d o p r a w e g o
d o l e w e g o
p o d d r z e w a
p o d d r z e w a
1 3 5 7 8
7 8 1 2
w s t a w 1 2 p r z e p e Bn i e n i e ,
1 2
p o d z i a B, p r o p a g a c j a
d o p r a w e g o
5
l i [c i a
d o l e w e g o
l i [c i a
3 8
1 3 5 7 8 1 2
B D w y k Ba d 7 ( 3 5 )
W a r t o [ 1 2 m u s i b y w s t a w i o n a d o s k r a j n i e p r a w e g o l i [c i a . J e d n a k j e s t o n j u | w c a Bo [c i
z a j t y . Z t e g o p o w o d u w z e B j e s t r o z b i j a n y n a 2 . W t y m c e l u p o r z d k u j e m y w a r t o [c i
i s t n i e j c e w w zl e i w a r t o [ w s t a w i a n , o d l e w e j ( n a j m n i e j s z a ) d o p r a w e j ( n a j w i k s z a ) .
W a r t o [ [r o d k o w , c z y l i 8 , p r z e n o s i m y d o k o r z e n i a . W a r t o [c i 7 i 8 t r a f i a j d o l e w e g o
l i [c i a , a 1 2 - d o p r a w e g o , j a k p o k a z a n o n a s l a j d z i e .
P o n a d t o , w t y m p r z y p a d k u w a r t o [ 8 p o w i n n a t r a f i d o k o r z e n i a , k t r y j e s t j u | w c a Bo [c i
w y p e Bn i o n y . Z t e g o w z g l d u u l e g a o n r o z b i c i u n a n o w y k o r z e D i d w a w z By w e w n t r z n e .
W t y m c e l u p o r z d k u j e m y w a r t o [c i j u | p r z e c h o w y w a n e w k o r z e n i u i w s t a w i a n d o
n i e g o w a r t o [, j a k p o k a z a n o n a s l a j d z i e . W a r t o [ [r o d k o w a , c z y l i 5 t r a f i a d o n o w e g o
k o r z e n i a . W a r t o [ 3 t r a f i a d o l e w e g o p o d d r z e w a , a w a r t o [ 8 - d o p r a w e g o , j a k p o k a z a n o
n a s l a j d z i e .
3 5
B a z y d a n y c h - B D
W s t a w i a n i e d a n y c h d o i n d e k s u -
p r z y k Ba d ( 4 )
5
3 8
1 3 5 7 8 1 2
w s t a w 9 p o s o r t u j
9
5
w a r t o [c i w t y m l i [c i u
3 8
1 3 5 7 8 9 1 2
B D w y k Ba d 7 ( 3 6 )
W a r t o [ 9 m u s i b y w s t a w i o n a d o s k r a j n i e p r a w e g o l i [c i a , k t r y p o s i a d a m i e j s c e n a
j e d n w a r t o [. W a r t o [c i w t y m l i [c i u n a l e |y p o s o r t o w a .
3 6
B a z y d a n y c h - B D
W s t a w i a n i e d a n y c h d o i n d e k s u -
p r z y k Ba d ( 5 )
5
3 8
d o w z Ba
1 3 5 7 8 9 1 2
w e w n t r z n e g o
6
6 7 8
w s t a w 6 p r z e p e Bn i e n i e ,
p o d z i a B, p r o p a g a c j a
d o p r a w e g o
d o l e w e g o
l i [c i a
l i [c i a
B D w y k Ba d 7 ( 3 7 )
W a r t o [ 6 m u s i b y w s t a w i o n a d o t r z e c i e g o o d l e w e j l i [c i a . J e d n a k j e s t o n j u | w c a Bo [c i
z a j t y . Z t e g o p o w o d u w z e B j e s t r o z b i j a n y n a 2 . W t y m c e l u p o r z d k u j e m y w a r t o [c i
i s t n i e j c e w w zl e i w a r t o [ w s t a w i a n , o d l e w e j ( n a j m n i e j s z a ) d o p r a w e j ( n a j w i k s z a ) .
W a r t o [ [r o d k o w , c z y l i 7 , p r z e n o s i m y d o w z Ba w e w n t r z n e g o . W a r t o [c i 6 i 7 t r a f i a j
d o l e w e g o l i [c i a , a 8 - d o p r a w e g o , j a k p o k a z a n o n a s l a j d z i e .
3 7
B a z y d a n y c h - B D
W s t a w i a n i e d a n y c h d o i n d e k s u -
p r z y k Ba d ( 6 )
5
3 7 8
1 3 5 6 7 8 9 1 2
B D w y k Ba d 7 ( 3 8 )
O s t a t e c z n a s t r u k t u r a i n d e k s u z o s t a Ba p r z e d s t a w i o n a n a s l a j d z i e .
3 8
Wyszukiwarka
Podobne podstrony:
Wyklad 9 Jezyk SQL obsluga struktury?zy?nych indeksy widokiSieci komputerowe wyklady dr FurtakWykład 05 Opadanie i fluidyzacjaWYKŁAD 1 Wprowadzenie do biotechnologii farmaceutycznejmo3 wykladyJJZARZĄDZANIE WARTOŚCIĄ PRZEDSIĘBIORSTWA Z DNIA 26 MARZEC 2011 WYKŁAD NR 3Wyklad 2 PNOP 08 9 zaoczneWyklad studport 8Kryptografia wykladBudownictwo Ogolne II zaoczne wyklad 13 ppozwyklad09Sporzadzanie rachunku przepływów pienieżnych wykład 1 i 2więcej podobnych podstron