¡Hola, Habr! Presento a su atención la traducción del artículo.
"¿Cómo funciona una base de datos relacional?".

Cuando se trata de bases de datos relacionales no puedo evitar pensar que falta algo. Se utilizan en todas partes. Hay muchas bases de datos diferentes disponibles, desde la pequeña y útil SQLite hasta la poderosa Teradata. Pero sólo hay unos pocos artículos que explican cómo funciona la base de datos. Puede buscar usted mismo utilizando "howdoesarelationaldatabasework" para ver los pocos resultados que hay. Además, estos artículos son breves. Si está buscando las últimas tecnologías de moda (BigData, NoSQL o JavaScript), encontrará artículos más detallados que explican cómo funcionan.

¿Son las bases de datos relacionales demasiado antiguas y aburridas para explicarlas fuera de cursos universitarios, trabajos de investigación y libros?

Como desarrollador, odio usar algo que no entiendo. Y si las bases de datos se han utilizado durante más de 40 años, debe haber una razón. A lo largo de los años, he dedicado cientos de horas a comprender verdaderamente estas extrañas cajas negras que uso todos los días. Bases de datos relacionales muy interesante porque ellos basado en conceptos útiles y reutilizables. Si está interesado en comprender una base de datos, pero nunca ha tenido el tiempo o las ganas de profundizar en este amplio tema, debería disfrutar de este artículo.

Aunque el título de este artículo es explícito, El propósito de este artículo no es entender cómo utilizar la base de datos.. Por lo tanto, ya deberías saber cómo escribir una solicitud de conexión simple y consultas básicas CRUD; De lo contrario, es posible que no comprenda este artículo. Eso es lo único que necesitas saber, te explicaré el resto.

Comenzaré con algunos conceptos básicos de informática, como la complejidad temporal de los algoritmos (BigO). Sé que algunos de ustedes odian este concepto, pero sin él no podrán comprender las complejidades dentro de la base de datos. Dado que este es un tema enorme, me centraré en lo que creo que es importante: cómo procesa la base de datos SQL investigación. solo te presentaré conceptos básicos de bases de datospara que al final del artículo tengas una idea de lo que sucede bajo el capó.

Dado que este es un artículo largo y técnico que involucra muchos algoritmos y estructuras de datos, tómate tu tiempo para leerlo. Algunos conceptos pueden resultar difíciles de entender; puedes omitirlos y aun así tener una idea general.

Para los más entendidos, este artículo se divide en 3 partes:

Descripción general de los componentes de la base de datos de bajo y alto nivel
Descripción general del proceso de optimización de consultas
Descripción general de la gestión de transacciones y grupos de búfer

Volver a lo básico

Hace años (en una galaxia muy, muy lejana...), los desarrolladores tenían que saber exactamente el número de operaciones que estaban codificando. Conocían sus algoritmos y estructuras de datos de memoria porque no podían permitirse el lujo de desperdiciar la CPU y la memoria de sus computadoras lentas.

En esta parte, le recordaré algunos de estos conceptos, ya que son esenciales para comprender la base de datos. También presentaré el concepto. índice de base de datos.

O(1) frente a O(n2)

Hoy en día, a muchos desarrolladores no les importa la complejidad temporal de los algoritmos... ¡y tienen razón!

Pero cuando se trata de una gran cantidad de datos (no hablo de miles) o si se trabaja en milisegundos, resulta fundamental comprender este concepto. Y como puedes imaginar, ¡las bases de datos tienen que lidiar con ambas situaciones! No le haré dedicar más tiempo del necesario para transmitir el mensaje. Esto nos ayudará a comprender el concepto de optimización basada en costos más adelante (el costo basado optimización).

Concepto

Complejidad temporal del algoritmo. Se utiliza para ver cuánto tiempo llevará ejecutar un algoritmo para una cantidad determinada de datos.. Para describir esta complejidad, utilizamos la notación matemática O grande. Esta notación se utiliza con una función que describe cuántas operaciones necesita un algoritmo para un número determinado de entradas.

