Internos de la base de datos

Capítulo 1. Introducción y visión general

Este trabajo se ha traducido utilizando IA. Agradecemos tus opiniones y comentarios: [e-mail]

Los sistemas de gestión de bases de datos pueden servir para diferentes propósitos: algunos se utilizan principalmente para datos temporales en caliente, otros sirven como almacenamiento en frío de larga duración, otros permiten consultas analíticas complejas, otros sólo permiten acceder a los valores por la clave, otros están optimizados para almacenar datos de series temporales y otros almacenan grandes blobs de forma eficiente. Para entender las diferencias y establecer distinciones, empezamos con una breve clasificación y visión general, ya que nos ayuda a comprender el alcance de los debates posteriores.

A veces la terminología puede ser ambigua y difícil de entender sin un contexto completo. Por ejemplo, las distinciones entre almacenes de columnas y de columnas anchas que tienen poco o nada que ver entre sí, o cómo se relacionan los índices agrupados y no agrupados con las tablas organizadas por índices. Este capítulo pretende desambiguar estos términos y encontrar sus definiciones precisas.

Empezaremos con una visión general de la arquitectura de los sistemas de gestión de bases de datos (ver "Arquitectura de los SGBD"), y hablaremos de los componentes del sistema y sus responsabilidades. A continuación, hablaremos de las diferencias entre los sistemas de gestión de bases de datos en cuanto al medio de almacenamiento (véase "SGBD basados en memoria frente a los basados en disco") y la disposición (véase "SGBD orientados a columnas frente a los orientados a filas").

Estos dos grupos no presentan una taxonomía completa de los sistemas de gestión de bases de datos y hay muchas otras formas de clasificarlos. Por ejemplo, algunas fuentes agrupan los SGBD en tres grandes categorías:

Bases de datos de procesamiento de transacciones en línea (OLTP)

Estos gestionan un gran número de solicitudes y transacciones de cara al usuario. Las consultas suelen ser predefinidas y de corta duración.

Bases de datos de procesamiento analítico en línea (OLAP)

Estas manejan agregaciones complejas. Las bases de datos OLAP se utilizan a menudo para análisis y almacenamiento de datos, y son capaces de gestionar consultas ad hoc complejas y de larga duración.

Procesamiento transaccional y analítico híbrido (HTAP)

Estas bases de datos combinan las propiedades de los almacenes OLTP y OLAP.

Existen muchos otros términos y clasificaciones: almacenes clave-valor, bases de datos relacionales, almacenes orientados a documentos y bases de datos de grafos. Estos conceptos no se definen aquí, ya que se supone que el lector tiene un conocimiento y comprensión de alto nivel de su funcionalidad. Dado que los conceptos que tratamos aquí son ampliamente aplicables y se utilizan en la mayoría de los tipos de almacenes mencionados en alguna capacidad, no es necesaria ni importante una taxonomía completa para el debate posterior.

Dado que la Parte I de este libro se centra en las estructuras de almacenamiento e indexación, necesitamos comprender los enfoques de organización de datos de alto nivel, y la relación entre los archivos de datos y los archivos de índices (consulta "Archivos de datos y archivos de índices").

Por último, en "Almacenamiento en búfer, inmutabilidad y ordenación", analizamos tres técnicas muy utilizadas para desarrollar estructuras de almacenamiento eficientes y cómo influye la aplicación de estas técnicas en su diseño e implementación.

Arquitectura del SGBD

No existe un plano común para el diseño de sistemas de gestión de bases de datos. Cada base de datos se construye de forma ligeramente distinta, y los límites de los componentes son algo difíciles de ver y definir. Aunque estos límites existan sobre el papel (por ejemplo, en la documentación del proyecto), en el código componentes aparentemente independientes pueden estar acoplados debido a optimizaciones de rendimiento, manejo de casos perimetrales o decisiones arquitectónicas.

Las fuentes que describen la arquitectura de los sistemas de gestión de bases de datos (por ejemplo, [HELLERSTEIN07], [WEIKUM01], [ELMASRI11] y [GARCIAMOLINA08]), definen los componentes y las relaciones entre ellos de forma diferente. La arquitectura presentada en la Figura 1-1 demuestra algunos de los temas comunes de estas representaciones.

Los sistemas de gestión de bases de datos utilizan un modelo cliente/servidor, en el que las instancias del sistema de bases de datos(nodos) adoptan el papel de servidores, y las instancias de las aplicaciones, el de clientes.

Las peticiones de los clientes llegan a través del subsistema de transporte. Las peticiones llegan en forma de consultas, la mayoría de las veces expresadas en algún lenguaje de consulta. El subsistema de transporte también es responsable de la comunicación con otros nodos del clúster de bases de datos.

Figura 1-1. Arquitectura de un sistema de gestión de bases de datos

