Cómo escribir un motor de base de datos simple [cerrado]

143

Estoy interesado en aprender cómo funciona un motor de base de datos (es decir, sus partes internas). Conozco la mayoría de las estructuras básicas de datos que se enseñan en CS (árboles, tablas hash, listas, etc.), así como una buena comprensión de la teoría del compilador (y he implementado un intérprete muy simple), pero no entiendo cómo hacerlo. sobre escribir un motor de base de datos. He buscado tutoriales sobre el tema y no pude encontrar ninguno, así que espero que alguien más pueda señalarme en la dirección correcta. Básicamente, me gustaría obtener información sobre lo siguiente:

  • Cómo se almacenan los datos internamente (es decir, cómo se representan las tablas, etc.)
  • Cómo el motor encuentra los datos que necesita (por ejemplo, ejecutar una consulta SELECT)
  • Cómo se insertan los datos de manera rápida y eficiente

Y cualquier otro tema que pueda ser relevante para esto. No tiene que ser una base de datos en disco, incluso una base de datos en memoria está bien (si es más fácil) porque solo quiero aprender los principios detrás de ella.

Muchas gracias por su ayuda.

a_m0d
fuente

Respuestas:

55

Si eres bueno leyendo el código, estudiar SQLite te enseñará una gran cantidad de cosas sobre el diseño de bases de datos. Es pequeño, por lo que es más fácil entenderlo. Pero también está escrito profesionalmente.

http://sqlite.org/

Robert Harvey
fuente
2
LOC de la descarga de sqlite shell.c => 3135, sqlite3.c => 136332, sqlite3ext.h => 447, sqlite3.h => 7097, total => 147011
Khaja Minhajuddin
1
Probablemente sea lo más pequeño que pueda hacer un motor de base de datos completamente funcional utilizando un lenguaje de llaves. SQLite también está disponible en C #.
Robert Harvey
1
@Ibrahim Najjar github.com/CsharpDatabase/csharp-sqlite
Robert Harvey
44
Recomiendo leer el código de SQLite 2.5.0: github.com/davideuler/SQLite-2.5.0-for-code-reading , es una versión temprana de SQLite que se puede compilar y ejecutar en GCC moderno (he probado en MacOS 10.13 y Debian 8)
david euler
1
cstack.github.io/db_tutorial es un buen punto de partida.
Ashish Negi
25

La respuesta a esta pregunta es enorme. Esperamos que una tesis de doctorado tenga una respuesta del 100%;) pero podemos pensar en los problemas uno por uno:

  • Cómo almacenar los datos internamente: debe tener un archivo de datos que contenga los objetos de su base de datos y un mecanismo de almacenamiento en caché para cargar los datos en foco y algunos datos a su alrededor en RAM suponen que tiene una tabla, con algunos datos, crearíamos un formato de datos para convertir esta tabla en un archivo binario, acordando la definición de un delimitador de columna y un delimitador de fila y asegurándose de que dicho patrón de delimitador nunca se use en sus propios datos. es decir, si ha seleccionado <*>, por ejemplo, para separar columnas, debe validar los datos que está colocando en esta tabla para que no contengan este patrón. también puede usar un encabezado de fila y un encabezado de columna especificando el tamaño de la fila y algún número de indexación interno para acelerar su búsqueda, y al comienzo de cada columna para tener la longitud de esta columna como "Adam", 1, 11.1, "

  • Cómo encontrar elementos rápidamente, intente usar hashing e indexación para apuntar a datos almacenados y almacenados en caché según diferentes criterios tomando el mismo ejemplo anterior, puede ordenar el valor de la primera columna y almacenarlo en un objeto separado que apunte a la identificación de la fila de elementos ordenados alfabéticamente , y así

  • Cómo acelerar la inserción de datos que sé de Oracle es que insertan datos en un lugar temporal tanto en la RAM como en el disco y realizan tareas de limpieza periódicamente, el motor de la base de datos está ocupado todo el tiempo optimizando su estructura, pero al mismo tiempo no lo hacemos querer perder datos en caso de falla de energía de algo así. así que trate de mantener los datos en este lugar temporal sin ordenarlos, agregue su almacenamiento original y más tarde cuando el sistema esté libre, recurra a sus índices y borre el área temporal cuando haya terminado