Por ejemplo, cuando digo "este algoritmo tiene complejidad O (alguna_función ())", significa que el algoritmo requiere operaciones de alguna_función (una_cierta_cantidad_de_datos) para procesar una cierta cantidad de datos.

En este caso, No es la cantidad de datos lo que importa**, de lo contrario ** cómo aumenta el número de operaciones al aumentar el volumen de datos. La complejidad del tiempo no proporciona un número exacto de operaciones, pero es una buena forma de estimar el tiempo de ejecución.

En este gráfico puede ver la cantidad de operaciones versus la cantidad de datos de entrada para diferentes tipos de complejidades de tiempo de algoritmo. Usé una escala logarítmica para mostrarlos. En otras palabras, la cantidad de datos aumenta rápidamente de mil millones a mil millones. Podemos ver que:

O(1) o complejidad constante permanece constante (de lo contrario no se llamaría complejidad constante).
O(log(n)) sigue siendo bajo incluso con miles de millones de datos.
Peor dificultad - O(n2), donde el número de operaciones crece rápidamente.
Las otras dos complicaciones aumentan con la misma rapidez.

Примеры

Con una pequeña cantidad de datos, la diferencia entre O(1) y O(n2) es insignificante. Por ejemplo, digamos que tiene un algoritmo que necesita procesar 2000 elementos.

El algoritmo O(1) le costará 1 operación
El algoritmo O(log(n)) le costará 7 operaciones
El algoritmo O(n) te costará 2 operaciones
El algoritmo O(n*log(n)) le costará 14 operaciones
El algoritmo O(n2) te costará 4 de operaciones

La diferencia entre O(1) y O(n2) parece grande (4 millones de operaciones), pero perderá un máximo de 2 ms, solo tiempo para parpadear. De hecho, los procesadores modernos pueden procesar cientos de millones de operaciones por segundo. Es por eso que el rendimiento y la optimización no son un problema en muchos proyectos de TI.

Como dije, sigue siendo importante conocer este concepto cuando se trabaja con grandes cantidades de datos. Si esta vez el algoritmo tiene que procesar 1 de elementos (que no es tanto para una base de datos):

El algoritmo O(1) le costará 1 operación
El algoritmo O(log(n)) le costará 14 operaciones
El algoritmo O(n) te costará 1 de operaciones
El algoritmo O(n*log(n)) le costará 14 de operaciones
El algoritmo O(n2) te costará 1 de operaciones

No he hecho los cálculos, pero diría que con el algoritmo O(n2) tienes tiempo para tomar un café (¡incluso dos!). Si agregas otro 0 al volumen de datos, tendrás tiempo para tomar una siesta.

vayamos más profundo

Para su información:

Una buena búsqueda en la tabla hash encuentra un elemento en O(1).
La búsqueda de un árbol bien equilibrado produce resultados en O(log(n)).
La búsqueda en una matriz produce resultados en O(n).
Los mejores algoritmos de clasificación tienen una complejidad O (n*log(n)).
Un algoritmo de clasificación incorrecto tiene una complejidad O (n2).

Nota: En las siguientes partes veremos estos algoritmos y estructuras de datos.

Existen varios tipos de complejidad temporal de algoritmos:

escenario de caso promedio
en el mejor de los casos
y el peor de los casos

La complejidad del tiempo es a menudo el peor de los casos.

Solo estaba hablando de la complejidad temporal del algoritmo, pero la complejidad también se aplica a:

consumo de memoria del algoritmo
algoritmo de consumo de E/S de disco

Por supuesto, existen complicaciones peores que n2, por ejemplo:

n4: ¡esto es terrible! Algunos de los algoritmos mencionados tienen esta complejidad.
3n: ¡esto es aún peor! Uno de los algoritmos que veremos a mitad de este artículo tiene esta complejidad (y de hecho se usa en muchas bases de datos).
factorial n: nunca obtendrás tus resultados incluso con una pequeña cantidad de datos.
nn: Si te encuentras con esta complejidad, deberías preguntarte si este es realmente tu campo de actividad...

Nota: No les di la definición real de la designación O grande, solo una idea. Puedes leer este artículo en Р'РёРєРёРμРμРμРёРёРёРёРё para la definición real (asintótica).

FusionarOrdenar