Tras la recepción de, el subsistema de transporte entrega la consulta a un procesador de consultas, que la analiza, interpreta y valida. Posteriormente, se realizan las comprobaciones de control de acceso, ya que sólo se pueden hacer completamente una vez interpretada la consulta.

La consulta analizada en se pasa al optimizador de consultas, que primero elimina las partes imposibles y redundantes de la consulta, y luego intenta encontrar la forma más eficiente de ejecutarla basándose en estadísticas internas (cardinalidad de los índices, tamaño aproximado de las intersecciones, etc.) y colocación de los datos (qué nodos del clúster contienen los datos y los costes asociados a su transferencia). El optimizador se encarga tanto de las operaciones relacionales necesarias para la resolución de la consulta, que suele presentarse como un árbol de dependencias, como de las optimizaciones, como el ordenamiento de los índices, la estimación de la cardinalidad y la elección de los métodos de acceso.

La consulta suele presentarse en forma de plan de ejecución (o plan de consulta): una secuencia de operaciones que hay que realizar para que sus resultados se consideren completos. Dado que la misma consulta puede satisfacerse utilizando distintos planes de ejecución que pueden variar en eficacia, el optimizador elige el mejor plan disponible.

El plan de ejecución lo lleva a cabo el motor de ejecución, que agrega los resultados de las operaciones locales y remotas. La ejecución remota puede implicar la escritura y lectura de datos hacia y desde otros nodos del clúster, y la replicación.

Las consultas locales (procedentes directamente de los clientes o de otros nodos) son ejecutadas por el motor de almacenamiento. El motor de almacenamiento tiene varios componentes con responsabilidades específicas:

Gestor de transacciones

Este gestor de programa las transacciones y se asegura de que no puedan dejar la base de datos en un estado lógicamente incoherente.

Gestor de cerraduras

Este gestor bloquea los objetos de la base de datos para las transacciones en ejecución, garantizando que las operaciones concurrentes no violen la integridad física de los datos.

Métodos de acceso (estructuras de almacenamiento)

Estos gestionan el acceso y la organización de los datos en el disco. Los métodos de acceso incluyen archivos de montón y estructuras de almacenamiento como los Árboles B (consulta "Árboles B ubicuos") o los Árboles LSM (consulta "Árboles LSM").

Gestor de búferes

Este gestor almacena en caché las páginas de datos en memoria (ver "Gestión del búfer").

Gestor de recuperación

Este gestor de mantiene el registro de operaciones y restaura el estado del sistema en caso de fallo (ver "Recuperación").

Juntos, los gestores de transacciones y de bloqueos son responsables del control de la concurrencia (ver "Control de la concurrencia"): garantizan la integridad lógica y física de los datos, al tiempo que aseguran que las operaciones concurrentes se ejecuten con la mayor eficacia posible.

SGBD en memoria frente a SGBD en disco

Los sistemas de bases de datos almacenan los datos en memoria y en disco. Los sistemas de gestión de bases de datos en memoria (a veces llamados SGBD de memoria principal) almacenan los datos principalmente en memoria y utilizan el disco para la recuperación y el registro. Los SGBD basados en disco almacenan la mayor parte de los datos en disco y utilizan la memoria para almacenar en caché el contenido del disco o como almacenamiento temporal. Ambos tipos de sistemas utilizan el disco hasta cierto punto, pero las bases de datos de memoria principal almacenan su contenido casi exclusivamente en RAM.

Acceder a la memoria ha sido y sigue siendo varios órdenes de magnitud más rápido que acceder al disco,¹ por lo que resulta convincente utilizar la memoria como almacenamiento primario, y resulta más factible económicamente hacerlo a medida que bajan los precios de la memoria. Sin embargo, los precios de la RAM siguen siendo altos en comparación con los dispositivos de almacenamiento persistente, como los SSD y los HDD.

Los sistemas de bases de datos de memoria principal se diferencian de sus homólogos basados en disco no sólo por el medio de almacenamiento primario, sino también por las estructuras de datos, la organización y las técnicas de optimización que utilizan.

Las bases de datos que utilizan la memoria como almacén primario de datos lo hacen principalmente por rendimiento, costes de acceso comparativamente bajos y granularidad de acceso. Programar para la memoria principal también es significativamente más sencillo que hacerlo para el disco. Los sistemas operativos abstraen la gestión de la memoria y nos permiten pensar en términos de asignación y liberación de trozos de memoria de tamaño arbitrario. En el disco, tenemos que gestionar manualmente las referencias a los datos, los formatos de serialización, la memoria liberada y la fragmentación.

Los principales factores que limitan el crecimiento de las bases de datos en memoria son la volatilidad de la RAM (en otras palabras, la falta de durabilidad) y los costes. Dado que el contenido de la RAM no es persistente, los errores de software, las caídas, los fallos de hardware y los cortes de energía pueden provocar la pérdida de datos. Hay formas de garantizar la durabilidad, como las fuentes de alimentación ininterrumpida y la RAM respaldada por baterías, pero requieren recursos de hardware adicionales y experiencia operativa. En la práctica, todo se reduce a que los discos son más fáciles de mantener y tienen precios significativamente más bajos.

