GT CSDL – Chng 5. Lu tr và cu trúc tp tin
NTD – Khoa Tin – HSP Hu
1

MC LC

CHNG V. LU TR VÀ CU TRÚC TP TIN 2
Mc ích: 2
Yêu cu: 2
5.1. B qun tr buffer 3
5.2. Cách thc t chc file 4
5.2.1. Mu tin vi  dài c nh (Fixed-Length Records) 4
5.2.2. Mu tin vi  dài thay i (Variable-Length Records) 5
5.3. T chc các mu tin trong file 6
5.3.1. T chc file tun t 7
5.3.2. T chc file cm 7
5.3.3. Lu tr t in d liu 8
5.4. Ch mc 8
5.4.1. Ch mc c sp. 9
5.4.2. Ch mc th cp 12
5.5. File ch mc B
+
-CÂY (B
+
-Tree Index file) 13
5.5.1. Cu trúc c a B
+
-cây 13
5.5.2. Các vn tin trên B
+
-cây 14

tree), bm (hashing) Các thit b lu tr (a) có th b
hng hóc không lng trc, các k thut RAID cho mt gii pháp hiu qu cho
vn  này.
Yêu cu:
- Hiu rõ các c im ca các thit b lu tr, cách t chc lu tr, truy
xut a.
- Các k thut t chc các mu tin trong file, các k thut t chc file.
- Hiu và vn dng các k thut h tr truy cp thông tin: ch mc (th t,
B
+
cây, bm.)

 tìm hiu tt phn này, b'n cn nh mt s phn trong môn h#c h i(u