Buena suerte, gran proyecto.

A.Rashad
fuente
11

SQLite se mencionó antes, pero quiero agregar algo.

Personalmente aprendí mucho al estudiar SQlite. Lo interesante es que no fui al código fuente (aunque solo tuve un breve vistazo). Aprendí mucho leyendo el material técnico y observando especialmente los comandos internos que genera. Tiene un intérprete basado en una pila propia y puede leer el código P que genera internamente con solo explicar. Por lo tanto, puede ver cómo se traducen varias construcciones al motor de bajo nivel (eso es sorprendentemente simple, pero ese es también el secreto de su estabilidad y eficiencia).

Juergen
fuente
9

Bien, he encontrado un sitio que tiene información sobre SQL e implementación; es un poco difícil vincular a la página que enumera todos los tutoriales, por lo que los vincularé uno por uno:

a_m0d
fuente
8

Sugeriría centrarse en www.sqlite.org

Es reciente, pequeño (código fuente 1 MB), de código abierto (para que pueda resolverlo usted mismo) ...

Se han escrito libros sobre cómo se implementa:

http://www.sqlite.org/books.html

Se ejecuta en una variedad de sistemas operativos tanto para computadoras de escritorio como para teléfonos móviles, por lo que experimentar es fácil y aprender sobre esto será útil ahora y en el futuro.

Incluso tiene una comunidad decente aquí: /programming/tagged/sqlite

michael aubert
fuente
1
El tamaño del byte para 3.10 ahora es casi 7.0 mb de código fuente. Solo unos pocos privilegiados podían digerir todo eso de una sola vez. Sin embargo, este también es un buen lugar para comenzar.
Laurie Stearn
1
En efecto. Habiendo pasado algún tiempo dentro del código fuente de SQLite para encontrar un error en SQLCipher, es una pesadilla absoluta. La vida era más simple hace 6 años :-)
michael aubert
Solo una pregunta rápida ya que me perdí la fiesta, supongo que sería mucho más relajante (y tal vez útil) comenzar desde la primera versión. En realidad, ¿debería hacerlo para toda lectura seria de código de grandes proyectos?
Nicholas Humphrey
7

puede ser que puedas aprender de HSQLDB . Creo que ofrecen una base de datos pequeña y sencilla para aprender. puedes mirar los códigos ya que es de código abierto.

ruiseñor2k1
fuente
3

No estoy seguro de si se ajustaría a sus requisitos, pero había implementado una base de datos simple orientada a archivos con soporte para simple ( SELECT, INSERT , UPDATE) usando perl.
Lo que hice fue almacenar cada tabla como un archivo en el disco y las entradas con un patrón bien definido y manipulé los datos utilizando herramientas Linux integradas como awk y sed. Para mejorar la eficiencia, los datos de acceso frecuente se almacenaron en caché.

sud03r
fuente
1
¿Todavía tiene el código? ¿Puede compartir un enlace
GK1
3

Si MySQL le interesa, también sugeriría esta página wiki , que tiene información sobre cómo funciona MySQL. Además, es posible que desee echar un vistazo a Comprender los componentes internos de MySQL .

También puede considerar buscar una interfaz que no sea SQL para su motor de base de datos. Por favor, eche un vistazo a Apache CouchDB . Es lo que llamarías, un sistema de base de datos orientado a documentos.

¡Buena suerte!


fuente
Y si quiere ver otra base de datos: sqlserverinternals.com, sus nbooks en el servidor interno SQl son de primera categoría.
HLGEM