Es probable que la situación cambie a medida que aumenten la disponibilidad y la popularidad de las tecnologías de Memoria No Volátil (NVM) [ARULRAJ17]. El almacenamiento NVM reduce o elimina por completo (dependiendo de la tecnología exacta) la asimetría entre las latencias de lectura y escritura, mejora aún más el rendimiento de lectura y escritura, y permite el acceso direccionable por bytes.

Durabilidad en almacenes basados en memoria

Los sistemas de bases de datos en memoria mantienen copias de seguridad en disco para proporcionar durabilidad y evitar la pérdida de los datos volátiles. Algunas bases de datos almacenan los datos exclusivamente en memoria, sin ninguna garantía de durabilidad, pero no hablamos de ellas en el ámbito de este libro.

Antes de que la operación pueda considerarse completa, sus resultados deben escribirse en un archivo de registro secuencial. Hablaremos de los registros de escritura anticipada con más detalle en "Recuperación". Para evitar reproducir el contenido completo del registro durante el arranque o tras un fallo, los almacenes en memoria mantienen una copia de seguridad. La copia de seguridad se mantiene como una estructura ordenada en disco, y las modificaciones de esta estructura suelen ser asíncronas (desacopladas de las peticiones de los clientes) y se aplican por lotes para reducir el número de operaciones de E/S. Durante la recuperación, el contenido de la base de datos puede restaurarse a partir de la copia de seguridad y los registros.

Los registros de registro suelen aplicarse a la copia de seguridad por lotes. Una vez procesado el lote de registros, la copia de seguridad mantiene una instantánea de la base de datos para un momento determinado, y el contenido del registro hasta ese momento puede descartarse. Este proceso se denomina checkpointing. Reduce los tiempos de recuperación al mantener la base de datos residente en el disco con las entradas de registro más actualizadas, sin necesidad de que los clientes se bloqueen hasta que se actualice la copia de seguridad.

Nota

Es injusto decir que la base de datos en memoria es el equivalente de una base de datos en disco con una enorme caché de páginas (véase "Gestión del búfer"). Aunque las páginas se almacenan en caché en memoria, el formato de serialización y la disposición de los datos conllevan una sobrecarga adicional y no permiten el mismo grado de optimización que pueden alcanzar los almacenes en memoria.

Las bases de datos basadas en disco utilizan estructuras de almacenamiento especializadas, optimizadas para el acceso al disco. En memoria, los punteros pueden seguirse comparativamente con rapidez, y el acceso aleatorio en memoria es significativamente más rápido que el acceso aleatorio en disco. Las estructuras de almacenamiento basadas en disco suelen tener forma de árboles anchos y cortos (véase "Árboles para el almacenamiento basado en disco"), mientras que las implementaciones basadas en memoria pueden elegir entre un conjunto mayor de estructuras de datos y realizar optimizaciones que, de otro modo, serían imposibles o difíciles de implementar en disco [GARCIAMOLINA92]. Del mismo modo, manejar datos de tamaño variable en disco requiere una atención especial, mientras que en memoria suele ser cuestión de referenciar el valor con un puntero.

Para algunos casos de uso, es razonable suponer que todo un conjunto de datos va a caber en la memoria. Algunos conjuntos de datos están limitados por sus representaciones en el mundo real, como los registros de alumnos de las escuelas, los registros de clientes de las empresas o el inventario de una tienda online. Cada registro no ocupa más que unos pocos Kb, y su número es limitado.

SGBD orientados a columnas frente a los orientados a filas

La mayoría de los sistemas de bases de datos almacenan un conjunto de registros de datos, formados por columnas y filas en tablas. Un campo es la intersección de una columna y una fila: un único valor de algún tipo. Los campos que pertenecen a la misma columna suelen tener el mismo tipo de datos. Por ejemplo, si definimos una tabla que contenga registros de usuarios, todos los nombres serían del mismo tipo y pertenecerían a la misma columna. Una colección de valores que pertenecen lógicamente al mismo registro (normalmente identificados por la clave) constituye una fila.

Una de las formas de clasificar las bases de datos es por cómo se almacenan los datos en el disco: por filas o por columnas. Las tablas pueden dividirse horizontalmente (almacenando juntos los valores que pertenecen a la misma fila) o verticalmente (almacenando juntos los valores que pertenecen a la misma columna). La Figura 1-2 muestra esta distinción: (a) muestra los valores divididos por columnas, y (b) muestra los valores divididos por filas.

Figura 1-2. Disposición de datos en almacenes orientados a columnas y filas

