Database System
8 – Hash-Based Indexing
Dahlia Widhyaestoeti, S.Kom
Powered by www.RedOffice.com
Pustaka Sistem Manajemen Database Edisi ketiga, Raghu Ramakrishnan & Johannes Gehrke, McGrawHill 2003
Hash-Based Indexing Hash-Based Indexing adalah organisasi file yang baik digunakan pada equality selection. Pemikiran dasarnya adalah menggunakan fungsi Hashing, yang memetakan nilai dalam field search ke dalam rentang dari bucket number untuk menemukan halaman di mana terdapat entri data yang di inginkan. Skema dalam Hash-Based Indexing : Static Hashing Extendible Hashing Linear Hashing
Static Hashing h(key) mod N key
Halaman yang berisi data
0 2
h
N-1 Primary bucket pages
Overflow pages
dapat dianggap sebagai kumpulan bucket, dengan sebuah halaman primer dan mungkin sebuah halaman overflow tambahan per bucket. Sebuah file terdiri dari bucket 0 sampai N-1, dengan satu halaman primer per bucket pada awalnya. Bucket berisi entri data.
Jika kita mempunyai N bucket, yang diberi nomor 0 sampai N-1, fungsi hash h dari bentuk h(nilai) = (a*nilai+b) berjalan dengan baik dalam praktiknya (bucket teridentifikasi adalah h (nilai) mod N). Konstanta a dan b dapat dipilih untuk “men-tune” fungsi hash.
Extendible Hashing Dengan mempertimbangkan file Static Hashing: Jika harus menyisipkan entri baru ke dalam bucket yang penuh, maka perlu menambah halaman overflow. Jika tidak ingin menambahkan halaman overflow, solusinya adalah mereorganisasi file pada titik ini dengan menggandakan jumlah bucket dan meredistribusi entri pada pada kumpulan bucket baru. Solusi menimbulkan masalah : Seluruh file harus dibaca Dua kali sebanyak halaman yang harus ditulis untuk melakukan reorganisasi. Cara mengatasi : Gunakan direktori dari pointer pada bucket Gandakan ukuran dari jumlah bucket dengan hanya menggandakan direktori dan memisahkan hanya bucket yang overflow
Extendible Hashing Direktori terdiri dari array yang
besarnya 4, yang masingmasing elemennya menjadi pointer pada bucket.
LOCAL DEPTH GLOBAL DEPTH
2 4* 12* 32* 16*
Data entri r Maka h(r)=32
Untuk menemukan entri data r ,
aplikasikan fungsi hash pada field search (Global Depth) dan mengambil 2 bits terakhir dari representasi biner. Jika h(r) = 5 = 101, berada pada bucket 01. Untuk menyisipkan entri data,
lakukan pencarian untuk menemukan bucket yang tepat. Jika bucket penuh maka split (dibagi alokasikan pada halaman baru)
BucketA
2 00
2 1*
5* 21* 13*
B ucket B
01 10
2
11
10*
D IR E C T O R Y
B ucket C
2 15* 7* 19* D ATA PA G E S
B ucket D
Contoh : sisipkan 13* dan 20*
Extendible Hashing LOCAL DEPTH
2 32*16*
GLOBAL DEPTH 2
B ucketA
3 32*16* B ucketA
GLOBAL DEPTH
2
3
1 * 5 * 2 1 *1 3 * B u c k e t B
00
LOCAL DEPTH
01
000
2 1* 5* 21*13* B ucket B
001
10
2
11
10*
B ucket C
15* 7* 19*
B ucket D
011
10*
B ucket C
101
2
110
15* 7* 19*
B ucket D
111
2 4* 12*20*
2
100
2 D IR E C T O R Y
010
B ucketA2 (`s p lit im a g e ' of B ucketA)
3 D IR E C T O R Y
4* 12*20*
B ucketA2 (`s p lit im a g e ' of B ucketA)
Extendible Hashing Hal penting yang muncul adalah Apakah memisahkan bucket mengharuskan penggandaan direktori ? LOCAL DEPTH
3 32*16* B ucket A
GLOBAL DEPTH 3 000
3 1* 9*
B ucket B
001 010
2
011
10*
B ucket C
100 101
2
110
15* 7* 19*
B ucket D
111 3 D IR E C T O R Y
4* 12* 20* 3 5* 21* 13*
B ucket A2 (`s p lit im a g e ' of B ucket A) Bucket B 2 (`s p lit im a g e ' of B ucket B )
Jika kita meyisipkan 9* ? Bucket B penuh Pisahkan Bucket dan gunakan elemen direktori 001 dan 101 Bucket Split tidak perlu menggandakan direktori Jika semua bucket telah terisi penuh, maka baru gandakan direktori.
Linear Hashing Adalah teknik dinamik hashing Mengatur penyisipan dan penghapusan Berbeda dengan static hashing, Linear Hashing tidak
memerlukan direktori Fleksibilitas dengan waktu dari bucket split Skema menggunakan famili dari fungsi hash h0,h1,h2, .. dengan sifat bahwa setiap rentang fungsi sebesar 2 kali rentang sebelumnya. Jika h memetakan entri data ke dalam satu M bucket, maka hi+1 memetakan entri data ke dalam salah satu dari 2M bucket. Misal sejumlah N dari bucket sebesar 32, h0 adalah h mod 32 (rentang 0 sampai 31).
Linear Hashing Bucket untuk di split Next Bucket yang ada pada permulaan putaran : Ini adalah rentang hlevel
Split bucket dalam putaran ini Jika hlevel (nilai search key) adalah rentang ini, harus menggunakan hlevel+1(nilai search key) untuk memutuskan jika entri adalah dalam bucket split image.
Bucket 'split image': tercipta (melalui mensplit bucket lain) dalam putaran ini.
Linear Hashing Level=0, N=4 h 1
h
Counter level digunakan untuk
PRIMARY 0 Next=0 PAGES 32*44* 36*
000
00
001
01
9* 25* 5*
010
10
14* 18*10* 30* Primary bucket page
011
11
Informasi ini hanya untuk ilustrasi
with h(r)=5
31* 35* 7* 11* Isi aktual file linear hashed
mengindikasi jumlah putaran terbaru dan diawali dengan 0. Bucket yang akan dipisahkan ditandai dengan Next dan pada awalnya adalah bucket 0 (bucket pertama). Jumlah bucket pada permulaan putaran 0, ditandai N0, menjadi N.
Linear Hashing Level=0 h 1
h
0
PRIMARY PAGES 32*
000
00
001
Next=1 9* 25* 5* 01
010
10
011
11
100
00
OVERFLOW PAGES
14* 18*10* 30* 31* 35* 7* 11* 44* 36*
43*
Penyisipan Entri 43* Membentuk halaman overflow. Kapanpun pemisahan terpicu, bucket Next akan dipisahkan, dan fungsi hash hlevel+1 mendistribusi entri diantara bucket ini . Setelah memisahkan bucket, nilai next ditambah 1.
Linear Hashing Level=0 h 1
h
0
PRIMARY PAGES 32*
000
00
001
Next=1 9* 25* 5* 01
010
10
011
11
100
00
OVERFLOW PAGES
Sisipkan record r dengan h(r) = 37
14* 18*10* 30* 31* 35* 7* 11* 44* 36*
43*
Linear Hashing Level=0 PRIMARY PAGES
h1
h0
000
00
001
01
010
10
9* 25* Next=2 14*18* 10* 30*
011
11
31*35* 7* 11*
100
00
44*36*
101
01
5* 37*29*
OVERFLOW PAGES
32*
Sisipkan record r dengan h(r) = 29
43*
Linear Hashing Level=0 h1
h0
000
00
PRIMARY PAGES
OVERFLOW PAGES
32*
Sisipkan record r dengan h(r) = 22, 66 dan 34
9* 25*
001
01
010
10
011
11
100
00
44*36*
101
01
5* 37*29*
110
10
14*30*22*
66*18* 10* 34* Next=3 31*35* 7* 11*
43*
Sisipkan record r dengan h(r) = 50?
Linear Hashing PRIMARY PAGES
h1
h0
000
00
32*
001
01
9* 25*
010
10
66* 18* 10* 34*
011
11
43* 35* 11*
100
00
44* 36*
101
11
5* 37* 29*
110
10
14* 30* 22*
111
11
31* 7*
Next=0
OVERFLOW PAGES
50*
Thank you !
