Jak napisać prosty silnik bazy danych [zamknięte]


143

Jestem zainteresowany dowiedzeniem się, jak działa silnik bazy danych (tj. Jego wnętrze). Znam większość podstawowych struktur danych nauczanych w CS (drzewa, tablice skrótów, listy itp.), A także całkiem dobre zrozumienie teorii kompilatora (i zaimplementowałem bardzo prosty interpreter), ale nie rozumiem, jak to zrobić o pisaniu silnika bazy danych. Szukałem poradników na ten temat i nie znalazłem żadnych, więc mam nadzieję, że ktoś inny wskaże mi właściwy kierunek. Zasadniczo chciałbym uzyskać informacje na następujące tematy:

  • W jaki sposób dane są przechowywane wewnętrznie (tj. W jaki sposób są reprezentowane tabele itp.)
  • W jaki sposób silnik znajduje potrzebne dane (np. Uruchamia zapytanie SELECT)
  • Jak dane są wstawiane w sposób szybki i skuteczny

Oraz wszelkie inne tematy, które mogą mieć znaczenie. Nie musi to być baza danych na dysku - nawet baza danych w pamięci jest w porządku (jeśli jest łatwiejsza), ponieważ chcę po prostu poznać zasady, które za nią stoją.

Wielkie dzięki za Twoją pomoc.

Odpowiedzi:


55

Jeśli jesteś dobry w czytaniu kodu, nauka SQLite nauczy Cię całej masy wiedzy na temat projektowania baz danych. Jest mały, więc łatwiej jest owinąć głowę. Ale jest też napisany profesjonalnie.

http://sqlite.org/


2
LOC powłoki pobierania sqlite.c => 3135, sqlite3.c => 136332, sqlite3ext.h => 447, sqlite3.h => 7097, total => 147011
Khaja Minhajuddin

1
Który jest prawdopodobnie tak mały, jak można stworzyć w pełni funkcjonalny silnik bazy danych przy użyciu języka nawiasów klamrowych. SQLite jest również dostępny w C #.
Robert Harvey


4
Polecam przeczytać kod SQLite 2.5.0: github.com/davideuler/SQLite-2.5.0-for-code-reading , jest to wczesna wersja SQLite, którą można skompilować i uruchomić na nowoczesnym GCC (przetestowałem it na MacOS 10.13 i Debian 8)
david euler

1
cstack.github.io/db_tutorial jest dobrym punktem wyjścia.
Ashish Negi

25

Odpowiedź na to pytanie jest ogromna. spodziewamy się, że praca doktorska da 100% odpowiedzi;), ale o problemach możemy myśleć jeden po drugim:

  • Jak przechowywać dane wewnętrznie: powinieneś mieć plik danych zawierający obiekty bazy danych i mechanizm buforowania, aby załadować dane w fokusie i niektóre dane wokół niego do pamięci RAM, zakładając, że masz tabelę, z pewnymi danymi, stworzymy format danych aby przekonwertować tę tabelę na plik binarny, zgadzając się na definicję separatora kolumny i separatora wierszy oraz upewnij się, że taki wzorzec separatora nigdy nie jest używany w samych danych. tj. jeśli wybrałeś na przykład <*> do oddzielania kolumn, powinieneś sprawdzić, czy dane, które umieszczasz w tej tabeli, nie zawierają tego wzorca. możesz również użyć nagłówka wiersza i nagłówka kolumny, określając rozmiar wiersza i jakiś wewnętrzny numer indeksujący, aby przyspieszyć wyszukiwanie, a na początku każdej kolumny mieć długość tej kolumny, taką jak „Adam”, 1, 11.1, "

  • Jak szybko znaleźć elementy spróbuj użyć haszowania i indeksowania, aby wskazać dane przechowywane i buforowane na podstawie różnych kryteriów, biorąc ten sam przykład powyżej, możesz posortować wartość pierwszej kolumny i zapisać ją w osobnym obiekcie wskazującym na identyfikator wiersza elementów posortowanych alfabetycznie , i tak dalej

  • Jak przyspieszyć wstawianie danych, które znam z Oracle to to, że umieszczają dane w tymczasowym miejscu zarówno w pamięci RAM, jak i na dysku i co jakiś czas wykonują porządki, silnik bazy danych jest cały czas zajęty optymalizacją swojej struktury ale jednocześnie nie chcą stracić dane w przypadku awarii zasilania czegoś takiego. więc staraj się przechowywać dane w tym tymczasowym miejscu bez sortowania, dołącz oryginalne miejsce do przechowywania, a później, gdy system będzie wolny, skorzystaj z indeksów i wyczyść obszar tymczasowy po zakończeniu