Los ejemplos de sistemas de gestión de bases de datos orientados a filas son abundantes: MySQL, PostgreSQL y la mayoría de las bases de datos relacionales tradicionales. Los dos almacenes pioneros de código abierto orientados a columnas son MonetDB y C-Store (C-Store es un predecesor de código abierto de Vertica).

Disposición de datos por filas

Los sistemas de gestión de bases de datos orientados a filas almacenan los datos en registros o filas. Su disposición se asemeja bastante a la representación tabular de datos, en la que cada fila tiene el mismo conjunto de campos. Por ejemplo, una base de datos orientada a filas puede almacenar eficazmente entradas de usuarios, con nombres, fechas de nacimiento y números de teléfono:

| ID | Name  | Birth Date  | Phone Number   |
| 10 | John  | 01 Aug 1981 | [phone] |
| 20 | Sam   | 14 Sep 1988 | [phone] |
| 30 | Keith | 07 Jan 1984 | [phone] |

Este enfoque funciona bien para los casos en los que varios campos constituyen el registro (nombre, fecha de nacimiento y un número de teléfono) identificados unívocamente por la clave (en este ejemplo, un número que se incrementa monotónicamente). Todos los campos que representan un único registro de usuario suelen leerse juntos. Al crear registros (por ejemplo, cuando el usuario rellena un formulario de registro), también los escribimos juntos. Al mismo tiempo, cada campo puede modificarse individualmente.

Dado que los almacenes orientados a filas son más útiles en escenarios en los que tenemos que acceder a los datos por filas, almacenar filas enteras juntas mejora la localización espacial² [DENNING68].

Dado que el acceso a los datos en un medio persistente como un disco se realiza normalmente por bloques (en otras palabras, la unidad mínima de acceso al disco es un bloque), un único bloque contendrá los datos de todas las columnas. Esto es estupendo para los casos en los que queremos acceder a un registro de usuario completo, pero hace que las consultas que acceden a campos individuales de varios registros de usuario (por ejemplo, las consultas que sólo buscan los números de teléfono) sean más caras, ya que también se paginarán los datos de los demás campos.

Disposición de datos por columnas

Los sistemas de gestión de bases de datos orientados a columnas particionan los datos verticalmente (es decir, por columnas) en lugar de almacenarlos en filas. Aquí, los valores de una misma columna se almacenan contiguamente en el disco (en lugar de almacenar las filas contiguamente, como en el ejemplo anterior). Por ejemplo, si almacenamos cotizaciones históricas de bolsa, las cotizaciones se almacenan juntas. Almacenar los valores de las distintas columnas en archivos o segmentos de archivos separados permite realizar consultas eficientes por columnas, ya que se pueden leer en una sola pasada en lugar de consumir filas enteras y descartar los datos de las columnas que no se consultaron.

Los almacenes orientados a columnas son adecuados para cargas de trabajo analíticas que calculan agregados, como la búsqueda de tendencias, el cálculo de valores medios, etc. El procesamiento de agregados complejos puede utilizarse en casos en los que los registros lógicos tienen varios campos, pero algunos de ellos (en este caso, las cotizaciones de precios) tienen distinta importancia y suelen consumirse juntos.

Desde una perspectiva lógica, los datos que representan las cotizaciones bursátiles pueden seguir expresándose como una tabla:

| ID | Symbol | Date        | Price     |
| 1  | DOW    | 08 Aug 2018 | 24,314.65 |
| 2  | DOW    | 09 Aug 2018 | 24,136.16 |
| 3  | S&P    | 08 Aug 2018 | 2,414.45  |
| 4  | S&P    | 09 Aug 2018 | 2,232.32  |

Sin embargo, la disposición física de la base de datos basada en columnas tiene un aspecto totalmente distinto. Los valores que pertenecen a la misma columna se almacenan muy juntos:

Symbol: 1:DOW; 2:DOW; 3:S&P; 4:S&P
Date:   1:08 Aug 2018; 2:09 Aug 2018; 3:08 Aug 2018; 4:09 Aug 2018
Price:  1:24,314.65; 2:24,136.16; 3:2,414.45; 4:2,232.32

Para reconstruir tuplas de datos, que pueden ser útiles para uniones, filtrados y agregados de varias filas, necesitamos conservar algunos metadatos a nivel de columna para identificar con qué puntos de datos de otras columnas está asociada. Si lo haces explícitamente, cada valor tendrá que contener una clave, lo que introduce duplicación y aumenta la cantidad de datos almacenados. Algunos almacenes de columnas utilizan en su lugar identificadores implícitos (ID virtuales) y utilizan la posición del valor (en otras palabras, su desplazamiento) para asignarlo a los valores relacionados [ABADI13].

Durante los últimos años, probablemente debido a la creciente demanda de realizar consultas analíticas complejas sobre conjuntos de datos cada vez mayores, hemos visto en muchos nuevos formatos de archivo orientados a columnas, como Apache Parquet, Apache ORC, RCFile, así como almacenes orientados a columnas, como Apache Kudu, ClickHouse y muchos otros [ROY12].