hành và kin trúc máy tính, c)ng nh môn h#c bo trì h thng. Các k* thut liên
quan n các phng tin lu tr ngoài (b nh ngoài), các vn ( v( b nh m
(buffer), cách truy xut #c ghi I/O và chi phí CPU khi truy xut d liu, các khái
nim phân trang – phân o'n… có th #c thêm trong các tài liu liên quan các
môn h#c nói trên.
Mt c s+ d liu c ánh x' vào mt s các file khác nhau c duy trì
b+i h i(u hành n(n. Các file này lu trú th,ng trc trên các "a vi backup trên
b!ng. M-i file c phân ho'ch thành các n v lu tr  dài c nh c g#i
là khi - n v cho c cp phát lu tr và truy(n d liu.
Mt khi có th cha mt vài h'ng mc d liu (data item). Ta gi thit
không mt h'ng mc d liu nào tri ra trên hai khi. Mt cách  gim s truy
xut "a là gi nhi(u khi có th c trong b nh chính. Mc ích là  khi mt
khi c truy xut, nó ã n.m s/n trong b nh chính và nh vy không cn mt
truy xut "a nào c.
Do không th lu tt c các khi trong b nh chính, ta cn qun tr cp phát
không gian s/n có trong b nh chính  lu tr các khi. B m (Buffer) là mt
phn c a b nh chính s/n có  lu tr bn sao khi "a. Luôn có mt bn sao

do c a yêu cu xut ra bt buc khi là ni dung c a b nh chính s4 b mt khi có
s c, ngc l'i d liu trên "a thì không.
Các  i sách thay th buffer (buffer-replacement policies).
Mc ích c a chin lc thay th khi trong buffer là ti thiu hoá các truy
xut "a. Các h i(u hành th,ng s0 dng chin lc LRU  thay th khi. Tuy
nhiên, mt h CSDL có th d oán d liu có th cn #c trong tng lai. Yêu
cu c a mt ng,i s0 dng i vi h CSDL bao g2m mt s bc. H CSDL có
th xác nh trc nhng khi nào s4 là cn thit b.ng cách xem xét m-i mt trong
các bc c yêu cu  thc hin ho't ng c yêu cu b+i ng,i s0 dng.
Nh vy, khác vi h i(u hành, h CSDL có th có thông tin liên quan n tng
lai, chí ít là tng lai gn. Trong nhi(u tr,ng hp, chin lc thay th khi ti u
cho h CSDL là MRU (Most Recently Used): Khi b thay th s4 là khi mi
c dùng gn ây nht!
B qun tr buffer s0 dng các thông tin thng kê liên quan n xác sut mt
yêu cu s4 tham kho mt d liu riêng bit nào ó. Ch5ng h'n, t in d liu và
các ch mc là mt trong nhng phn c truy xut th,ng xuyên nht c a
CSDL. Do ó, b qun tr buffer s4 không xoá các khi t in d liu, ch mc
kh3i b nh chính tr phi các nhân t khác bc ch làm i(u ó.
GT CSDL – Chng 5. Lu tr và cu trúc tp tin
NTD – Khoa Tin – HSP Hu
4

Trong b qun tr buffer còn có các h con nh.m i(u khin tng tranh vì
tt nhiên s4 có nhi(u khi cùng truy cp lên b nh m. Các k* thut i(u khin
tng tranh có th xem thêm trong phn i(u khin tng tranh + phn sau và
trong môn h#c h i(u hành.
Bên c'nh ó, các h thng khôi phc (crash-recovery subsystem) s4 áp 6t
các ràng buc nghiêm nh6t lên vic thay th khi. Nu mt khi b s0a i, b
qun tr buffer không c phép vit l'i phiên bn mi c a khi trong buffer lên
"a, vì nó s4 phá hu7 phiên bn c). Thay vào ó, phi xem xét quy(n vit l'i t h

nht, trong ni dung c a mu tin này có cha a ch c a mu tin b xoá th hai và
c nh vy. Nh vy, các mu tin b xoá s4 t'o ra mt danh sách liên kt dc g#i
là danh sách t do (free list). Khi chèn mu tin mi, ta s0 dng con tr3 u danh
GT CSDL – Chng 5. Lu tr và cu trúc tp tin
NTD – Khoa Tin – HSP Hu
5

sách c cha trong header  xác nh danh sách, nu danh sách không r-ng ta
chèn mu tin mi vào vùng c tr3 b+i con tr3 u danh sách nu không ta chèn
mu tin mi vào cui file.
Chèn và xoá i vi file mu tin  dài c nh c thc hin n gin vì
không gian c gii phóng b+i mu tin b xoá úng b.ng không gian cn thit 
chèn mt mu tin. i vi file c a các mu tin  dài thay i vn ( tr+ nên phc
t'p hn nhi(u.
5.2.2. Mu tin vi  dài thay i (Variable-Length Records)
Mu tin trong 1 file có  dài thay i do mt s lý do sau:
- Vic lu tr nhi(u kiu mu tin trong mt file.
- Kiu mu tin cho phép  dài tr,ng thay i.
- Kiu mu tin cho phép l6p l'i các tr,ng.
Có nhi(u k* thut  thc hin mu tin  dài thay i.  minh ho' ta xét
các biu di9n khác nhau trên các mu tin  dài thay i có nh d'ng sau:
Biu din chui byte (Byte-String Representation).
Mt cách n gin  thc hin các mu tin  dài thay i là gn mt ký
hiu 6c bit End-of-record (⊥) vào cui m-i record. Khi ó có th lu m-i mu
tin nh mt chu-i byte liên tip. Thay vì s0 dng mt ký hiu 6c bit + cui c a
m-i mu tin, mt phiên bn c a biu di9n chu-i byte là lu tr  dài mu tin +
bt u c a m-i mu tin.
Biu di9n chu-i byte có mt s h'n ch sau:
- Khó s0 dng không gian b chim hình thc b+i mt mu tin b xoá, i(u
này dn n mt s ln các mnh nh3 c a "a b lãng phí.

thay i s0 dng mu tin  dài c nh là:
Không gian d tr (reserved space). Gi thit r.ng các mu tin có  dài
không vt quá mt ng1ng ( dài ti a). Ta có th s0 dng mu tin  dài c
nh (có  dài ti a), Phn không gian cha dùng n c lp y b+i mt ký
t 6c bit: null ho6c End-of-record.
Contr3 (Pointers). Mu tin  dài thay i c biu di9n b+i mt danh sách
các mu tin  dài c nh, c "móc xích" vi nhau b+i các con tr3.
S bt li c a cu trúc con tr3 là lãng phí không gian trong tt c các mu tin
ngo'i tr mu tin u tiên trong danh sách.  gii quyt vn ( này ng,i ta (
ngh phân các khi trong file thành hai lo'i:
Khi neo (Anchor block). Ch cha các mu tin u tiên trong danh sách
Khi tràn (Overflow block). Cha các mu tin còn l'i c a danh sách
Nh vy, tt c các mu tin trong mt khi có cùng  dài, cho dù file có th
cha các mu tin không cùng  dài.
5.3. T chc các mu tin trong file
Trong phn trên ta ã xét làm th nào  biu di9n các mu tin trong mt cu
trúc file.Mt quan h c th hin là mt tp hp các mu tin. Gi s0 mt tp hp
các mu tin nh th ã c cho trc, vn ( 6t ra là làm th nào  t chc
chúng trong mt file. Có mt s cách t chc sau:
T chc file ng (Heap File Organization). Trong t chc này, mt mu tin
bt k: có th c lu tr + bt k: ni nào trong file, + ó có không gian cho nó.
Không có th t nào gia các mu tin. Mt file tng ng vi mt quan h.
T chc file tun t ( Sequential File Organization). Trong t chc này, các
mu tin c lu tr th t tun t, da trên giá tr c a khoá tìm kim c a m-i
mu tin.
T chc file b!m (Hashed File Organization). Trong t chc này, có mt
hàm b!m c tính toán trên thuc tính nào ó c a mu tin. Kt qu c a hàm b!m
xác nh mu tin c b trí trong khi nào trong file. T chc này liên h ch6t
ch4 vi cu trúc ch mc.
GT CSDL – Chng 5. Lu tr và cu trúc tp tin

th li dng c toàn b nhng cái mà h thng file c a i(u hành cung cp.
Thông th,ng, các b c a mt quan h c biu di9n nh các mu tin  dài c
nh. Nh vy các quan h có th ánh x' vào mt cu trúc file. S thc hin n
gin ó c a h CSDL quan h rt phù hp vi các h CSDL c thit k cho các
máy tính cá nhân. Trong các h thng ó, kích c1 c a CSDL nh3.
Tuy nhiên, nhi(u h CSDL quy mô ln không nh, cy trc tip vào h i(u
hành n(n  qun tr file. Thay vào ó, mt file c cp phát cho h CSDL. Tt
c các quan h c lu tr trong mt file này, và s qun tr file này thuc v( h
CSDL. Cu trúc file d'ng này, c g#i là gom cm (clustering), cho phép ta #c
nhi(u mu tin c yêu cu trong mt khi.
Tuy nhiên, cu trúc gom cm trên l'i t3 ra không có li b.ng t chc lu m-i
quan h trong mt file riêng, i vi mt s câu vn tin.
GT CSDL – Chng 5. Lu tr và cu trúc tp tin
NTD – Khoa Tin – HSP Hu
8

Vic xác nh khi nào thì gom cm th,ng ph thuc vào kiu câu vn tin
mà ng,i thit k CSDL ngh" r.ng nó xy ra th,ng xuyên nht. S0 dng thn
tr#ng gom cm có th ci thin hiu n!ng áng k trong vic x0 lý câu vn tin.
5.3.3. Lu tr t in d liu
Mt h CSDL cn thit duy trì d liu v( các quan h, nh s 2 c a các
quan h. Thông tin này c g#i là t in d liu (data dictionary) hay mc lc
h thng (system catalog). Mt s thông tin mà h thng lu tr là:
- Các tên c a các quan h.
- Các tên c a các thuc tính c a m-i quan h.
- Các mi(n (giá tr) và các  dài c a các thuc tính.
- Các tên c a các View c nh ngh"a trên CSDL và nh ngh"a c a các
view này.
- Các ràng buc toàn v;n.
Nhi(u h thng còn lu tr các thông tin liên quan n ng,i s0 dng h

c làm nh mc lc c mô t nh trên, trong thc t, s4 quá ln  c qun
lý mt cách hiu qu. Thay vào ó, ng,i ta s0 dng các k* thut ch mc tinh t
hn. Có hai kiu ch mc:
Ch mc c sp (Ordered indices): c da trên mt th t sp xp theo
các giá tr.
Ch mc b!m (Hash indices): c da trên các giá tr c phân phi (u
qua các bucket. Bucket mà mt giá tr c gán vi nó c xác nh b+i mt
hàm, c g#i là hàm b!m (hash function).
i vi c hai kiu này, ta s4 nêu ra mt vài k* thut. M-i k* thut phù hp
vi các ng dng CSDL riêng bit. M-i k* thut phi c ánh giá trên c s+ c a
các nhân t sau:
Kiu truy xut: Các kiu truy xut c h- tr hiu qu. Các kiu này bao
hàm c tìm kim mu tin vi mt giá tr thuc tính c th ho6c tìm các mu tin vi
giá tr thuc tính n.m trong mt khong xác nh.
Th,i gian truy xut: Th,i gian  tìm kim mt h'ng mc d liu hay mt
tp các h'ng mc.
Th,i gian chèn: Th,i gian  chèn mt h'ng mc d liu mi. Giá tr này
bao hàm th,i gian  tìm v trí chèn thích hp và th,i gian cp nht cu trúc ch
mc.
Th,i gian xoá: Th,i gian  xoá mt h'ng mc d liu. Giá tr này bao hàm
th,i gian tìm kim h'ng mc cn xoá, th,i gian cp nht cu trúc ch mc.
Tng phí tn không gian: Không gian ph b chim b+i mt cu trúc ch
mc.
Mt file th,ng i kèm vi mt vài ch mc. Thuc tính ho6c tp hp các
thuc tính c dùng  tìm kim mu tin trong mt file c g#i là khoá tìm
kim. Chú ý r.ng nh ngh"a này khác vi nh ngh"a khoá s cp (primary key),
khoá d tuyn (candidate key), và siêu khoá (superkey). Nh vy, nu có mt vài
ch mc trên mt file, có mt vài khoá tìm kim tng ng.
5.4.1. Ch mc c sp.
Mt ch mc lu tr các giá tr khoá tìm kim tng ng vi các mu tin, các
Hình 3
Có hai lo'i ch mc c sp:
Ch mc 6c. M-i mu tin ch mc (u vào ch mc/ index entry) xut hin
i vi m-i giá tr khoá tìm kim trong file. Mu tin ch mc cha giá tr khoá tìm
kim và mt con tr3 ti mu tin d liu u tiên vi giá tr khoá tìm kim ó.
Ch mc tha. Mt mu tin ch mc c t'o ra ch vi mt s giá tr. C)ng
nh vi ch mc 6c, m-i mu tin ch mc cha mt giá tr khoá tìm kim và mt
con tr3 ti mu tin d liu u tiên vi giá tr khoá tìm kim này.  nh v mt
mu tin, ta tìm u vào ch mc vi giá tr khoá tìm kim ln nht trong các giá tr
khoá tìm kim nh3 hn ho6c b.ng giá tr khoá tìm kim ang tìm. Ta bt u t
mu tin c tr3 ti b+i u vào ch mc, và ln theo các con tr3 trong file (d
liu) n tn khi tìm thy mu tin mong mun.
Ch mc 6c cho phép tìm kim mu tin nhanh hn ch mc tha, song ch
mc tha l'i òi h3i ít không gian hn ch mc 6c. Hn na, ch mc tha yêu
cu mt tn phí duy trì nh3 hn i vi các ho't ng chèn, xoá.
Ng,i thit k h thng phi cân nhc s cân i gia th,i truy xut và tn
phí không gian. Mt tho hip tt là có mt ch mc tha vi mt u vào ch mc
cho m-i khi, vì nh vy cái giá ni tri trong x0 lý mt yêu cu CSDL là th,i
gian mang mt khi t "a vào b nh chính. M-i khi mt khi c mang vào,
th,i gian quét toàn b khi là không áng k. S0 dng ch mc tha, ta tìm khi
cha mu tin cn tìm. Nh vy, tr phi mu tin n.m trên khi tràn, ta ti thiu hoá
c truy xut khi, trong khi gi c kích c1 c a ch mc nh3 nh có th.
5.4.1.2. Ch mc nhiu mc
Ch mc có th rt ln, ngay c khi s0 dng ch mc tha và không th cha
 trong b nh mt ln. Tìm kim nh phân có th c s0 dng  tìm mt u
vào trên file ch mc, song vn phi truy xut khi, vi B là s khi "a cha ch
mc. Nu B ln, th,i gian truy xut này vn là khá ln. Hn na nu s0 dng các
khi tràn, tìm kim nh phân không s0 dng c và nh vy vic tìm kim phi

mc, chèn giá tr khoá này và con tr3 ti mu tin vào ch mc. Nu là ch mc tha
và lu u vào cho m-i khi, không cn thit phi thay i tr phi khi mi c
t'o ra. Trong tr,ng hp ó, giá tr khoá tìm kim u tiên trong khi mi c
chèn vào ch mc.
5.4.2. Ch mc th cp.
Ch mc th cp trên mt khoá d tuyn ging nh ch mc s cp 6c,
ngo'i tr các mu tin c tr3 n b+i các giá tr liên tip trong ch mc không
c lu tr tun t. Nói chung, ch mc th cp có th c cu trúc khác vi ch
mc s cp. Nu khoá tìm kim c a ch mc s cp không là khoá d tuyn, ch
mc ch cn tr3 n mu tin u tiên vi mt giá tr khoá tìm kim riêng là  (các
mu tin khác cùng giá tr khoá này có th tìm l'i c nh, quét tun t file).
Nu khoá tìm kim c a mt ch mc th cp không là khoá d tuyn, vic tr3
ti mu tin u tiên vi giá tr khoá tìm kim riêng không  , do các mu tin trong
file không còn c sp tun t theo khoá tìm kim c a ch mc th cp, chúng có
th n.m + bt k: v trí nào trong file. B+i vy, ch mc th cp phi cha tt c các
con tr3 ti m-i mu tin. Ta có th s0 dng mc ph gián tip  thc hin ch mc
GT CSDL – Chng 5. Lu tr và cu trúc tp tin
NTD – Khoa Tin – HSP Hu
13

th cp trên các khoá tìm kim không là khoá d tuyn. Các con tr3 trong ch mc
th cp nh vy không trc tip tr3 ti mu tin mà tr3 ti mt bucket cha các con
tr3 ti file.
Ch mc th cp phi là 6c, vi mt u vào ch mc cho m-i mu tin. Ch
mc th cp ci thin hiu n!ng các vn tin s0 dng khoá tìm kim không là khóa
c a ch mc s cp, tuy nhiên nó l'i em l'i mt tn phí s0a i CSDL áng
k.Vic quyt nh các ch mc th cp nào là cn thit da trên ánh giá c a nhà
thit k CSDL v( tn sut vn tin và s0a i.
5.5. File ch mc B
+

1
, K
2
, , K
n-1
, và n con tr3 P
1
, P
2
, ,
P
n
, các giá tr khoá trong nút c sp th t: i < j  K
i
< K
j
.
P
1

K
1

P
2

K
2

. . .

i
và L
j
là hai nút lá vi i < j thì m-i giá tr
khoá trong nút L
i
nh3 hn m#i giá tr khoá trong L
j
. Nu ch mc B
+
-cây là 6c,
m-i giá tr khoá tìm kim phi xut hin trong mt nút lá nào ó.
Các nút không là lá c a mt B
+
-cây t'o ra mt ch mc nhi(u mc trên các
nút lá. Cu trúc c a các nút không là lá tng t nh cu trúc nút lá ngo'i tr tt
c các con tr3 (u tr3 n các nút c a cây. Các nút con tr3m/2không là lá có th
cha n m con tr3 và phi cha không ít hn ngo'i tr nút gc. Nút gc c
GT CSDL – Chng 5. Lu tr và cu trúc tp tin
NTD – Khoa Tin – HSP Hu
14

phép cha ít nht 2 con tr3. S con tr3 trong mt nút c g#i là s nan (fanout)
c a nút.
Con tr3 P
i
c a mt nút không là lá (cha p con tr3, 1 < i < p) tr3 n mt cây
con cha các giá tr khoá tìm kim nh3 hn K
i
và ln hn ho6c b.ng K

m/2
K, trong ó K
là s giá tr khoá tìm kim trong B
+
-cây, m là bc c a cây.
5.5.3. Cp nht trên B
+
-cây
Chèn. S0 dng cùng k* thut nh tìm kim, ta tìm nút lá trong ó giá tr khoá
tìm kim cn chèn s4 xut hin. Nu khoá tìm kim ã xut hin r2i trong nút lá,
chèn mu tin vào trong file, thêm con tr3 ti mu tin vào trong bucket tng ng.
Nu khoá tìm kim cha hin din trong nút lá, ta chèn mu tin vào trong file r2i
chèn giá tr khoá tìm kim vào trong nút lá + v trí úng (bo t2n tính th t), t'o
mt bucket mi vi con tr3 tng ng. Nu nút lá không còn ch- cho giá tr khoá
mi, Mt khi mi c yêu cu t h i(u hành, các giá tr khoá trong nút lá
c tách mt n0a cho nút mi, giá tr khoá mi c chèn vào v trí úng c a nó
vào mt trong hai khi này. i(u này kéo theo vic chèn giá tr khoá u khi mi
và con tr3 ti khi mi vào nút cha. Vic chèn c6p giá tr khoá và con tr3 vào nút
cha này l'i có th dn n vic tách nút ra làm hai. Quá trình này có th dn n
tn nút gc. Trong tr,ng hp nút gc b tách làm hai, mt nút gc mi c t'o
ra và hai con c a nó là hai nút c tách ra t nút gc c), chi(u cao cây t!ng lên
mt.
Xoá. S0 dng k* thut tìm kim tìm mu tin cn xoá, xoá nó kh3i file, xoá
giá tr khoá tìm kim kh3i nút lá trong B
+
-cây nu không có bucket kt hp vi giá
tr khoá tìm kim ho6c bucket tr+ nên r-ng sau khi xoá con tr3 tng ng trong
nó. Vic xoá mt giá tr khoá kh3i mt nút c a B
+
-cây có th dn n nút lá tr+

b chim b+i (khoá,con tr3). Ta có th ci tin s s0 sng không gian trong B
+
-cây
b.ng cách bao hàm nhi(u nút anh em hn khi tái phân phi trong khi tách và trn.
Khi chèn, nu mt nút là y, ta th0 phân phi l'i mt s u vào n mt trong
các nút k(  t'o không gian cho u vào mi. Nu vic th0 này tht b'i, ta mi
thc hin tách nút và phân chia các u vào gia mt trong các nút k( và hai nút
nhn c do tách nút. Khi xoá, nu nút u vào, ta th0 mn mt u vào t mt
trong hai nút anh em2m/3cha ít hn mu tin, ta phân phi l'i các u vào c a
nút2m/3k(. Nu c hai (u có úng cho hai nút anh em k( và xoá nút th 3. Nu
k nút c s0 dng trong tái phân u vào. Tuy(k-1)m/kphi (k-1 nút anh em),
m-i nút m bo cha ít nht nhiên, cái giá phi tr cho cp nht c a cách tip
cn này s4 cao hn.
5.6. File ch mc B - cây (B-Tree Index Files)
Ch mc B-cây tng t nh ch mc B+-cây. S khác bit là + ch- B-cây
lo'i b3 lu tr d tha các giá tr khoá tìm kim. Trong B-cây, các giá tr khoá ch
xut hin mt ln. Do các khoá tìm kim xut hin trong các nút không là lá không
xut hin + bt k: ni nào khác na trong B-cây, ta phi thêm mt tr,ng con tr3
cho m-i khoá tìm kim trong các nút không là lá. Con tr3 thêm vào này tr3 ti
ho6c mu tin trong file ho6c bucket tng ng.
Mt nút lá B-cây tng quát có d'ng:
P1

K1

P2

K2
Các con tr3 Pi là các con tr3 cây và c dùng nh trong B+-cây. Các con
tr3 Bi trong các nút không là lá là các con tr3 mu tin ho6c con tr3 bucket. Rõ ràng
là s giá tr khoá trong nút không lá nh3 hn s giá tr trong nút lá. S nút c
truy xut trong quá trình tìm kim trong mt B-cây ph thuc ni khoá tìm kim
c nh v.
Xoá trong mt B-cây phc t'p hn trong mt B+-cây. Xoá mt u vào xut
hin + mt nút không là lá kéo theo vic tuyn ch#n mt giá tr thích hp trong cây
GT CSDL – Chng 5. Lu tr và cu trúc tp tin
NTD – Khoa Tin – HSP Hu
16

con c a nút cha u vào b xoá. Nu khoá Ki b xoá, khoá nh3 nht trong cây con
c tr3 b+i Pi+1 phi c di chuyn vào v trí c a Ki. Nu nút lá còn l'i quá ít
u vào, cn thit các ho't ng b sung.
nh ngha ch mc trong SQL
Mt ch mc c t'o ra b+i lnh CREATE INDEX vi cú pháp
CREATE INDEX < index-name > ON < relation_name > (< attribute-list >)
attribute-list là danh sách các thuc tính c a quan h c dùng làm khoá tìm
kim cho ch mc. Nu mun khai báo là khoá tìm kim là khoá d tuyn, thêm
vào t khoá UNIQUE:

CREATE UNIQUE INDEX < index-name > ON < relation_name > (<
attribute-list >)
8 ây attribute-list phi t'o thành mt khoá d tuyn, nu không s4 có mt
thông báo l-i.
 b3 i mt ch mc ta s0 dng lnh DROP:DROP INDEX < index-name >
5.7. Phng pháp b!m (HASHING)
5.7.1. B!m t"nh (Static Hashing)
Bt li c a t chc file tun t là ta phi truy xut mt cu trúc ch mc 
nh v d liu, ho6c phi s0 dng tìm kim nh phân, và kt qu là có nhi(u ho't

kim trong tp hp tt c các giá tr khoá có th.
+ Phân phi ngu nhiên: Trong tr,ng hp trung bình, các bucket
c gán mt s lng giá tr khoá tìm kim gn b.ng nhau.
Các hàm b!m phi c thit k thn tr#ng. Mt hàm b!m xu có th dn
n vic tìm kim chim mt th,i gian t7 l vi s khoá tìm kim trong file.
5.7.1.2. #iu khin tràn bucket
Khi chèn mt mu tin, nu bucket tng ng còn ch-, mu tin c chèn vào
bucket, nu không s4 xy ra tràn bucket. Tràn bucket do các nguyên do sau:
+ Các bucket không  . S các bucket nB phi tho mãn nB > nr / fr trong ó
nr là tng s mu tin s4 lu tr, fr là s mu tin có th lp y trong mt bucket.
+ S lch. Mt vài bucket c gán cho mt s lng mu tin nhi(u hn các
bucket khác, nh vy mt bucket có th tràn trong khi các bucket khác vn còn
không gian. Tình hung này c g#i là s lch bucket. S lch xy ra do hai
nguyên nhân:
+ Nhi(u mu tin có cùng khoá tìm kim
+ Hàm b!m c ch#n phân phi các giá tr khoá không (u
Ta qun lý tràn bucket b.ng cách dùng các bucket tràn (phng pháp liên kt
ngoài). Nu mt mu tin phi c chèn vào bucket B nhng bucket B ã y, khi
ó mt bucket tràn s4 c cp cho B và mu tin c chèn vào bucket tràn này.
Nu bucket tràn c)ng y mt bucket tràn mi l'i c cp và c nh vy. Tt c
các bucket tràn c a mt bucket c “móc xích” vi nhau thành mt danh sách
liên kt. Vic i(u khin tràn dùng danh sách liên kt nh vy c g#i là dây
chuy(n tràn. i vi dây chuy(n tràn, thut toán tìm kim thay i chú ít: trc
tiên ta c)ng tính giá tr hàm b!m trên khoá tìm kim, ta c bucket B, kim tra
các mu tin, trong bucket B và tt c các bucket tràn tng ng, có giá tr khoá
khp vi giá tr tìm không.
Mt cách i(u khin tràn bucket na là phng pháp a ch m+ (b!m óng):
Khi cn chèn mt mu tin vào mt bucket nhng nó ã y, thay vì cp thêm
mt bucket tràn, ta s0 dng mt hàm b!m k trong mt dãy các hàm b!m c
ch#n  tìm bucket khác cho mu tin, nu bucket sau c)ng y, ta l'i s0 dng mt

+ T chc l'i theo chu k: cu trúc b!m áp ng s phát trin kích c1 file.
Mt s t chc l'i nh vy kéo theo vic la ch#n mt hàm b!m mi, tính l'i hàm
b!m trên m-i mu tin trong file và sinh ra cách gán bucket mi. T chc l'i là mt
ho't ng tn th,i gian. Hn na, nó òi h3i cm truy xut file trong khi ang t
chc l'i file.
K* thut b!m ng cho phép s0a i hàm b!m  phù hp vi s t!ng ho6c
gim c a CSDL. Mt d'ng b!m ng c g#i là b!m có th m+ rng (extendable
hashing) c thc hin nh sau: Ch#n mt hàm b!m h vi các tính cht (u,
ngu nhiên và có mi(n giá tr tng i rng, ch5ng h'n, là mt s nguyên b bit (b
th,ng là 32). Khi kh+i u ta không s0 dng toàn b b bit b. i bit này c≤i≤giá
tr b!m. T'i mt th,i im, ta ch s0 dng i bit 0. i bit này c dùng nh mt 
d,i (offset) trong mt bng a ch bucket ph. giá tr i t!ng lên hay gim xung
tu: theo kích c1 CSDL.
S i xut hin bên trên bng a ch bucket ch ra r.ng i bit c a giá tr b!m
h(K) c òi h3i  xác nh bucket úng cho K, s này s4 thay i khi kích c1
file thay i. M6c dù i bit dc òi h3i  tìm u vào úng trong bng a ch
bucket, mt s u vào bng k( nhau có th tr3 n cùng mt bucket. Tt c các
nh vy có chung hash prefix chung, nhng chi(u dài c a prefix này có th nh3
hn i. Ta kt hp mt s nguyên ch  dài c a hash prefix chung này, ta s4 ký
hiu s nguyên kt hp vi bucket j là ij. S các u vào bng a ch bucket tr3
n bucket j là 2
i−ij
.
Cu trúc b!m có th m+ rng tng quát
 nh v bucket cha giá tr khoá tìm kim K , ta ly i bit cao u tiên c a
h(K), tìm trong u vào bng tng ng vi chu-i bit này và ln theo con tr3 trong
u vào bng này.  chèn mt mu tin vi giá tr khoá tìm kim K, tin hành th
tc dnh v trên, ta c bucket, gi s0 là bucket j. Nu còn cho cho mu tin, chèn
mu tin vào trong bucket ó. Nu không, ta phi tách bucket ra và phân phi l'i
GT CSDL – Chng 5. Lu tr và cu trúc tp tin

bucket trc khi truy xut n bucket. Vì vy, b!m có th m+ rng là mt k* thut
rt hp dn.
5.7.3. Ch$n ch mc hay b!m?
Ta ã xét qua các s 2: ch mc th t, b!m. Ta có th t chc file các mu
tin b+i ho6c s0 dng t chc file tun t ch mc, ho6c s0 dng B+-cây, ho6c s0
dng b!m M-i s 2 có nhng các u im trong các tình hung nht nh. Mt
nhà thc thi h CSDL có th cung cp nhi(u nhi(u s 2,  l'i vic quyt nh s0
dng s 2 nào cho nhà thit k CSDL.  có mt s la ch#n khôn ngoan, nhà
thc thi ho6c nhà thit k CSDL phi xét các yu t sau:
Cái giá phi tr cho vic t chc l'i theo nh k: c a ch mc ho6c b!m có
chp nhn c hay không?
Tn s tng i c a các ho't ng chèn và xoá là bao nhiêu ?
Có nên ti u hoá th,i gian truy xut trung bình trong khi th,i gian truy xut
tr,ng hp xu nht t!ng lên hay không ?
GT CSDL – Chng 5. Lu tr và cu trúc tp tin
NTD – Khoa Tin – HSP Hu
20

Các kiu vn tin mà các ng,i s0 dng thích 6t ra là gì ?
CÂU H%I VÀ BÀI TP
1. Xét vic xoá mu tin 5 trong file: So sánh các i(u tt/xu tng i c a các k* thut xoá sau:
Di chuyn mu tin 6 n không gian ch chim b+i mu tin 5, r2i di chuyn
mu tin 7 n ch- b chim b+i mu tin 6.
Di chuyn mu tin 7 n ch- b chim b+i mu tin 5

các mu tin  dài thay i phù hp hn phng pháp con tr3.
7. Nêu lên mt ví d, trong ó phng pháp con tr3  biu di9n các mu tin
 dài thay i phù hp hn phng pháp không gian d tr.
8. Nu mt khi tr+ nên r-ng sau khi xoá. Khi này c tái s0 dng vào
mc ích gì ?
9. Trong t chc file tun t, t'i sao khi tràn c s0 dng thm chí, t'i th,i
im ang xét, ch có mt mu tin tràn ?
10. Lit kê các u im và nhc im c a m-i mt trong các chin lc lu
tr CSDL quan h sau:
Lu tr m-i quan h trong mt file
Lu tr nhi(u quan h trong mt file
11. Nêu mt ví d biu thc 'i s quan h và mt chin lc x0 lý vn tin
trong ó:
MRU phù hp hn LRU
LRU phù hp hn MRU
12. Khi nào s0 dng ch mc 6c phù hp hn ch mc tha ? Gii thích.
13. Nêu các im khác nhau gia ch mc s cp và ch mc th cp .
14. Có th có hai ch mc s cp i vi hai khoá khác nhau trên cùng mt
quan h ? Gii thích.
15. Xây dng mt B
+
-cây i vi tp các giá tr khoá: (2, 3, 5, 7, 11, 15, 19,
25, 29, 33, 37, 41, 47). Gi thit ban u cây là r-ng và các giá tr c chèn theo
th t t!ng. Xét trong các tr,ng hp sau:
M-i nút cha ti a 4 con tr3
M-i nút cha ti a 6 con tr3
M-i nút cha ti a 8 con tr3
16. i vi m-i B
+
-cây trong bài tp 15, trình bày các bc thc hin trong

Chèn 15

TÀI LI&U THAM KH'O
[1]. Ph'm Gia Tin, Ph'm Th Phi, H qun tr c s+ d liu, B môn h
thng máy tính & truy(n thông, Khoa CNTT, H Cn Th, 2007.