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

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.

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/

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.

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).

Istnieją książki na ten temat, od których warto zacząć, to Database Systems: The Complete Book autorstwa Garcia-Molina, Ullman i Widom

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:

• http://c2.com/cgi/wiki?CategoryPattern
• http://c2.com/cgi/wiki?SliceResultVertically
• http://c2.com/cgi/wiki?SqlMyopia
• http://c2.com/cgi/wiki?SqlPattern
• http://c2.com/cgi/wiki?StructuredQueryLanguage
• http://c2.com/cgi/wiki?TemplateTables
• http://c2.com/cgi/wiki?ThinkSqlAsConstraintSatisfaction

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

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.

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.

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!