¿Qué haces cuando necesitas ordenar una colección? ¿Qué? Llamas a la función sort()... Ok, buena respuesta... Pero para una base de datos, debes entender cómo funciona esta función sort().

Hay varios buenos algoritmos de clasificación, así que me centraré en los más importantes: fusionar ordenar. Es posible que no comprenda por qué es útil ordenar datos en este momento, pero debería comprenderlo después de la parte de optimización de consultas. Además, comprender la clasificación de fusión nos ayudará a comprender más adelante la operación común de unión de bases de datos llamada unir únete (asociación de fusión).

Unir

Como muchos algoritmos útiles, la ordenación por fusión se basa en un truco: combinar 2 matrices ordenadas de tamaño N/2 en una matriz ordenada de N elementos cuesta solo N operaciones. Esta operación se llama fusión.

Veamos qué significa esto con un ejemplo sencillo:

Esta figura muestra que para construir la matriz final de 8 elementos ordenada, solo necesita iterar una vez sobre las 2 matrices de 4 elementos. Dado que ambas matrices de 4 elementos ya están ordenadas:

1) comparas ambos elementos actuales en dos matrices (al principio actual = primero)
2) luego toma el más pequeño para ponerlo en una matriz de 8 elementos
3) y pasar al siguiente elemento de la matriz donde tomaste el elemento más pequeño
y repite 1,2,3 hasta llegar al último elemento de uno de los arrays.
Luego tomas los elementos restantes de la otra matriz para colocarlos en una matriz de 8 elementos.

Esto funciona porque ambas matrices de 4 elementos están ordenadas y, por lo tanto, no es necesario "regresar" a esas matrices.

Ahora que entendemos el truco, aquí está mi pseudocódigo para fusionar:

array mergeSort(array a)
   if(length(a)==1)
      return a[0];
   end if

   //recursive calls
   [left_array right_array] := split_into_2_equally_sized_arrays(a);
   array new_left_array := mergeSort(left_array);
   array new_right_array := mergeSort(right_array);

   //merging the 2 small ordered arrays into a big one
   array result := merge(new_left_array,new_right_array);
   return result;

La clasificación por combinación divide un problema en problemas más pequeños y luego encuentra los resultados de los problemas más pequeños para obtener el resultado del problema original (nota: este tipo de algoritmo se llama divide y vencerás). Si no comprende este algoritmo, no se preocupe; No lo entendí la primera vez que lo vi. Si puede ayudarte, veo este algoritmo como un algoritmo de dos fases:

Fase de división, donde la matriz se divide en matrices más pequeñas
La fase de clasificación es donde se combinan pequeños arreglos (usando unión) para formar un arreglo más grande.

Fase de división

En la etapa de división, la matriz se divide en matrices unitarias en 3 pasos. El número formal de pasos es log(N) (ya que N=8, log(N) = 3).

¿Cómo puedo saber esto?

¡Soy un genio! En una palabra: matemáticas. La idea es que cada paso divida el tamaño de la matriz original por 2. El número de pasos es la cantidad de veces que puedes dividir la matriz original en dos. Esta es la definición exacta de un logaritmo (base 2).

Fase de clasificación

En la fase de clasificación, se comienza con matrices unitarias (de un solo elemento). Durante cada paso, aplica múltiples operaciones de combinación y el costo total es N = 8 operaciones:

En la primera etapa tienes 4 fusiones que cuestan 2 operaciones cada una.
En el segundo paso tienes 2 fusiones que cuestan 4 operaciones cada una.
En el tercer paso tienes 1 fusión que cuesta 8 operaciones.

Como hay pasos log(N), costo total norte * operaciones de registro (N).

Ventajas de la clasificación por fusión

¿Por qué este algoritmo es tan poderoso?

Porque:

Puede cambiarlo para reducir el uso de memoria de modo que no cree nuevas matrices sino que modifique directamente la matriz de entrada.

Nota: este tipo de algoritmo se llama in-place (clasificación sin memoria adicional).