powodzenia, świetny projekt.


11

SQLite został wspomniany wcześniej, ale chcę coś dodać.

Osobiście wiele się nauczyłem, studiując SQlite. Ciekawostką jest to, że nie przeszedłem do kodu źródłowego (chociaż tylko rzuciłem okiem). Wiele się nauczyłem, czytając materiał techniczny i specjalnie przyglądając się wewnętrznym poleceniom, które generuje. Posiada wewnętrzny interpreter oparty na stosie i możesz odczytać kod P, który generuje wewnętrznie, używając tylko funkcji wyjaśniania. W ten sposób możesz zobaczyć, jak różne konstrukcje są tłumaczone na silnik niskiego poziomu (to jest zaskakująco proste - ale to także sekret jego stabilności i wydajności).



9

Okay, znalazłem stronę, która zawiera informacje o SQL i implementacji - trochę trudno jest linkować do strony, która zawiera wszystkie samouczki, więc będę je linkować jeden po drugim:


8

Sugerowałbym skupienie się na www.sqlite.org

Jest nowy, mały (kod źródłowy 1 MB), open source (więc możesz sam to rozgryźć) ...

Napisano książki o tym, jak jest wdrażany:

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

Działa na różnych systemach operacyjnych zarówno dla komputerów stacjonarnych, jak i telefonów komórkowych, więc eksperymentowanie jest łatwe, a poznanie go będzie przydatne teraz iw przyszłości.

Ma nawet przyzwoitą społeczność tutaj: /programming/tagged/sqlite


1
Rozmiar bajtu 3.10 to obecnie prawie 7,0 MB kodu źródłowego. Tylko nieliczni uprzywilejowani mogli to wszystko przetrawić na jednym posiedzeniu. Niemniej jednak, ten jest również dobrym miejscem do rozpoczęcia.
Laurie Stearn

1
W rzeczy samej. Niedawno spędziłem trochę czasu w kodzie źródłowym SQLite w celu znalezienia błędu w SQLCipher, jest to absolutny koszmar. Życie było prostsze 6 lat temu :-)
michael aubert

Tylko krótkie pytanie, ponieważ przegapiłem imprezę, myślę, że byłoby o wiele bardziej relaksujące (i może przydatne), aby zacząć od pierwszej wersji? Właściwie powinienem to zrobić dla każdego poważnego czytania kodu dużych projektów?
Nicholas Humphrey

7

może możesz się nauczyć z HSQLDB . Myślę, że oferują małą i prostą bazę danych do nauki. możesz spojrzeć na kody, ponieważ jest to oprogramowanie typu open source.


3

Nie jestem pewien, czy będzie pasował do twoich wymagań, ale zaimplementowałem prostą bazę danych zorientowaną na pliki z obsługą simple ( SELECT, INSERT , UPDATE) przy użyciu perla.
To, co zrobiłem, to przechowywałem każdą tabelę jako plik na dysku i wpisy z dobrze zdefiniowanym wzorcem i manipulowałem danymi za pomocą wbudowanych narzędzi linuksowych, takich jak awk i sed. w celu poprawy wydajności zapisano w pamięci podręcznej często używane dane.


1
czy nadal masz kod, czy możesz udostępnić link
GK1

3

Jeśli MySQL Cię interesuje, proponuję również tę stronę wiki , która zawiera informacje o działaniu MySQL. Możesz również zapoznać się z artykułem Understanding MySQL Internals .

Można również rozważyć interfejs inny niż SQL dla silnika bazy danych. Proszę spojrzeć na Apache CouchDB . To, co nazwałbyś, system baz danych zorientowany na dokumenty.

Powodzenia!


I jeśli chcesz spojrzeć na inną bazę danych : sqlserverinternals.com, jej nbooki na wewnętrznych serwerach SQl są najważniejszymi.
HLGEM
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.