Newsgroup: it.comp.software.database
Titolo: Hash vs B+-tree

   Devo implementare un minimo motore per l'accesso ai dati organizzati 
in tuple su file e sono indeciso se inidicizzarli mediante tabella di 
hash (indiretta) o con una struttura ad albero bilanciato (sempre 
indiretta). Quel che so e` che la prima struttura permette un accesso ai 
dati con tempo costante mentre la seconda ammette un tempo logaritmico e 
che quest'ultima consente maggiore flessibilita` nell'inserimento e 
nella rimozione degli elementi, mentre la prima mi sembra piu` semplice 
da implementare. Voi cosa mi consigliereste?
-- 
Alla prossima,
Marco

 wrote in message 
news:lNJG9.17615$t_1.1...@tornado.fastwebnet.it...

Ciao Marco,
prendi le mie motivazioni con le pinze perche' non sono mai
andato a fondo sugli Hash Index, ho solo letto alcune
considerazioni senza mai andare a fondo analizzando la
complessita algoritmica di questa tecnica.
Da quello che ho capito gli hash index sono molto efficienti per
le ricerce puntuali (operatore di uguaglianza), ma offrono solitamente
prestazioni scarse nelle operazioni di ordinamento e di ricerche per
intervalli di valori.
I B+-Tree offrono delle prestazioni comunque comparabili, in fase
di ricerca puntuale, e solitamente superiori per ricerche piu'
generalizzate.
Tieni conto che il B+-Tree e' una struttura molto "flat", pochi
livelli permettono di indicizzare milioni di righe, quindi solitamente
in una ricerca puntuale (index seek) e' sufficiente "navigare"
pochi livelli.
I B+-Tree inoltre, come fai notare, sono piu' flessibili in fase
di menutenzione.
Tieni conto che la maggior parte degli RDBMS utilizzano le strutture
B-Tree come struttura principale per gli indici (anche se alcuni
permettono di creare altre tipologie di indice tipo R-Tree, GiST ecc).
Ci sono poi delle consderazioni legate anche all'implementazione
degli algoritmi di "Join" che sono interessarti.
SQL Server, per esempio, puo' utilizzare gli algoritmi "Inner Loop"
e "Merge" se ha a disposzione i necessari indici, altrimenti puo'
costruire dinamicamente una hash table per sviluppare l'operazione.
Funziona piu' o meno come spiegato in questo articolo di
Zeller e Gray:
"Adaptive Hash Join for a Multiprogramming Environment"
http://www.acm.org/sigmod/vldb/conf/1990/P186.PDF
Comunque se fai delle ricerche con Googles ci sono delle discussioni
in comp.databases.theory, ad esempio:
http://groups.google.com/groups?hl=en&lr=&ie=UTF-8&threadm=R.521s19%2425u%40gaea.titan.org&rnum=24&prev=/groups%3Fq%3Dhash%2Bindexes%2Bgroup:comp.databases.theory%26hl%3Den%26lr%3D%26ie%3DUTF-8%26scoring%3Dd%26start%3D20%26sa%3DN
Anche sul sito SIGMOD ci sono degli articoli a riguardo
http://www.acm.org/sigmod/
 (se trovi qualche cosa di interessante
ti sarei grato se me lo comunicassi, sopratutto se riguarda un'analisi
formale della complessita').
Ciao,
-- 
Gianluca Hotz
Backoffice MVP (SQL Server) MCP SQL Server and MCP Windows
Vice-President of the Italian User Group for SQL Server
Founding Member of the Italian User Group for .NET
http://www.ghotz.com
http://www.ugiss.org

 formale della complessita').
   Ok, se scopro qualcosa di utile, lo rendo pubblico qui sul newsgroup.
-- 
Alla prossima,
Marco