In MySQL, un tipo di indice è un b-albero, e accedere a un elemento in un b-albero è in logaritmica tempo ammortizzato O(log(n)).B-Tree vs Hash Table
D'altra parte, l'accesso ad un elemento in una tabella hash è in O(1).
Perché una tabella di hash non viene utilizzata al posto di un albero b per accedere ai dati all'interno di un database?
È possibile accedere agli elementi solo tramite la chiave primaria in una tabella hash. Questo è più veloce che con un algoritmo di albero (O(1) invece di log(n)), ma non è possibile selezionare gli intervalli (tutto il resto x e y). Gli algoritmi albero supportano questo valore in Log(n) dove un indice hash può comportare una scansione completa della tabella O(n). Anche il sovraccarico costante degli indici hash è in genere maggiore (che non è un fattore nella notazione theta, ma esiste ancora). anche algoritmi ad albero sono di solito più facile da mantenere, crescere con i dati, la scala, ecc
indici hash lavorare con i formati predefiniti hash, così si finisce con alcune "secchi" in cui gli oggetti vengono memorizzati in. Questi oggetti sono ricollegati per trovare davvero quello giusto all'interno di questa partizione.
Quindi, se si dispone di piccole dimensioni si hanno un sacco di overhead per piccoli elementi, grandi formati risultato in un'ulteriore scansione.
Gli algoritmi di tabelle hash di oggi sono generalmente in scala, ma il ridimensionamento può essere inefficiente.
Esistono infatti algoritmi di hashing scalabili. Non chiedermi come funziona - è un mistero anche per me. AFAIK si sono evoluti dalla replica scalabile dove re-hashing non è facile.
sua chiamata rush - R eplication U mirino S calable H incenerimento, e questi algoritmi sono quindi chiamati algoritmi RUSH.
Tuttavia, potrebbe esserci un punto in cui l'indice supera una dimensione tollerabile rispetto alle dimensioni dell'hash e l'intero indice deve essere ricostruito. Di solito questo non è un problema, ma per enormi enormi database, questo può richiedere giorni.
Il compromesso per algoritmi ad albero è piccolo e sono adatti per quasi tutti i casi l'uso e, quindi, sono di default.
Tuttavia, se si dispone di un caso d'uso molto preciso e si sa esattamente cosa e solo ciò che sta per essere necessario, è possibile usufruire di indici di hashing.
Puoi spiegare di più sulla ricostruzione dell'indice? Significa che per x giorni mentre l'indice viene ricostruito, la tabella è totalmente non disponibile per l'uso durante quel periodo? – Pacerier
che dipende dal sistema di database in uso. la domanda riguardava solo gli aspetti teorici. Non conosco i dettagli di implementazione dei sistemi di database comuni. ma di solito questo non dovrebbe essere il caso perché il secondo indice può essere costruito mentre il primo è ancora in uso –
La complessità temporale hashtables è costante solo per hashtables sufficientemente dimensioni (ci devono essere abbastanza secchi per contenere i dati). La dimensione di una tabella di database non è nota in anticipo, quindi la tabella deve essere modificata di tanto in tanto per ottenere prestazioni ottimali da una tabella hash. Il rehashing è anche costoso.
È possibile eseguire nuovamente il ritrasferimento mentre db è online? O dobbiamo bloccare il tavolo per riordinare tutto? – Pacerier
Pacerier, MySQL non supporta gli indici hash. È teoricamente possibile ripetere l'indice mentre il database è ancora online (continuare a usare il vecchio indice, creare un nuovo indice, passare a quello nuovo quando è finito), ma non so cosa potrebbe fare MySQL se implementato Indici hash. –
MySQL supporta gli indici hash giusto? : http://dev.mysql.com/doc/refman/5.5/en/index-btree-hash.html – Pacerier
Penso che Hashmaps non sia scalabile, e può essere costoso quando è necessario ridisegnare l'intera mappa.
In realtà, sembra che MySQL utilizzi entrambi i tipi di indici o una tabella hash o un b-tree in base al seguente link.
La differenza tra l'utilizzo di un b-albero e una tabella di hash è che il primo consente di utilizzare confronti colonna nelle espressioni che utilizzano l'=,>,> =, <, < =, o tra gli operatori, mentre il secondo viene utilizzato solo per i confronti di uguaglianza che utilizzano gli operatori = o < =>.
Questo è ingiusto. La miglior risposta ha il punteggio più basso. –
Questo è esattamente quello che stavo cercando. Mi importa di come influisce sulle mie domande piuttosto che su un'analisi tecnica. –
Le tabelle hash non supportano le query di intervallo e non possono crescere o ridursi uniformemente durante l'operazione. –
@HenningMakholm Perché non hash per le colonne che non richiedono query di intervallo? – Pacerier