36
dengan
membagi
indeks
yang
ada ke
beberapa file,
untuk
membagi ke
ukuran yang lebih kecil dan mengatur indeks dengan indeks.
•
B-Tree
B-Tree adalah sebuah tree yang seimbang dan biasanya dirancang
untuk
media
penyimpanan sekunder
serta
banyak
dipakai
oleh
sistem
basis
data.
Sebuah
B-Tree
T
mempunyai
root
T
dan
ciri-ciri
sebagai
berikut :
1. Setiap node x mempuyai penjelasan sebagai berikut :
a. n[x], sejumlah key yang disimpan di node x,
b. key dari n[x]
itu sendiri, yang disimpan terurut sehingga key1[x]
=
key2[x] = . . . = key
n[x]
[x],
c. leaf[x],
sebuah
nilai
yang
bernilai benar jika
x
adalah leaf,
dan
salah jika x adalah node internal.
2. Setiap
node
internal
x
selalu
mempunyai
pointer
sebanyak n[x]+1
buah ke
node
anaknya,
sedangkan node
leaf
tidak
mempunyai node
anak.
3. Semua leaf mempunyai ketinggian yang sama (h).
4. Sebuah node
mempunyai batas bawah dan atas di sejumlah key dan
batasan ini
dapat
dinyatakan dalam
bilangan
bulat
t
=
2
disebut
derajat minimum dari B-Tree :
a.
Setiap
node
selain
root
harus mempunyai
sedikitnya
key
t-1
buah.
Setiap
node
internal
selain
root
mempunyai
sedikitnya
t
node
anak. Jika
tree
tidak
kosong,
maka
root
minimal
mempunyai 1 key.
 |