Estructures d'emmagatzemament de bases de dades

Les taules de les bases de dades i els índexs típicament s'emmagatzemen en memòria secundària (disc dur). Hi ha diverses formes d'emmagatzemar aquesta informació (fitxers plans ordenats o no ordenats, ISAM, piles, taules de hash, Arbres B+...). Aquest article vol analitzar aquestes opcions i els seus corresponents avantatges i inconvenients.

Sistemes d'emmagatzematge

Fitxers plans

El concepte de base de dades en fitxer pla es refereix a diferents mètodes que es poden utilitzar per codificar un model de dades (típicament una taula) en un fitxer de text pla.

Normalment cada fila del fitxer representa un registre de la taula i els camps de la taula estan limitats per algun tipus de separador (un espai, una coma, un punt i coma, etc.) o per una mida fixa del camp. En alguns casos pot ser necessari utilitzar elements extres per delimitar els camps (per exemple alguna forma d'escapar el delimitador quan aquest forma part d'un camp de la base de dades). En aquest model no hi ha definició de relacions entre els elements.

Aquest model s'anomena pla per què tot s'emmagatzema en un sol fitxer sense relacions ni models complexes com els utilitzats per exemple en una base de dades relacional.

Un dels formats més comuns de fitxer pla és el Comma Separated Values (CSV) i és suportat per múltiples gestors de bases de dades com una forma simple de fer còpies de seguretat o d'importar o exportar dades en una base de dades relacional.

El clàssic exemple de base de dades de fitxer pla pot ser la típica llista d'adreces o agenda. Aquesta base de dades consisteix en un nombre fix de camps (Nom, Cognoms, número de telèfon, etc.) i cada fila del fitxer representa un registre (adreça o contacte). Un altre exemple pot ser una taula HTML.

Aquests tipus de base de dades són les més fàcils d'implementar (es poden fer a mà en un paper, utilitzant un processador de text simple, etc.)

XML és possiblement en l'actualitat el format de text pla més utilitzat per emmagatzemar dades. Però cal tenir en compte que XML permet tot un complex sistema d'estructures de dades niades i jeràrquiques que l'allunyen del model de fitxer pla.

Hi ha dos tipus de fitxers plans:

• Ordenats: també s'anomenen llistes enllaçades. Els registres s'emmagatzemen en ordre i normalment cal reorganitzar els fitxer cada cop que s'insereix un registre. El cost d'inserció d'un registre és molt ineficient però les cerques (al tenir ordenat el fitxer) es poden realitzar mitjançant algorismes de cost asimptòtic logarítmic (O(log(n))) com per exemple l'algorisme de cerca binària.

• No ordenats: Els registres s'emmagatzemen en el fitxer en l'ordre en què són inserits. Aquest algorisme té un cost d'inserció asimptòtic fix però a canvi té un cost asimptòtic de cerca lineal. La majoria de bases de dades actual utilitzen un índex per a les claus primàries que solucionen aquest problema.

Implementacions

• TextDB una base de dades basada en fitxers plans.
• SQLite és una llibreria C que implementa un gestor de base de dades SQL autocontingut, encastable i de configuració zero.

Fitxers estructurats

Piles

Les piles són una estructura de dades que es pot utilitzar per emmagatzemar bases de dades. Les seves característiques són:

• És un dels mètodes més bàsics i simples
• La inserció és una operació eficient (els registres es guarden al final del fitxer)
• L'obtenció de les dades és poc eficient, ja que cal cercar tot la pila (no està ordenada) i per tant té un cost asimptòtic lineal.

Avantatges:

• Són un bon sistema per a bolcar dades ràpidament
• És un bon sistema per a grups de dades petits.

Inconvenients:

• No és un sistema eficient per obtenir registres a partir d'una clau, especialment si la pila és gran.
• Ordenar la pila és una operació costosa.

Arbres B+

Aquest sistema és en teoria el més utilitzat.

Vegeu l'article sobre arbres.

ISAM

Vegeu l'article sobre ISAM.