Egyszerű adatbázisban (név, telszám) logaritmikus keresésnél gyorsabb létezik? (bővebben lent)

Nem mindegy milyen adatbázisról beszélsz.

Általánosságban ha csak konkrét egyezőséget akarsz vizsgálni, akkor az valamilyen hashtable struktúrával gyorsítható konstans időre, de hash alapján nem tudsz pl. kisebb mint, vagy nagyobb mint vizsgálatokat végezni.

Random access fájlban hashelheted mondjuk a nevet a fájl sorához (vagy byte-jához akár).

Szöveges fájl esetében a seek (navigáció az adott rekordhoz) ilyen esetben konstans (de magát a rekordot persze be kell olvasnod karakterenként).

Alapfogalmakat tisztázzunk. Amiről te beszélsz, az nem adatbázis.

Ha saját programban tárolod az adatokat, először az adatszerkezetet kell meghatározni, addig nem sok értelme van a keresés sebességéről beszélni.

Adatbázisban pedig nincs saját kereső algoritmus, hanem indexelés van, és a többi az adatbázis dolga.

"Bináris fa, bináris keresés"

Nem csak bináris keresés létezik, lehet több utas is. Ha jól emlékeszem (nem esküszöm meg rá), akkor a régi Clipper-es ntx index 12 utas keresést használt, ami valószínűleg egy használati szokásokon alapuló tapasztalati érték.

(Ha indexekről beszélünk, akkor sokszor nem is maga a keresés okozza a gondot, hanem az index karbantartása, a keresési fa "egyensúlyban" tartása sok beszúrás és törlés után.)

** "index karbantartása"

Mármint nem a szimpla rendezett lista jellegű indexekről van most szó, hanem a több utasakról, ahol az egyes "utak" értékhatárai is tárolva vannak a fa szintjein. Ez a megoldás egyébként igen gyors keresést tesz lehetővé. (Ez is logaritmikus, csak nem feltétlenül kettes alapú.)

"és a többi az adatbázis dolga"

Muhhaha.. :o)

Az adatbázisnak nincs semmi "dolga". Az egy passzív adathalmaz.

"Igaza van annak a válaszolónak, aki jelezte, hogy rosszul használom az alapfogalmat, hogy ez nem adatbázis."

Dehogy volt igaza. Eleve, már egy 10 byte-os halmaz is lehet adatbázis.

Amiről meg ő beszél, na, éppen az nem adatbázis, csak annak kezelője.

Ha betűre indexelsz, akkor azzal már meghatározol egy részhalmazt, amin műveletet végzel és ami - átlagban - a huszada sincs a teljes halmaznak. Ha meg betűpárra indexelsz, akkor még kisebb halmazzal kell dolgoznod, ami a teljes halmaznak mindössze egy-két százaléka, vagy még annál is kevesebb, statisztikailag.