---

Hej NG

Jeg står i et projekt og skal opbygge en database, fra grunden. Jeg
overvejer om jeg skal bruge hash eller b-træer til søgning. Er der nogen der
har nogle gode argumenter for / imod??

--
Venligst ZAP

---

"ZAP" <presario266@hotmail.com> skrev
> Jeg står i et projekt og skal opbygge en database, fra grunden. Jeg
> overvejer om jeg skal bruge hash eller b-træer til søgning. Er der nogen
der
> har nogle gode argumenter for / imod??


Jeg vil mene at du skal bruge B-tree fordi B-tree er bla. lavet til at
organiserer filstrukture!

(John =

---

---

"Claus Brinch Jensen" <c-b-j@e-mail.dk> skrev i en meddelelse
news:9ceb3q$80m$1@news.cybercity.dk...
>
> Med andre ord, at svare på dit spørgsmål med de tilgængelige informationer
> vil være det rene gætværk.

Ok, her er status:

Jeg har opbygget et DBMS, der skal tage sig af db filer på en lokal disk.
Når en tabel oprettes, dannes der en .meta fil der indeholder oplysninger om
tabellen (type, størrelse m.m), samt en .tab fil der indeholder de egentlige
data binært. Det er meningen at brugeren selv skal kunne vælge hvilke felter
der skal indekseres. Søgning i tabellen skal som nævnt foregå enten som
hash, eller som b-træ, og det jeg mangler er argumenter for at gøre det ene
eller det andet. Hvis du ønsker at hjælpe og mangler oplysninger, er det
blot at spørge, i stedet for at konstaterer at spørgsmålet er irrelevant.

Venligst ZAP

---

"ZAP" <presario266@hotmail.com> writes:

>Søgning i tabellen skal som nævnt foregå enten som
>hash, eller som b-træ, og det jeg mangler er argumenter for at gøre det ene
>eller det andet.

Som sædvanligt kommer det an på, hvilke operationer på din data
struktur, der er hyppige.

I det omfang man nu kan generalisere, så kan man dog sige at i de
situationer, hvor man traditionelt vakler mellem hash-tabeller eller
balancerede træer, så skal man vælge "ternary search tree"s.

En hash-tabel har den primære ulempe at hash-værdien typisk tager
linær tid i nøglens længde at udregne. Der er dog også andre
problemer ved hash-tabeller, f.eks. spørgsmålet om hvilken hash-
funktion, man skal bruge.
Generelt kan man sige at ternary search trees er at foretrække
frem for hash-tabeller i følgende situationer:

1) Miss'es er hyppige
2) Lange nøgler
3) Indsættelse og fjernelse er mindre hyppig end søgning
4) Unicode strenge
5) Hvis du har brug for at traversere data i rækkefølge
6) Hvis du vil lave partiel matching, eller "nabo"-søgninger
7) Resizing af en hash-tabel er dyrt

Se f.eks.

http://www.ddj.com/articles/1998/9804/9804a/9804a.htm?topic=algoritms

for mere information. Derudover har Sedgewick mere at sige om sagen.

Mvh
Asger Alstrup Nielsen

---

Hej,

> I det omfang man nu kan generalisere, så kan man dog sige at i de
> situationer, hvor man traditionelt vakler mellem hash-tabeller eller
> balancerede træer, så skal man vælge "ternary search tree"s.

Hvad er det?

> En hash-tabel har den primære ulempe at hash-værdien typisk tager
> linær tid i nøglens længde at udregne.

Hmm, ja, det er svært at slå en værdi op hvis man ikke må se på den.

> Der er dog også andre
> problemer ved hash-tabeller, f.eks. spørgsmålet om hvilken hash-
> funktion,

Hvad er der galt med standard funktionen fra universal hashing?


Venlig Hilsen

Christian Worm

---

"Christian Worm Mortensen" <worm@dkik.dk> writes:

>> I det omfang man nu kan generalisere, så kan man dog sige at i de
>> situationer, hvor man traditionelt vakler mellem hash-tabeller eller
>> balancerede træer, så skal man vælge "ternary search tree"s.

>Hvad er det?

Ternary search trees er beskrevet nærmere i det link, jeg gav i første
mail.

>> En hash-tabel har den primære ulempe at hash-værdien typisk tager
>> linær tid i nøglens længde at udregne.

>Hmm, ja, det er svært at slå en værdi op hvis man ikke må se på den.

Finten er, at i et ternary search tree, kan man i nogle situationer
afgøre et miss uden at skulle se på hele nøglen.

>Hvad er der galt med standard funktionen fra universal hashing?

Der findes simpelthen ikke nogen hash-funktion, som er ideel er alle
sammenhænge. Problemet kan være at den skaber for mange konflikter,
eller at den er for langsom at udregne. Det kommer helt an på karakteren
af dine data og brug af hashtabellen.
Generelt kan man dog sige, at man kun skal begynde at bekymre sig om
optimaliteten af sin hash-funktion, hvis man observerer et problem med
den man bruger, så som mange konflikter, eller at man har brug for de
allersidste 5-10% performance.

Mvh
Asger Alstrup Nielsen

---

Hej,

> >Hvad er det?
>
> Ternary search trees er beskrevet nærmere i det link, jeg gav i første
> mail.

Ok, har lige skimmet den.

> Finten er, at i et ternary search tree, kan man i nogle situationer
> afgøre et miss uden at skulle se på hele nøglen.

Ja, ok.

> Der findes simpelthen ikke nogen hash-funktion, som er ideel er alle
> sammenhænge.

Nej - men der findes hashfunktioner der med god sandsynlighed bruger
O(1) tid hvis blot inddata er uafhænigt af et tilfældigt valg du
foretager når du konstruerer din hash funktion.


Venlig Hilsen

Christian Worm

---

> Generelt kan man dog sige, at man kun skal begynde at bekymre sig om
> optimaliteten af sin hash-funktion, hvis man observerer et problem med
> den man bruger, så som mange konflikter, eller at man har brug for de
> allersidste 5-10% performance.

Jeg vil mene at man skal være på vagt overfor compiler optimeringsfejl (*)
som kan være fatale (helt andet målestok end 5-10% performance forskel)
jeg har lavet følgende benchmark i vc++:

et sted i algoritmen udføres linjen (1):
LPOINT a = b-c; // hvor b og c er LPOINT's
gøres dette tager algoritmen 950 ms
udskiftes (1):
a.x=b.x-c.x;
a.y=b.y-c.y; // denne og ovenstående linje kaldes (2)
tager algoritmen 750 ms

udføres (1) to gange tager algoritmen 1182 ms mens den kun tager 776 ms hvis
(2) udføres 2 gange.
projektet er sat til release med maximize speed optimering. Formodentlig
skyldes det en "fejl" i compiler optimeringerne (en compiler burde kunne
optimere bedre). Jeg har ligeledes set at en inline funktion hvor alle
parametre er referencer kan nedsætte hastigheden selvom funktionen returnere
en "basic type".

struct LPOINT{
double x;
double y;
LPOINT(){}
LPOINT(LCOORD Ix,LCOORD Iy) : x(Ix),y(Iy){}
LPOINT operator-(const LPOINT& a) const{
return LPOINT(x - a.x,y - a.y);
}
};


(*) primært når man laver de funktioner der kaldes mange gange (som fx. en
hashfunktion)