Distinciones y optimizaciones

No basta con decir que las distinciones entre los almacenes en filas y en columnas radican únicamente en la forma en que se almacenan los datos. Elegir la disposición de los datos es sólo uno de los pasos de una serie de posibles optimizaciones a las que apuntan los almacenes en columnas.

La lectura de varios valores de la misma columna en una sola ejecución mejora significativamente la utilización de la caché y la eficiencia computacional. En las CPU modernas, se pueden utilizar instrucciones vectorizadas para procesar múltiples puntos de datos con una sola instrucción de CPU³ [DREPPER07].

Almacenar juntos valores que tienen el mismo tipo de datos (por ejemplo, números con otros números, cadenas con otras cadenas) ofrece una mejor relación de compresión. Podemos utilizar distintos algoritmos de compresión según el tipo de datos y elegir el método de compresión más eficaz para cada caso.

Para que decida si utilizar un almacén orientado a columnas o a filas, debes conocer tus patrones de acceso. Si los datos leídos se consumen en registros (es decir, se solicitan la mayoría o todas las columnas) y la carga de trabajo consiste principalmente en consultas puntuales y escaneos de rangos, es probable que el enfoque orientado a filas dé mejores resultados. Si los escaneos abarcan muchas filas, o calculan agregados sobre un subconjunto de columnas, merece la pena considerar un enfoque orientado a columnas.

Tiendas de columna ancha

Las bases de datos orientadas a columnas no deben confundirse con los almacenes de columnas anchas, como BigTable o HBase, donde los datos se representan como un mapa multidimensional, las columnas se agrupan en familias de columnas (que suelen almacenar datos del mismo tipo), y dentro de cada familia de columnas, los datos se almacenan por filas. Esta disposición es la mejor para almacenar datos recuperados por una clave o una secuencia de claves.

Un ejemplo canónico del artículo Bigtable [CHANG06] es una Tabla Web. Una Tabla Web almacena instantáneas del contenido de una página web, sus atributos y las relaciones entre ellos en un momento determinado. Las páginas se identifican por la URL invertida, y todos los atributos (como el contenido de la página y los anclajes, que representan enlaces entre páginas) se identifican por las marcas de tiempo en las que se tomaron esas instantáneas. De forma simplificada, puede representarse como un mapa anidado, como muestra la Figura 1-3.

Figura 1-3. Estructura conceptual de una Tabla Web

Los datos se almacenan en un mapa ordenado multidimensional con índices jerárquicos: podemos localizar los datos relacionados con una página web concreta por su URL invertida y sus contenidos o anclas por la marca de tiempo. Cada fila está indexada por su clave de fila. Las columnas relacionadas se agrupan en familias de columnas -contents y anchor en este ejemplo- que se almacenan en disco por separado. Cada columna dentro de una familia de columnas se identifica por la clave de columna, que es una combinación del nombre de la familia de columnas y un calificador (html, cnnsi.com, my.look.ca en este ejemplo). Las familias de columnas almacenan varias versiones de los datos por fecha y hora. Esta disposición nos permite localizar rápidamente las entradas de nivel superior (páginas web, en este caso) y sus parámetros (versiones del contenido y enlaces a las otras páginas).

Aunque es útil comprender la representación conceptual de los almacenes de columnas anchas, su disposición física es algo diferente. En la Figura 1-4 se muestra una representación esquemática de la disposición de los datos en familias de columnas: las familias de columnas se almacenan por separado, pero en cada familia de columnas, los datos que pertenecen a la misma clave se almacenan juntos.

Figura 1-4. Estructura física de una Mesa Web

Ficheros de datos y ficheros índice

El objetivo principal de un sistema de base de datos es almacenar datos y permitir un acceso rápido a ellos. Pero, ¿cómo se organizan los datos? ¿Por qué necesitamos un sistema de gestión de bases de datos y no sólo un montón de archivos? ¿Cómo mejora la eficacia la organización de los archivos?

Los sistemas de bases de datos utilizan archivos para almacenar los datos, pero en lugar de basarse en jerarquías de directorios y archivos del sistema de archivos para localizar los registros, componen archivos utilizando formatos específicos de la implementación. Las principales razones para utilizar una organización de archivos especializada en lugar de archivos planos son:

Eficacia de almacenamiento

Los archivos se organizan de forma que se minimice la sobrecarga de almacenamiento por registro de datos almacenado.

Eficacia de acceso

Los registros pueden localizarse en el menor número posible de pasos.

Actualizar la eficiencia

Las actualizaciones de los registros se realizan de forma que se minimice el número de cambios en el disco.

Los sistemas de bases de datos almacenan registros de datos, formados por múltiples campos, en tablas, donde cada tabla suele representarse como un archivo independiente. Cada registro de la tabla puede consultarse mediante una clave de búsqueda. Para localizar un registro, los sistemas de bases de datos utilizan índices: estructuras de datos auxiliares que permiten localizar eficazmente los registros de datos sin escanear una tabla entera en cada acceso. Los índices se construyen utilizando un subconjunto de campos que identifican el registro.

