– přiřazení adresy uložení věty v bloku jejímu klíči na základě transformačního algoritmu
a) přímé adresování – jednoznačný vztah mezi klíčem a adresou
b) nepřímé adresování – transformační funkce neposkytuje jednoznačný vztah mezi klíčem a adresou (celočíselné dělení prvočíslem, slučování číslic, převod na jiná základ, generování náhodného čísla)
Toto vše jsou relativně primitivní organizace, dnes se ve velkých DB systémech používají B-stromy a bitmapové indexy.
B-stromy
- věty v databázi mohou být jakkoli upořádány, B-strom vzniká navíc vedle neuspořádané DB
6 prvků definice B-stromu řádu m:
1. každý uzel má nejvýše m následníků
2. každý uzel má alespoň m/2 následníků vyjma kořene a listů
3. kořen má alespoň 2 následníky
4. všechny listy jsou na stejné úrovni
5. uzel, který není listem a má k následníků, obsahuje k-1 hodnot klíčů
6. jestliže uzel G je následníkem uzlu H, pak mezi hodnotami klíče gi a hi platí:
gi <>i je-li G 1.následník
hj-1 <= gi <>j je-li G j-tý následník (1
gi >= hk-1 je-li G k-tý následník
Při rozšiřování nebo zužování databáze dochází k bobtnání či zužování B-stromu
Žádné komentáře:
Okomentovat