Estructuras de almacenamiento de bases de datos

Las tablas e índices de bases de datos se pueden almacenar en el disco en una de varias formas, incluidos archivos planos ordenados/desordenados , ISAM , archivos de montón, contenedores de hash o árboles B+ . Cada forma tiene sus propias ventajas y desventajas particulares. Las formas más utilizadas son los árboles B y los ISAM. Dichas formas o estructuras son un aspecto del esquema general utilizado por un motor de base de datos para almacenar información.

El almacenamiento desordenado generalmente almacena los registros en el orden en que se insertan. Este tipo de almacenamiento ofrece una buena eficiencia de inserción ( ), pero tiempos de recuperación ineficientes ( ). Sin embargo, estos tiempos de recuperación suelen ser mejores, ya que la mayoría de las bases de datos utilizan índices en las claves principales , lo que da como resultado tiempos de recuperación de o para claves que son iguales a los desplazamientos de filas de la base de datos dentro del sistema de almacenamiento. ^{[ cita requerida ]}${\displaystyle O\izquierda(1\derecha)}$${\displaystyle O\izquierda(n\derecha)}$${\displaystyle O\left(\log n\right)}$${\displaystyle O\izquierda(1\derecha)}$

El almacenamiento ordenado generalmente almacena los registros en orden y puede ser necesario reorganizarlos o aumentar el tamaño del archivo cuando se inserta un nuevo registro, lo que da como resultado una menor eficiencia de inserción. Sin embargo, el almacenamiento ordenado proporciona una recuperación más eficiente ya que los registros están preordenados, lo que da como resultado una complejidad de . ^{[ cita requerida ]}${\displaystyle O\left(\log n\right)}$

Los archivos de montón son listas de registros desordenados de tamaño variable. Aunque comparten un nombre similar, los archivos de montón son muy diferentes de los montones en memoria . Los montones en memoria están ordenados, a diferencia de los archivos de montón.

• El método más simple y básico
  • inserción eficiente, con nuevos registros agregados al final del archivo, proporcionando orden cronológico
  • La recuperación es eficiente cuando el identificador de la memoria es la dirección de la memoria.
  • La búsqueda es ineficiente, ya que la búsqueda debe ser lineal.
  • La eliminación se realiza marcando los registros seleccionados como "eliminados".
  • requiere reorganización periódica si el archivo es muy volátil (cambia con frecuencia)
• Ventajas
  • Eficiente para la carga masiva de datos
  • Eficiente para relaciones relativamente pequeñas, ya que se evitan los gastos generales de indexación.
  • Eficiente cuando las recuperaciones involucran una gran proporción de registros almacenados
• Desventajas
  • No es eficiente para la recuperación selectiva utilizando valores clave, especialmente si son grandes.
  • La clasificación puede llevar mucho tiempo
  • No apto para tablas volátiles.

• Las funciones hash calculan la dirección de la página en la que se almacenará el registro en función de uno o más campos del registro.
  • Funciones hash elegidas para garantizar que las direcciones se distribuyan uniformemente en el espacio de direcciones.
  • La 'ocupación' es generalmente del 40% al 60% del tamaño total del archivo
  • Dirección única no garantizada, por lo que se requieren mecanismos de detección y resolución de colisiones.
• Direccionamiento abierto
• Desbordamiento encadenado/desencadenado
• Pros y contras
  • Eficiente para coincidencias exactas en campos clave
  • No apto para recuperación de rango, que requiere almacenamiento secuencial.
  • Calcula dónde se almacena el registro en función de los campos del registro.
  • Las funciones hash garantizan una distribución uniforme de los datos
  • Las colisiones son posibles, por lo que se requiere detección y restauración de colisiones.

Éstos son los más utilizados en la práctica.

• El tiempo que se tarda en acceder a cualquier registro es el mismo porque se busca el mismo número de nodos.
• El índice es un índice completo, por lo que no es necesario ordenar el archivo de datos.
• Pros y contras
  • Estructura de datos versátil: acceso secuencial y aleatorio
  • El acceso es rápido
  • Admite coincidencias exactas, de rango, de clave parcial y de patrones de manera eficiente.
  • Los archivos volátiles se manejan de manera eficiente porque el índice es dinámico: se expande y se contrae a medida que la tabla crece y se encoge.
  • menos adecuado para archivos relativamente estables: en este caso, ISAM es más eficiente

La mayoría de las bases de datos relacionales convencionales utilizan un almacenamiento "orientado a filas", lo que significa que todos los datos asociados con una fila determinada se almacenan juntos. Por el contrario, los DBMS orientados a columnas almacenan todos los datos de una columna determinada juntos para poder atender con mayor rapidez las consultas de estilo almacén de datos . Las bases de datos de correlación son similares a las bases de datos basadas en filas, pero aplican una capa de indirección para asignar múltiples instancias del mismo valor al mismo identificador numérico.

• Índice de base de datos
• ISMA