Un sistema de base de datos suele separar los archivos de datos y los archivos de índice: los archivos de datos almacenan registros de datos, mientras que los archivos de índice almacenan metadatos de registros y los utilizan para localizar registros en los archivos de datos. Los archivos índice suelen ser más pequeños que los archivos de datos. Los archivos se dividen en páginas, que suelen tener el tamaño de uno o varios bloques de disco. Las páginas pueden organizarse como secuencias de registros o como páginas ranuradas(ver "Páginas ranuradas").

Los registros nuevos (inserciones) y las actualizaciones de los existentes se representan mediante pares clave/valor. La mayoría de los sistemas de almacenamiento modernos no borran los datos de las páginas explícitamente. En su lugar, utilizan marcadores de borrado (también llamados lápidas), que contienen metadatos de borrado, como una clave y una marca de tiempo. El espacio ocupado por los registros sombreados por sus actualizaciones o marcadores de borrado se recupera durante la recogida de basura, que lee las páginas, escribe los registros vivos (es decir, no sombreados) en el nuevo lugar, y descarta los sombreados.

Ficheros de datos

Los archivos de datos (a veces llamados archivos primarios) pueden implementarse como tablas organizadas por índices (IOT), tablas organizadas por montones (archivos heap) o tablas organizadas por hash (archivos hashed).

No es necesario que los registros de los archivos de montón sigan un orden determinado, y la mayoría de las veces se colocan en orden de escritura. De este modo, no es necesario realizar ningún trabajo adicional ni reorganizar el archivo cuando se añaden nuevas páginas. Los ficheros montón requieren estructuras de índice adicionales, que apunten a las ubicaciones donde se almacenan los registros de datos, para que puedan buscarse.

En los archivos hash, los registros se almacenan en cubos, y el valor hash de la clave determina a qué cubo pertenece un registro. Los registros del bucket pueden almacenarse en orden de apéndice u ordenados por clave para mejorar la velocidad de búsqueda.

Las tablas organizadas por índices (IOT) almacenan registros de datos en el propio índice. Dado que los registros se almacenan en orden de clave, los escaneos de rango en las IOT pueden implementarse escaneando secuencialmente su contenido.

Almacenar registros de datos en el índice nos permite reducir el número de búsquedas en disco en al menos una, ya que después de recorrer el índice y localizar la clave buscada, no tenemos que dirigirnos a un archivo distinto para encontrar el registro de datos asociado.

Cuando los registros se almacenan en un archivo independiente, los archivos de índice contienen entradas de datos, que identifican de forma única los registros de datos y contienen información suficiente para localizarlos en el archivo de datos. Por ejemplo, podemos almacenar desplazamientos de archivos (a veces llamados localizadores de filas), ubicaciones de registros de datos en el archivo de datos, o ID de bucket en el caso de archivos hash. En las tablas organizadas por índices, las entradas de datos contienen registros de datos reales.

Ficheros índice

Un índice es una estructura que organiza los registros de datos en disco de forma que se faciliten las operaciones de recuperación. Los archivos de índices se organizan como estructuras especializadas que asignan claves a ubicaciones en los archivos de datos donde se almacenan los registros identificados por dichas claves (en el caso de archivos de montón) o claves primarias (en el caso de tablas organizadas por índices).

Un índice sobre un fichero primario (de datos) se denomina índice primario. En la mayoría de los casos también podemos suponer que el índice primario se construye sobre una clave primaria o un conjunto de claves identificadas como primarias. Todos los demás índices se denominan secundarios.

Los índices secundarios pueden apuntar directamente al registro de datos, o simplemente almacenar su clave primaria. Un puntero a un registro de datos puede contener un desplazamiento a un archivo del montón o a una tabla organizada por índices. Múltiples índices secundarios pueden apuntar al mismo registro, permitiendo que un mismo registro de datos sea identificado por diferentes campos y localizado a través de diferentes índices. Mientras que los archivos de índices primarios contienen una única entrada por clave de búsqueda, los índices secundarios pueden contener varias entradas por clave de búsqueda [GARCIAMOLINA08].

Si el orden de los registros de datos sigue el orden de la clave de búsqueda, este índice se denomina agrupado (también conocido como clustering). Los registros de datos en el caso agrupado suelen almacenarse en el mismo archivo o en un archivo agrupado, donde se conserva el orden de las claves. Si los datos se almacenan en un archivo independiente, y su orden no sigue el orden de las claves, el índice se denomina no agrupado (a veces llamado no agrupado).

La Figura 1-5 muestra la diferencia entre ambos enfoques:

• a) Una tabla organizada por índices, en la que los registros de datos se almacenan directamente en el fichero índice.

