keresstruktúrákat
Keresstruktúrák olyan adatszerkezetek, amelyek adatok gyors keresésére, lekérdezésére és rendezésére szolgálnak. Céljuk a keresési idők csökkentése és a memória-/műveleti költségek optimalizálása a feladat jellegétől függően. Gyakorlati alkalmazások közé tartoznak a szövegkeresés, az adatbázisok és a térbeli vagy multidimenzionális adatok kezelése.
A leggyakoribb típusok közé tartoznak:
- Fordított indexek (inverted index): szöveges dokumentumgyűjteményekben minden szórészhez a dokumentum-azonosítók listája tartozik, lehetővé téve gyors, konjunkciós
- Sorrend- és tartományi indexek (például B-táblák és B+ fák): adatbázisokban és fájlrendszerekben használják tartomány- és rendezett
- Prefixfák és más keresőfák (trie): hatékonyak prefixalapú keresésre és automatikus kiegészítésre; memóriaigényesebbek lehetnek nagy adathalmazokon.
- Többdimenziós és geometriai indexek (például k-d fák, R-fák): multidimenzionális adatok tartomány- és közelítõ kereséseire alkalmasak.
- Hash-táblák: pontos egyezések gyors lekérdezésére adnak jó teljesítményt, de nem ideálisak tartomány- vagy rendezett keresésekhez.
- Kiegészítő megoldások: a modern rendszerek gyakran kombinálják a különböző struktúrákat különféle lekérdezési típusok kiszolgálására.
Kihívások közé tartozik a skálázhatóság, a dinamikus frissítés és a megfelelő egyensúly megtalálása a lekérdezési sebesség