Strutture dati utilizzate nel DBMS

Question

Quali sono le strutture dati utilizzate in DBMS come Oracle, MySQL & amp; Sqlite per l'archiviazione e il recupero di record.

Answer 1

MySQL ha sistemi di archiviazione collegabili. Ciò significa che il motore può utilizzare diversi depositi. Ne ha attualmente 5-6 che puoi usare. E poiché è open source, puoi vedere come è fatto.

SQLite utilizza la propria implementazione B-Tree con journaling. Open source: puoi vederlo.

Firebird e Interbase utilizzano B-Trees con sistemi di controllo delle versioni multi-record per l'archiviazione. Firebird è open source. Vale la pena cercare.

Non posso dire per Oracle , MS SQL Server o altri sistemi di database proprietari, poiché mantengono segrete le informazioni di archiviazione.

Answer 2

Di solito un'implementazione intelligente di B-Trees

Dall'articolo di Wikipedia collegato sopra:

  

Un albero B di ordine m (il numero massimo di figli per ciascun nodo) è un albero che soddisfa le seguenti proprietà:

     

  
1. Ogni nodo ha al massimo m figli.
  
2. Ogni nodo (tranne radice e foglie) ha almeno m & # 8260; 2 figli.
  
3. La radice ha almeno due figli se non è un nodo foglia.
  
4. Tutte le foglie appaiono allo stesso livello e contengono informazioni.
  
5. Un nodo non foglia con k figli contiene k & # 8211; 1 chiavi
  

I vantaggi sono che è possibile accedere ai dati in tempo logaritmico, come nella maggior parte degli alberi di ricerca (come gli alberi binari standard), ma le proprietà di temporizzazione sono migliori nel caso medio.