• b) Un fichero índice que almacene los desplazamientos y otro fichero que almacene los registros de datos.

Figura 1-5. Almacenamiento de registros de datos en un archivo de índice frente al almacenamiento de desplazamientos al archivo de datos (segmentos de índice en blanco; segmentos con registros de datos en gris)

Nota

Las tablas organizadas por índices almacenan la información en orden de índice y están agrupadas por definición. Los índices primarios suelen estar agrupados. Los índices secundarios no están agrupados por definición, ya que se utilizan para facilitar el acceso por claves distintas de la primaria. Los índices agrupados pueden estar organizados por índices o tener archivos de índices y datos separados.

Muchos sistemas de bases de datos tienen una clave primaria inherente y explícita, un conjunto de columnas que identifican de forma única el registro de la base de datos. En los casos en que no se especifica la clave primaria, el motor de almacenamiento puede crear una clave primaria implícita (por ejemplo, MySQL InnoDB añade una nueva columna de autoincremento y rellena sus valores automáticamente).

Esta terminología se utiliza en distintos tipos de sistemas de bases de datos: sistemas de bases de datos relacionales (como MySQL y PostgreSQL), almacenes NoSQL basados en Dynamo (como Apache Cassandra y en Riak) y almacenes de documentos (como MongoDB). Puede haber alguna nomenclatura específica de cada proyecto, pero lo más habitual es que haya una clara correspondencia con esta terminología.

Índice Primario como Indirección

Hay diferentes opiniones en la comunidad de bases de datos sobre si los registros de datos de deben referenciarse directamente (mediante el desplazamiento de archivos) o a través del índice de clave primaria.⁴

Ambos enfoques tienen sus pros y sus contras, y es mejor discutirlos en el ámbito de una implementación completa. Al referenciar los datos directamente, podemos reducir el número de búsquedas en disco, pero tenemos que pagar un coste de actualización de los punteros cada vez que se actualiza o reubica el registro durante un proceso de mantenimiento. Utilizar la indirección en forma de índice primario nos permite reducir el coste de actualización de los punteros, pero tiene un coste mayor en una ruta de lectura.

Actualizar sólo un par de índices puede funcionar si la carga de trabajo consiste principalmente en lecturas, pero este planteamiento no funciona bien para cargas de trabajo con mucha escritura y múltiples índices. Para reducir los costes de las actualizaciones de punteros, en lugar de los desplazamientos de carga, algunas implementaciones utilizan claves primarias para la indirección. Por ejemplo, MySQL InnoDB utiliza un índice primario y realiza dos búsquedas: una en el índice secundario y otra en un índice primario al realizar una consulta [TARIQ11]. Esto añade una sobrecarga de una búsqueda en el índice primario en lugar de seguir el desplazamiento directamente desde el índice secundario.

La Figura 1-6 muestra las diferencias entre ambos enfoques:

• a) Dos índices hacen referencia a entradas de datos directamente desde ficheros de índice secundarios.

• b) Un índice secundario pasa por la capa de indirección de un índice primario para localizar las entradas de datos.

Figura 1-6. Referenciar tuplas de datos directamente (a) frente a utilizar un índice primario como indirección (b)

También es posible utilizar un enfoque híbrido y almacenar tanto los desplazamientos del fichero de datos como las claves primarias. En primer lugar, comprueba si el desplazamiento de datos sigue siendo válido y paga el coste adicional de recorrer el índice de clave primaria si ha cambiado, actualizando el fichero índice tras encontrar un nuevo desplazamiento.

Amortiguación, inmutabilidad y ordenación

Un motor de almacenamiento se basa en alguna estructura de datos. Sin embargo, estas estructuras no describen la semántica del almacenamiento en caché, la recuperación, la transaccionalidad y otras cosas que los motores de almacenamiento añaden sobre ellas.

En los próximos capítulos, comenzaremos el debate con los Árboles B (véase "Árboles B ubicuos") e intentaremos comprender por qué hay tantas variantes de Árboles B, y por qué siguen apareciendo nuevas estructuras de almacenamiento de bases de datos.

Las estructuras de almacenamiento tienen tres variables comunes: utilizan almacenamiento intermedio (o evitan utilizarlo), utilizan archivos inmutables (o mutables) y almacenan valores en orden (o fuera de orden). La mayoría de las distinciones y optimizaciones de las estructuras de almacenamiento que se tratan en este libro están relacionadas con uno de estos tres conceptos.

Amortiguación

