PDA

Visualizza la versione completa : [C] Cosa sono i B-tree ???


_sys/sid
15-10-2004, 18:42
Da titolo... Lascio la domanda libera...
Approfondiro' dopo... :-)

Cosa sono i B-Tree e come sono costruiti ?

Grazie.

mondobimbi
16-10-2004, 16:55
B-tree=albero binario
è una struttura dati molto efficiente quando bilanciata.
Un nodo della struttura contiene una chiave, il puntatore ai dati e un puntatore ai nodi figli, destro e sinistro.
Nel sottoalbero sx vanno inseriti i nodi la cui chiava è minore della chiave del nodo di riferimento, nel sottoalbero dx quelli con chiave maggiore.
Un esempio di nodo in c++

class TNode {

char * key ;
void * data;

TNode * left;
TNode * right;

public:

...
...

}

internet
16-10-2004, 17:44
Originariamente inviato da _sys/sid
Da titolo... Lascio la domanda libera...
Approfondiro' dopo... :-)

Cosa sono i B-Tree e come sono costruiti ?

Grazie.

E' difficile spiegarlo in poche righe, ti posso dire che sono alberi auto-bilancianti i cui nodi contengono un numero variabile di elementi (chiavi), e sono diversi come struttura dagli alberi binary (binary trees).

http://cs.hbg.psu.edu/courses/comp419.taw.s97/btree.gif

La maggiorparte dei DBMS ne fa uso per la memorizzazione degli indici (creati esplicitamente in SQL tramite CREATE INDEX http://www.postgresql.org/docs/current/static/sql-createindex.html)

per maggiori info
http://www.bluerwhite.org/btree
http://sky.fit.qut.edu.au/~maire/baobab/lecture/sld001.htm

una demo in java
http://www.geocities.com/SiliconValley/Program/2864/File/btree.html

_sys/sid
16-10-2004, 18:08
Grazie Mille...
(Per adesso sono aposto...) :D

_sys/sid
16-10-2004, 20:02
Cosa vuol dire Struttura Bilanciata ???

Luc@s
16-10-2004, 20:47
Originariamente inviato da _sys/sid
Cosa vuol dire Struttura Bilanciata ???

at rigth < n
at center n
at left > n

Questo è bilanciato ;)

internet
16-10-2004, 21:00
Originariamente inviato da _sys/sid
Cosa vuol dire Struttura Bilanciata ???

Il bilanciamento a cui si riferisce quel link, è una proprietà di questi alberi, in cui nessuna foglia è più lontana dalla radice rispetto alle altre foglie. (la definizione esatta tiene conto della lunghezza di ogni cammino dalla radice a una foglia, e dipende dal tipo di alberi)

http://www.nist.gov/dads/HTML/balancedtree.html

albero non bilanciato


[a]
\
[b]
\
[c]
\
[d]
\
[e]


albero bilanciato


[c]
/ \
[b] [d]
/ \
[a] [e]

_sys/sid
17-10-2004, 11:05
Ok... Per il Momento risposte e link, sembrano piu' che soddisfacenti...

Grazie Mille a tutti. :ciauz:

Loading