Qual è l'algoritmo per la ricerca di query nel database?

Question

Buongiorno a tutti, attualmente sto facendo ricerche sull'ottimizzazione degli algoritmi di ricerca.

A partire da ora, sto effettuando ricerche sul database.

In un database con supporto SQL.

Posso scrivere la query per una tabella specifica.

1. Selezionare il numero da Tabella1 dove Nome = "Test";
2. Selezionare * da Tabella1 dove Nome = "Test";

1 ricerca il numero da Tabella1 da dove il nome è Test e 2 ricerca tutta la colonna per il nome Test.

Capisco il concetto della funzione, tuttavia ciò che mi interessa sapere quale è l'approccio della ricerca?

E 'solo una semplice ricerca lineare dove dal primo indice fino all'ennesimo indice si afferra finché la condizione è vera avendo così O (n) velocità o ha un algoritmo unico che velocizza il suo processo?

Answer 1

domanda molto buona, ma può avere molte risposte a seconda della struttura della tabella e come è normalizzata ...

solito per effettuare una Seacrh in una query SELECT il DBMS ordina la tabella (che utilizza mergesort perché questo algoritmo è valido per I/O su disco, non quicksort), quindi a seconda degli indici (se la tabella ha) corrisponde solo ai numeri, ma se la struttura è più complessa il DBMS può eseguire una ricerca in un albero, ma questo è troppo profondo, fammi ricapitolare nei miei appunti che ho preso.

Si consiglia di attivare il piano di esecuzione query, here is an example in come farlo in SQL Server 2008. E quindi eseguire l'istruzione SELECT con la clausola WHERE e si sarà in grado di iniziare a capire cosa sta succedendo all'interno del DBMS.

Answer 2

Se non ci sono indici, allora sì, viene eseguita una ricerca lineare.

Tuttavia, i database utilizzano in genere un indice B Tree quando si specifica una (e) colonna (e) come chiave. Si tratta di formati speciali di strutture dati che sono sintonizzati in modo specifico (fattori di ramificazione di B Tree alti) per ottenere prestazioni ottimali sull'hardware del disco magnetico, dove il fattore di perdita di tempo più significativo è l'operazione di ricerca (la testina magnetica deve spostarsi in una parte del file).

Si può pensare all'indice come una copia ordinata/strutturata dei valori in una colonna. Può essere determinato rapidamente se il valore cercato è nell'indice. Se lo trova, troverà anche un puntatore che punta alla posizione corretta della riga corrispondente nel file di dati principale (in modo che possa andare a leggere le altre colonne nella riga). A volte un indice multi-colonna contiene tutti i dati richiesti dalla query, quindi non è necessario tornare al file principale, può solo leggere ciò che ha trovato e quindi farlo.

Esistono altri tipi di indici, ma penso che tu abbia l'idea: duplicare i dati e organizzarli in modo veloce da cercare.

Su un database di grandi dimensioni, gli indici fanno la differenza tra l'attesa di una frazione di secondo, o forse giorni per il completamento di una query complessa.

btw- Gli alberi B non sono una struttura di dati semplice e di facile comprensione, e l'algoritmo di attraversamento è anche complesso. Inoltre, l'attraversamento è ancora più brutto della maggior parte del codice che si trova, perché in un database vengono costantemente caricati/scaricati blocchi di dati dal disco e gestiti in memoria, e questo notevolmente migliora il codice. Ma, se hai familiarità con binary search trees, allora penso che tu capisca abbastanza bene il concetto.

Answer 3

Bene, dipende da come vengono memorizzati i dati e cosa si sta tentando di fare.

• Come già indicato, una struttura comune per il mantenimento delle voci è un B+ tree. L'albero è ben ottimizzato per il disco poiché i dati effettivi vengono memorizzati solo nelle foglie e le chiavi sono archiviate nei nodi interni. Solitamente consente un numero molto limitato di accessi al disco poiché i livelli superiori dello k dell'albero possono essere memorizzati nella RAM, e solo i pochi livelli inferiori verranno memorizzati su disco e richiedono una lettura del disco per ciascuno.
• Altre alternative sono un hash table. Mantieni in memoria (RAM) un array di "puntatori" - questi puntatori indicano un indirizzo del disco, che contiene un bucket che include tutte le voci con il valore hash corrispondente. Usando questo metodo, hai solo bisogno degli accessi al disco O(1) (che di solito è il collo di bottiglia quando si occupano di basi di dati), quindi dovrebbe essere relativamente veloce.
  Tuttavia, una tabella hash non consente query di intervallo efficienti (che possono essere eseguite in modo efficiente in un albero B +).

Lo svantaggio di tutto quanto sopra è che richiede una sola chiave - vale a dire se la tabella hash o B + albero è costruito secondo il campo "id" del rapporto, e poi si esegue una ricerca in base alla chiave" "- Diventa inutile.
Se si desidera garantire una ricerca rapida di tutti i campi della relazione, sono necessarie diverse strutture, ciascuna in base a una chiave diversa, che non è molto efficiente in termini di memoria.

Ora, ci sono molte ottimizzazioni da considerare in base all'utilizzo specifico. Se per esempio il numero di ricerche è molto piccolo (diciamo il loglogN più piccolo delle operazioni totali), il mantenimento di un albero B + è nel complesso meno efficiente di quanto basta memorizzare gli elementi come elenco e nelle rare occasioni di una ricerca - basta fare un ricerca lineare.