¿Cómo funcionan las bases de datos internamente? [cerrado]

He estado trabajando con bases de datos durante los últimos años y me gustaría pensar que me he vuelto bastante competente en su uso. Sin embargo, estaba leyendo recientemente sobre la Ley de abstracciones con fugas de Joel y me di cuenta de que, aunque puedo escribir una consulta para obtener prácticamente cualquier cosa que quiera de una base de datos, no tengo idea de cómo la base de datos realmente interpreta la consulta. ¿Alguien sabe de algún buen artículo o libro que explique cómo funcionan las bases de datos internamente?

Algunas cosas específicas que me interesan son:

• ¿Qué hace realmente una base de datos para averiguar qué coincide con una declaración de selección?
• ¿Cómo interpreta una base de datos una combinación de manera diferente a una consulta con varias declaraciones "where key1 = key2"?
• ¿Cómo almacena la base de datos toda su memoria?
• ¿Cómo se almacenan los índices?

¿Qué hace realmente una base de datos para averiguar qué coincide con una declaración de selección?

Para ser franco, es una cuestión de fuerza bruta. Simplemente, lee cada registro de candidato en la base de datos y hace coincidir la expresión con los campos. Por lo tanto, si tiene "seleccionar * de la tabla donde nombre = 'fred'", literalmente recorre cada registro, toma el campo "nombre" y lo compara con 'fred'.

Ahora, si el campo "table.name" está indexado, entonces la base de datos (probablemente, pero no necesariamente) usará el índice primero para ubicar los registros candidatos a los que aplicar el filtro real.

Esto reduce el número de registros candidatos a los que aplicar la expresión; de lo contrario, simplemente hará lo que llamamos un "escaneo de tabla", es decir, leerá cada fila.

Pero fundamentalmente, la ubicación de los registros candidatos es independiente de cómo aplica la expresión de filtro real y, obviamente, hay algunas optimizaciones inteligentes que se pueden hacer.

¿Cómo interpreta una base de datos una combinación de manera diferente a una consulta con varias declaraciones "where key1 = key2"?

Bueno, una combinación se usa para crear una nueva "pseudotabla", sobre la cual se aplica el filtro. Entonces, tiene los criterios de filtro y los criterios de unión. Los criterios de combinación se utilizan para construir esta "pseudotabla" y luego el filtro se aplica contra eso. Ahora, al interpretar la combinación, vuelve a ser el mismo problema que el filtro: comparaciones de fuerza bruta y lecturas de índice para construir el subconjunto de la "pseudotabla".

¿Cómo almacena la base de datos toda su memoria?

Una de las claves para una buena base de datos es cómo administra sus búferes de E / S. Pero básicamente hace coincidir bloques de RAM con bloques de disco. Con los administradores de memoria virtual modernos, una base de datos más simple casi puede depender de la VM como su administrador de búfer de memoria. Los DB de gama alta hacen todo esto ellos mismos.

¿Cómo se almacenan los índices?

Árboles B + normalmente, deberías buscarlo. Es una técnica sencilla que ha existido durante años. Su beneficio se comparte con la mayoría de los árboles equilibrados: acceso constante a los nodos, además de que todos los nodos hoja están vinculados para que pueda atravesar fácilmente de un nodo a otro en orden clave. Entonces, con un índice, las filas pueden considerarse "ordenadas" para campos específicos en la base de datos, y la base de datos puede aprovechar esa información para beneficiarse de las optimizaciones. Esto es distinto de, por ejemplo, usar una tabla hash para un índice, que solo le permite acceder rápidamente a un registro específico. En un B-Tree puede llegar rápidamente no solo a un registro específico, sino a un punto dentro de una lista ordenada.

La mecánica real de almacenar e indexar filas en la base de datos es bastante sencilla y se comprende bien. El juego es administrar búferes y convertir SQL en rutas de consulta eficientes para aprovechar estos modismos básicos de almacenamiento.

Luego, está toda la complejidad de los múltiples usuarios, el bloqueo, el registro y las transacciones además del lenguaje de almacenamiento.

• ¿Qué hace realmente una base de datos para averiguar qué coincide con una declaración de selección?

  Las bases de datos están usando índices (ver más abajo)

• ¿Cómo interpreta una base de datos una combinación de manera diferente a una consulta con varias declaraciones "where key1 = key2"? Las operaciones de unión se pueden convertir en operaciones de árbol binario fusionando árboles.

• ¿Cómo almacena la base de datos toda su memoria?

  archivos con mapas de memoria para un acceso más rápido a sus datos

• ¿Cómo se almacenan los índices?

  Internamente, las bases de datos están trabajando con B-Trees para la indexación.

Esto debería explicarse con mayor detalle en wikipedia.

http://en.wikipedia.org/wiki/B-tree

http://en.wikipedia.org/wiki/Database

Además de leer, puede resultar instructivo utilizar las herramientas de la base de datos para examinar el plan de ejecución que la base de datos utiliza en sus consultas. Además de obtener información sobre cómo está funcionando, puede experimentar con técnicas para optimizar las consultas con un mejor ciclo de retroalimentación.

Saif, excelente enlace. Una descripción general a vista de pájaro que logra cubrir la mayoría de los temas y proporciona detalles sobre implementaciones de proveedores específicos.

Hice tres intentos de escribir una explicación, pero este es un tema demasiado grande. Consulte el artículo de Hellerstein (el que está en el servidor de Berkeley al que se vinculó Saif) y luego pregunte sobre los detalles.

Vale la pena señalar que solo un subconjunto de "buenas ideas conocidas" se implementa en cualquier DBMS. Por ejemplo, SQLite ni siquiera realiza combinaciones hash, solo hace bucles anidados (¡ack!). Pero luego, es un dbms fácilmente integrable, y hace su trabajo muy bien, así que hay algo que decir sobre la falta de complejidad.

Aprender cómo un DBMS recopila estadísticas y cómo las usa para construir planes de consulta, así como aprender a leer los planes de consulta en primer lugar, es una habilidad invaluable, si tiene que elegir un tema "interno de la base de datos" para aprende, aprende esto. Hará un mundo de diferencia (y nunca volverá a escribir accidentalmente un producto cartesiano ... ;-)).

Si desea saber más en detalle, le recomiendo obtener las fuentes sqlite y echar un vistazo a cómo lo hace. Es completo, aunque no a la escala de las bases de datos comerciales y de código abierto más grandes. Si quieres saber más en detalle, te recomiendo The Definitive Guide to SQLite, que no solo es una gran explicación de sqlite, sino también uno de los libros técnicos más legibles que conozco. En el lado de MySQL, puede aprender del Blog de rendimiento de MySQL , así como en el frente del libro, el MySQL de alto rendimiento de O'Reilly (V2), del cual el blog es uno de los autores.