Define si la estructura de almacenamiento opta o no por recoger una determinada cantidad de datos en memoria antes de ponerlos en el disco. Por supuesto, toda estructura en disco tiene que utilizar el almacenamiento en búfer hasta cierto punto, ya que la unidad más pequeña de transferencia de datos hacia y desde el disco es un bloque, y es deseable escribir bloques completos. Aquí hablamos de almacenamiento en búfer evitable, algo que los implementadores de motores de almacenamiento deciden hacer. Una de las primeras optimizaciones que tratamos en este libro es añadir búferes en memoria a los nodos del Árbol B para amortizar los costes de E/S (ver "Árboles B perezosos"). Sin embargo, ésta no es la única forma en que podemos aplicar el almacenamiento intermedio. Por ejemplo, los Árboles LSM de dos componentes(ver "Árbol LSM de dos componentes"), a pesar de sus similitudes con los Árboles B, utilizan el almacenamiento en memoria intermedia de una forma totalmente distinta, y combinan el almacenamiento en memoria intermedia con la inmutabilidad.

Mutabilidad (o inmutabilidad)

Este define si la estructura de almacenamiento lee o no partes del archivo, las actualiza y escribe los resultados actualizados en la misma ubicación del archivo. Las estructuras inmutables son de sólo añadir: una vez escrito, el contenido del archivo no se modifica. En su lugar, las modificaciones se añaden al final del archivo. Hay otras formas de implementar la inmutabilidad. Una de ellas es la copia en escritura (ver "Copia en escritura"), en la que la página modificada, que contiene la versión actualizada del registro, se escribe en la nueva ubicación del archivo, en lugar de en su ubicación original. A menudo, la distinción entre LSM y Árboles B se establece como inmutable frente al almacenamiento de actualizaciones in situ, pero existen estructuras (por ejemplo, los "Árboles Bw") que se inspiran en los Árboles B pero son inmutables.

Pedidos

Este se define como si los registros de datos se almacenan o no en el orden de las claves en las páginas del disco. En otras palabras, las claves que ordenan estrechamente se almacenan en segmentos contiguos en el disco. El orden suele definir si podemos o no escanear eficientemente el rango de registros, no sólo localizar los registros de datos individuales. Almacenar los datos fuera de orden (la mayoría de las veces, en orden de inserción) permite algunas optimizaciones del tiempo de escritura. Por ejemplo, Bitcask (ver "Bitcask") y WiscKey (ver "WiscKey") almacenan los registros de datos directamente en archivos de sólo inserción.

Por supuesto, una breve discusión de estos tres conceptos no basta para mostrar su poder, y continuaremos esta discusión a lo largo del resto del libro.

Resumen

En este capítulo hemos hablado de la arquitectura de un sistema de gestión de bases de datos y de sus componentes principales.

Para resaltar la importancia de las estructuras basadas en disco y su diferencia con las basadas en memoria, analizamos los almacenes basados en memoria y en disco. Llegamos a la conclusión de que las estructuras basadas en disco son importantes para ambos tipos de almacenes, pero se utilizan con fines distintos.

Para comprender cómo influyen los patrones de acceso en el diseño de los sistemas de bases de datos, hablamos de los sistemas de gestión de bases de datos orientados a columnas y a filas, y de los principales factores que los diferencian. Para iniciar una conversación sobre cómo se almacenan los datos, cubrimos los archivos de datos e índices.

Por último, hemos introducido tres conceptos básicos: almacenamiento en búfer, inmutabilidad y ordenación. Los utilizaremos a lo largo de este libro para destacar propiedades de los motores de almacenamiento que los utilizan.

Otras lecturas

Si quieres saber más sobre los conceptos mencionados en este capítulo, puedes consultar las siguientes fuentes:

Arquitectura de la base de datos

Hellerstein, Joseph M., Michael Stonebraker y James Hamilton. 2007. "Arquitectura de un sistema de bases de datos". Fundamentos y Tendencias en Bases de Datos 1, nº 2 (febrero): 141-259. https://doi.org/10.1561/1900000002.

SGBD orientado a columnas

Abadi, Daniel, Peter Boncz, Stavros Harizopoulos, Stratos Idreaos y Samuel Madden. 2013. Diseño e implementación de sistemas modernos de bases de datos orientados a columnas. Hanover, MA: Now Publishers Inc.

SGBD en memoria

Faerber, Frans, Alfons Kemper y Per-Åke Alfons. 2017. Sistemas de bases de datos de memoria principal. Hanover, MA: Now Publishers Inc.

¹ Puedes encontrar una visualización y comparación de las latencias de acceso a disco y memoria, y muchas otras cifras relevantes a lo largo de los años en https://people.eecs.berkeley.edu/~rcs/research/interactive_latency.html.

² La localidad espacial es uno de los Principios de la Localidad, que establece que si se accede a una posición de memoria, se accederá a las posiciones de memoria cercanas en un futuro próximo.

³ Las instrucciones vectorizadas, o SIMD (Single Instruction Multiple Data), describen una clase de instrucciones de la CPU que realizan la misma operación en varios puntos de datos.

⁴ El post original que ha suscitado el debate era polémico y unilateral, pero puedes consultar la presentación que compara los formatos de índice y almacenamiento de MySQL y PostgreSQL, que también hace referencia a la fuente original.