Puede cambiarlo para utilizar espacio en disco y una pequeña cantidad de memoria al mismo tiempo sin incurrir en una sobrecarga significativa de E/S de disco. La idea es cargar en la memoria sólo aquellas partes que se están procesando actualmente. Esto es importante cuando necesita ordenar una tabla de varios gigabytes con sólo un búfer de memoria de 100 megabytes.

Nota: este tipo de algoritmo se llama clasificación externa.

Puede cambiarlo para que se ejecute en múltiples procesos/hilos/servidores.

Por ejemplo, la clasificación por fusión distribuida es uno de los componentes clave Hadoop (que es una estructura en big data).

Este algoritmo puede convertir el plomo en oro (¡de verdad!).

Este algoritmo de clasificación se utiliza en la mayoría (si no en todas) las bases de datos, pero no es el único. Si quieres saber más, puedes leer esto. trabajo de investigación, que analiza los pros y los contras de los algoritmos comunes de clasificación de bases de datos.

Matriz, árbol y tabla hash

Ahora que entendemos la idea de complejidad y clasificación del tiempo, debo hablarles sobre 3 estructuras de datos. Esto es importante porque ellos son la base de las bases de datos modernas. También presentaré el concepto. índice de base de datos.

Matriz

Una matriz bidimensional es la estructura de datos más simple. Se puede considerar una tabla como una matriz. Por ejemplo:

Esta matriz bidimensional es una tabla con filas y columnas:

Cada línea representa una entidad.
Las columnas almacenan propiedades que describen la entidad.
Cada columna almacena datos de un tipo específico (entero, cadena, fecha...).

Esto es conveniente para almacenar y visualizar datos; sin embargo, cuando necesita encontrar un valor específico, esto no es adecuado.

Por ejemplo, si quisieras encontrar todos los tipos que trabajan en el Reino Unido, tendrías que mirar cada fila para determinar si esa fila pertenece al Reino Unido. Te costará N transaccionesDonde N - número de líneas, lo cual no está mal, pero ¿podría haber una manera más rápida? Ahora es el momento de que nos familiaricemos con los árboles.

Nota: La mayoría de las bases de datos modernas proporcionan matrices extendidas para almacenar tablas de manera eficiente: tablas organizadas en montón y tablas organizadas por índice. Pero esto no cambia el problema de encontrar rápidamente una condición específica en un grupo de columnas.

Árbol e índice de base de datos

Un árbol de búsqueda binario es un árbol binario con una propiedad especial, la clave en cada nodo debe ser:

mayor que todas las claves almacenadas en el subárbol izquierdo
menos que todas las claves almacenadas en el subárbol derecho

Veamos qué significa esto visualmente.

Idea

Este árbol tiene N = 15 elementos. Digamos que estoy buscando 208:

Empiezo en la raíz cuya clave es 136. Como 136 <208, miro el subárbol derecho del nodo 136.
398>208 por lo tanto estoy mirando el subárbol izquierdo del nodo 398
250>208 por lo tanto estoy mirando el subárbol izquierdo del nodo 250
200<208, por lo tanto estoy mirando el subárbol derecho del nodo 200. Pero 200 no tiene un subárbol derecho, el valor no existe (porque si existe, estará en el subárbol derecho 200).

Ahora digamos que estoy buscando 40

Empiezo en la raíz cuya clave es 136. Como 136 > 40, miro el subárbol izquierdo del nodo 136.
80 > 40, por eso estoy mirando el subárbol izquierdo del nodo 80
40= 40, el nodo existe. Recupero el ID de fila dentro del nodo (que no se muestra en la imagen) y busco en la tabla el ID de fila dado.
Conocer el ID de la fila me permite saber exactamente dónde están los datos en la tabla, para poder recuperarlos al instante.

Al final, ambas búsquedas me costarán la cantidad de niveles dentro del árbol. Si lee atentamente la parte sobre la ordenación por combinación, debería ver que hay niveles de registro (N). Resulta, registro de costos de búsqueda(N), ¡nada mal!

Volvamos a nuestro problema.

Pero esto es muy abstracto, así que volvamos a nuestro problema. En lugar de un número entero simple, imagine una cadena que represente el país de alguien en la tabla anterior. Digamos que tienes un árbol que contiene el campo "país" (columna 3) de la tabla:

Si quieres saber quién trabaja en el Reino Unido.
miras el árbol para obtener el nodo que representa a Gran Bretaña
Dentro de "UKnode" encontrará la ubicación de los registros de trabajadores del Reino Unido.

Esta búsqueda costará operaciones log(N) en lugar de N operaciones si usa la matriz directamente. Lo que acabas de presentar fue índice de base de datos.

Puede crear un árbol de índice para cualquier grupo de campos (cadena, número, 2 líneas, número y cadena, fecha...) siempre que tenga una función para comparar claves (es decir, grupos de campos) para poder configurar orden entre las llaves (que es el caso de cualquier tipo básico en la base de datos).

B+Índice de árbol

Si bien este árbol funciona bien para obtener un valor específico, existe un GRAN problema cuando necesitas obtener múltiples elementos entre dos valores. Esto costará O(N) porque tendrá que mirar cada nodo en el árbol y verificar si está entre estos dos valores (por ejemplo, con un recorrido ordenado del árbol). Además, esta operación no es compatible con la E/S de disco, ya que es necesario leer el árbol completo. Necesitamos encontrar una manera de ejecutar eficientemente solicitud de rango. Para resolver este problema, las bases de datos modernas utilizan una versión modificada del árbol anterior llamado B+Tree. En un árbol B+Tree:

solo los nodos más bajos (hojas) almacenar información (ubicación de filas en la tabla relacionada)
el resto de los nodos están aquí para enrutamiento al nodo correcto durante la búsqueda.

Como puede ver, aquí hay más nodos (dos veces). De hecho, tiene nodos adicionales, "nodos de decisión", que le ayudarán a encontrar el nodo correcto (que almacena la ubicación de las filas en la tabla asociada). Pero la complejidad de la búsqueda sigue siendo O (log (N)) (solo hay un nivel más). La gran diferencia es que Los nodos en el nivel inferior están conectados a sus sucesores..

Con este B+Tree, si buscas valores entre 40 y 100:

Sólo necesitas buscar 40 (o el valor más cercano después de 40 si 40 no existe) como lo hiciste con el árbol anterior.
Luego, recopile 40 herederos utilizando enlaces de herederos directos hasta llegar a 100.

Digamos que encuentra M sucesores y el árbol tiene N nodos. Encontrar un nodo específico cuesta log(N) como el árbol anterior. Pero una vez que obtenga este nodo, obtendrá M sucesores en M operaciones con referencias a sus sucesores. Esta búsqueda solo cuesta M+log(N) operaciones en comparación con N operaciones en el árbol anterior. Además, no es necesario leer el árbol completo (solo nodos M+log(N)), lo que significa menos uso del disco. Si M es pequeño (por ejemplo, 200 filas) y N es grande (1 de filas), habrá una GRAN diferencia.

Pero aquí hay nuevos problemas (¡otra vez!). Si agrega o elimina una fila en la base de datos (y por lo tanto en el índice B+Tree asociado):

debe mantener el orden entre los nodos dentro de un árbol B+; de lo contrario, no podrá encontrar los nodos dentro de un árbol sin clasificar.
debe mantener el número mínimo posible de niveles en B+Tree; de lo contrario, la complejidad temporal O(log(N)) se convierte en O(N).

En otras palabras, B+Tree debe ser autoordenado y equilibrado. Afortunadamente, esto es posible con operaciones inteligentes de eliminación e inserción. Pero esto tiene un costo: las inserciones y eliminaciones en un árbol B+ cuestan O(log(N)). Por eso algunos de ustedes han escuchado eso. usar demasiados índices no es una buena idea. En realidad, está ralentizando la inserción/actualización/eliminación rápida de una fila en una tablaporque la base de datos necesita actualizar los índices de la tabla utilizando una costosa operación O(log(N)) para cada índice. Además, agregar índices significa más carga de trabajo para administrador de transacciones (se describirá al final del artículo).

Para obtener más detalles, puede consultar el artículo de Wikipedia sobre B+Árbol. Si desea un ejemplo de implementación de B+Tree en una base de datos, eche un vistazo este articulo и este articulo de un desarrollador líder de MySQL. Ambos se centran en cómo InnoDB (el motor MySQL) maneja los índices.

