A hash kód

A hash-kódokat manapság már csak hálós vagy hierarchikus modellben használják. Ennek a kódolási technikának a lényege, hogy egy számítási algoritmus alapján magából az index kulcsból alakítják ki az úgynevezett hash-kódokat, amelynek alapján egy táblázatból kiolvasható a keresett értéket tartalmazó sor fizikai címe vagy egy számítási algoritmus adja meg a keresett értéket. A hash-kód számítási algoritmusa nem mindig ad különböző értékeket az index kulcsokra. Ez abból is következik, hogy csak véges hosszúságú hash-táblát tudunk kezelni. Minél jobb a hash-algoritmus, annál kevesebb lesz a kulcsütközés.

A hash-kód kulcsütközés

Azokban az esetekben, amikor különböző kulcsértékekhez ugyanazt a címet adja, ezeket a különböző kulcsú rekordokat szinonimoknak mondjuk. A szinonim rekordokat kezelni kell (Például külön táblákba tesszük a különböző betűvel kezdődő neveket, és ott más módszerrel finomítjuk a keresést. Ez az elosztott altáblák módszere.) Nyilván annál jobb egy hash-leképezés, minél kevesebb szinonim van. Példa hash-leképezésre: alkalmasan nagy prímszámmal osztjuk a numerikusnak tekintett kulcsot, és a maradékot használjuk fel címként. Kulcs szerinti közvetlen feldolgozásra a jó hash-leképezés hatékonyabb az indexnél, ezért a hash-leképezést előszeretettel alkalmazzák a hierarchikus és hálós modellben.

Hash-kód és relációs adatbázis

A hash-leképezést relációs adatbázisoknál nem használják, mert nem tesz lehetővé szekvenciális elérést: csak kulcs szerint lehet keresni, egy rekord más mezője szerint nem. Az azonos kódot adó kulcsokat összeláncolják a hash-táblában. A láncok növekedésével természetesen a reláció sorainak eléréséhez szükséges idő is növekszik. A hash-kód alapján történő visszakeresés nagyon gyors.

Bináris fa

Ma már szinte kizárólag a bináris fákat alkalmazzák a relációs adatbázisokban. Ennél a módszernél a bináris keresést alkalmazzuk. Ehhez az index kulcsokat növekvő vagy csökkenő sorrendbe kell rendezni. A fa szerkezetet azért használják, mert nagy adatbázisok esetén az összes index kulcs nem tartható egy időben a memóriában. A fa gyökere és csomópontjai nem tartalmazzák az index kulcshoz tartozó sor fizikai helyét, hanem csak a fa levelei. A keresés mindig a gyökértől indul, a megfelelő ág felé folytatódik, és akkor ér véget, ha egy levélhez érünk. Ha a levélben tárolt index kulcs azonos a keresettel, akkor megtaláltuk a keresett értéket, különben sikertelen volt a keresés.

Bináris fa

A kiegyensúlyozott bináris fa

A bináris fák felépítésénél arra törekszenek, hogy a fa valamennyi ága azonos hosszúságú legyen. Az ily módon felépített fát kiegyensúlyozott fának hívják. A kiegyensúlyozott fákban találhatjuk meg a lehető legkevesebb összehasonlítással a keresett elemet.

A gyakorlati megoldásokban a hatékonyság kedvéért a csomópontokban nem csak egy index kulcs értéket tárolnak, hanem a háttértár tárolási egységének megfelelő számút. Mivel a PC-s rendszerek olvasási egysége 2 hatvány (például: 2, 4, 8, … ,64), ezért egy lap általában ekkora.

A bináris fák bejárása

A bináris fák segítségével egy konkrét index kulcsot vagy az index kulcsok egy tartományát kereshetjük meg. A reláció sorait az index kulcs szerinti növekvő vagy csökkenő sorrendben is végigjárhatjuk, ami valójában a bináris fa Bal-Közép-Jobb vagy Jobb-Közép-Bal bejárását jelenti. Ez hash-kód esetén nem valósítható meg.

Asszociatív rendszerek

Az utóbbi évtizedben kialakult és nem túlságosan széles körben elterjedt rendszerek, amelyek hardver szinten támogatják a memóriatartalom alapján az adateléréseket. Ezeket asszociatív memóriának hívjuk. Ezek segítségével lehet olyan tárolási és keresési módokat létrehozni, amelyek a tartalom alapján adnak eredményeket. A gyakorlatban speciális célhardver és célszoftver segítségével lehet alkalmazni csak őket.

A hash-kódokat manapság már csak hálós vagy hierarchikus modellben használják. Ennek a kódolási technikának a lényege, hogy egy számítási algoritmus alapján magából az index kulcsból alakítják ki az úgynevezett hash-kódokat, amelynek alapján egy táblázatból kiolvasható a keresett értéket tartalmazó sor fizikai címe vagy egy számítási algoritmus adja meg a keresett értéket. A hash-kód számítási algoritmusa nem mindig ad különböző értékeket az index kulcsokra. Ez abból is következik, hogy csak véges hosszúságú hash-táblát tudunk kezelni. Minél jobb a hash-algoritmus, annál kevesebb lesz a kulcsütközés.

Ma már szinte kizárólag a bináris fákat alkalmazzák a relációs adatbázisokban. Ennél a módszernél a bináris keresést alkalmazzuk. Ehhez az index kulcsokat növekvő vagy csökkenő sorrendbe kell rendezni.

Az utóbbi évtizedben kialakult és nem túlságosan széles körben elterjedt rendszerek, amelyek hardver szinten támogatják a memóriatartalom alapján az adateléréseket. Ezeket asszociatív memóriának hívjuk. Ezek segítségével lehet olyan tárolási és keresési módokat létrehozni, amelyek a tartalom alapján adnak eredményeket. A gyakorlatban speciális célhardver és célszoftver segítségével lehet alkalmazni csak őket.