Nota: Un lector me dijo que, debido a optimizaciones de bajo nivel, el árbol B+ debería estar completamente equilibrado.

Tabla de picadillo

Nuestra última estructura de datos importante es la tabla hash. Esto es muy útil cuando desea buscar valores rápidamente. Además, comprender una tabla hash nos ayudará a comprender más adelante una operación común de unión de bases de datos llamada unión hash ( unión hash). La base de datos también utiliza esta estructura de datos para almacenar algunas cosas internas (p. ej. mesa de bloqueo o grupo de buffer, veremos ambos conceptos más adelante).

Una tabla hash es una estructura de datos que encuentra rápidamente un elemento por su clave. Para construir una tabla hash necesitas definir:

ключ para tus elementos
función hash para llaves. Los hash de clave calculados dan la ubicación de los elementos (llamados segmentos ).
función para comparar claves. Una vez que hayas encontrado el segmento correcto, deberás encontrar el elemento que buscas dentro del segmento utilizando esta comparación.

Ejemplo simple

Pongamos un ejemplo claro:

Esta tabla hash tiene 10 segmentos. Como soy vago, sólo me imaginé 5 segmentos, pero sé que eres inteligente, así que te dejaré imaginar los otros 5 por tu cuenta. Utilicé una función hash módulo 10 de la clave. En otras palabras, almaceno sólo el último dígito de la clave del elemento para encontrar su segmento:

si el último dígito es 0, el elemento cae en el segmento 0,
si el último dígito es 1, el elemento cae en el segmento 1,
si el último dígito es 2, el elemento cae en el área 2,
...

La función de comparación que utilicé es simplemente igualdad entre dos números enteros.

Digamos que quieres obtener el elemento 78:

La tabla hash calcula el código hash para 78, que es 8.
La tabla hash mira el segmento 8 y el primer elemento que encuentra es 78.
Ella te devuelve el artículo 78.
La búsqueda cuesta sólo 2 operaciones (uno para calcular el valor hash y el otro para buscar el elemento dentro del segmento).

Ahora digamos que quieres obtener el elemento 59:

La tabla hash calcula el código hash para 59, que es 9.
La tabla hash busca en el segmento 9, el primer elemento encontrado es 99. Como 99!=59, el elemento 99 no es un elemento válido.
Usando la misma lógica se toma el segundo elemento (9), el tercero (79),..., el último (29).
Elemento no encontrado.
La búsqueda costó 7 operaciones..

Buena función hash

Como ves, dependiendo del valor que busques, ¡el coste no es el mismo!

Si ahora cambio la función hash módulo 1 de la clave (es decir, tomando los últimos 000 dígitos), la segunda búsqueda solo cuesta 000 operación ya que no hay elementos en el segmento 6. El verdadero desafío es encontrar una buena función hash que cree depósitos que contengan una cantidad muy pequeña de elementos..

En mi ejemplo, encontrar una buena función hash es fácil. Pero este es un ejemplo simple, encontrar una buena función hash es más difícil cuando la clave es:

cadena (por ejemplo, apellido)
2 líneas (por ejemplo, apellido y nombre)
2 líneas y fecha (por ejemplo, apellido, nombre y fecha de nacimiento)
...

Con una buena función hash, las búsquedas en la tabla hash cuestan O(1).

Matriz vs tabla hash

¿Por qué no utilizar una matriz?

Mmm, buena pregunta.

La tabla hash puede ser parcialmente cargado en la memoriay los segmentos restantes pueden permanecer en el disco.
Con una matriz debes usar espacio contiguo en la memoria. Si estás cargando una mesa grande es muy difícil encontrar suficiente espacio continuo.
Para una tabla hash, puede seleccionar la clave que desee (por ejemplo, país y apellido de la persona).

Para más información puedes leer el artículo sobre Javamapa hash, que es una implementación eficiente de una tabla hash; No es necesario comprender Java para comprender los conceptos tratados en este artículo.

Fuente: habr.com

Cómo funcionan las bases de datos relacionales (Parte 1)