Chciałbym napisać mega prostą bazę danych, a dokładniej chyba silnik bazodanowy w celach edukacyjnych. Szukałem w internecie i są nawet jakieś tutoriale, ale nie chcę się na nikim wzorować ani przepisywać kodu. Chciałbym poznać teorię działania bazy/silnika, jak to wygląda pod spodem i na jej podstawie spróbować coś zaimplementować. Proszę o podzielenie się materiałami/książkami tłumaczącymi działanie baz danych od strony teoretycznej.
3
4
Widziałem, że O'Reilly wydało niedawno (2019) książkę o szczegółach implementacjach baz danych: Database Internals Alexa Petrova https://www.oreilly.com/library/view/database-internals/9781492040330/
2
KIlka rozróżnień.
Jak spojrzysz na dominujacy rynek, pomyślisz że każda baza ma język SQL (i jego interpreter).
No nie każda.
Język SQL uchodzi za bardzo trudny w implementacji, syntax nie jest czystym syntaxem, konstrukcje lokalne mają sens lub nie mają zaleznie od szerszej "chmurki" semantyki. Sądzę, ze dla nawet doświadczonego singla bez szans.
Więc 1. czy z językiem SQL (lub odpowiednikiem) czy nie. Są key-value (nie mówie o cluodowych, a lokalnych jak Berkeley DB, Kyoto cabinet i podobne)
edit: również rejestr Windows
Zajmijmy się spodem. Pojawia się (2) zbiór główny i indeks (indeksy)
Zbiór główny jest łatwiejszy, gdy chodzi o rekordy stałej długości (bajka, w sam raz na dydaktykę), znacznie trudniejszy w zarządzaniu gdy zmiennej długości (3)
Idenksy to przede wszystkicm czytanie o R-Drzewach (R-tree), w tym pokrewnych i to powszechnie dostepna wiedza "studencka" (4)
Rekord moze dawać zdolnosc zewnętrzenej interpretacji (mieć nazwane pola) - lub byc czytelny tylko dla programu np w C++ (jako struktury). (5)
Stałorekordowy z nazwanymi polami to np taka klasyka jak dBase (Clipper, Harbour Project) czy FoxPro
2
sql czy nosql ? — flinst-one 34 minuty temu
Jestem @flinst-one za a nawet przeciw :)
Za podobnym wyborem, ale "nosql" to taka parasolka z której NIC nie wynika.. Już pominę nowszy sposób czytania Not Only Sql, ale nie da sie niczego zdefinciowac przez "nie".
"Zjadłbym do kawy nie-paluszka".
1
aby poznać jak to działa na samym spodzie możesz napisać kopię DBFów - to jest chyba najprostszy typ baz - bazy plikowe.
0
@Spearhead: Przeglądnąłem i wygląda dobrze, dzięki.
@abrakadaber: Chodzi o SQLite? Czy znasz jeszcze jakieś prostsze alternatywy?
Nie wiem, czy chcę koniecznie walczyć z SQL, bo pewnie sama implementacja tokenizacji(?) to by była mordęga? Sorry, jestem totalnie niekompetentny w tej dziedzinie, chodzi mi o to, że silnik musi sparsować zapytanie SQL i "zrozumieć", więc trzeba to zaimplementować.
Głównie interesuje mnie implementacja struktur danych, czytałem, że większość baz SQL działa na drzewach binarnych(?). Kiedyś też czytałem, że baza jest zapisywana w postaci binarnej podzielona na bloki(?), każdy blok ma np. 4096 kB, część bloku zajmuje nagłówek i jest w nim też część na dane itd. Pewnie piszę straszne brednie, bo to dla mnie czarna magia. Jeśli baza noSQL też implementuje takie rzeczy, to może łatwiej taką?
Niestety mój stan wiedzy jest zerowy i nawet nie wiem, jak wam określić o co mi chodzi.
No i baza danych to bardzo szerokie pojęcie. Szukałem też przykładów, żeby na nie zerknąć i np. trafiłem na coś takiego: https://github.com/typicode/lowdb
Załóżmy, że chciałbym napisać bazę, która udostępnia takie API, jak ten przykład, ale warstwa danych byłaby niskopoziomowa tzn. implementowała to wsyzstko o czym wyżej pisałem. Ma jakikolwiek sens to co piszę?
Bo przecież tutaj autor wykorzystał wysokopoziomowe API, dlatego to tak wygląda, ale na końcu to i tak zbiór zer i jedynek.
Albo taki przykład: https://github.com/pouchdb/pouchdb
Jest to baza danych w rozumnieniu takim, w jakim zrozumieliście mój pierwszy post? Jakkolwiek tyczą się jej pojęcia z książki, którą podał @Spearhead, czy zasada działania jest kompletnie inna i w tym wypadku nie jest tym co mnie interesuje?
1
szafran98 napisał(a):
Kiedyś też czytałem, że baza jest zapisywana w postaci binarnej podzielona na bloki(?), każdy blok ma np. 4096 kB, część bloku zajmuje nagłówek i jest w nim też część na dane itd.
To (może) być trochę inaczej dla bazy "plik na tabelę" (zwykle maja oddzielny plik / pliku na indeksy do danej tabeli) vs "wszystkie tabele w jednym pliku".
Pierwsze to Postgres i MySQL, drugie Micorosoft czy Interbase
Profesjonalna baza danych MUSI optymalizować względem pracy dysku i - sądzę niemały wysiłek intelektualny z tym związany - patrzy "blokami" czy "stronami". W dydaktynym to by była masakra.
szafran98 napisał(a):
Jeśli baza noSQL też implementuje takie rzeczy, to może łatwiej taką?
Stwierdzenie "baza NoSQL" samo w sobie nie znaczy nic.
szafran98 napisał(a):
@abrakadaber: Chodzi o SQLite? Czy znasz jeszcze jakieś prostsze alternatywy?
Nie.
DBF to nie SQLite
DBFy to najprościej jak można. Podstawa polskiego IT 1985-199...
szafran98 napisał(a):
Niestety mój stan wiedzy jest zerowy i nawet nie wiem, jak wam określić o co mi chodzi.
Drzewa (intelektualnie najpierw B-dtreza, potem rozszerzamy na R-drzewa), podstawowa wiedza wykładowa
2
nie, SQLite to jest cały silnik, który implementuje też SQLa - DBFy to są pliki rekordowe z dodatkowymi plikami indeksowymi (jedna tabela to jeden plik + dodatkowy plik dla każdego indeksu). Myślę, że jakąś implementację możesz od tego zacząć. Z jednej strony jest to w miarę proste do implementacji (jak już ogarniesz usuwanie rekordów, trzymanie opisu pól, wielodostęp, jakieś API do odczytu danych) a z drugiej, pod spodem, większość baz SQLowych trzyma dane właśnie w ten sposób (w bardzo wielkim uproszczeniu) dodając dodatkową warstwę w postaci SQLa i serwera, który zarządza serwowaniem danych i wielodostępem
1
abrakadaber napisał(a):
nie, SQLite to jest cały silnik, który implementuje też SQLa - DBFy to są pliki rekordowe z dodatkowymi plikami indeksowymi (jedna tabela to jeden plik + dodatkowy plik dla każdego indeksu). Myślę, że jakąś implementację możesz od tego zacząć. Z jednej strony jest to w miarę proste do implementacji (jak już ogarniesz usuwanie rekordów, trzymanie opisu pól, wielodostęp, jakieś API do odczytu danych) a z drugiej, pod spodem, większość baz SQLowych trzyma dane właśnie w ten sposób (w bardzo wielkim uproszczeniu) dodając dodatkową warstwę w postaci SQLa i serwera, który zarządza serwowaniem danych i wielodostępem
Pliki główne DBF były 99% kompatybilne pomiędzy ówczesnymi vendorami (chyba w wersji Microsoft Fox doszedł jakiś dodatkowy inny typ numeryczny), ale indeksy były totalnie różne, niekompatybilne
Wdzieczny temat do samoróbek
Implementacja javowska zupełnie "na goło" (pliku glównego - bez indeksów) to może 10 klas i 2-4tys linii kodu
0
@abrakadaber: Tak jak to przedstawiasz, to te DBFy wygląda, że zawierają właśnie to co mnie interesuje. Poczytam o tym więcej.
@ZrobieDobrze: Niestety nie doceniłem studiów kiedy mogłem i teraz będę tę wiedzę nadrabiał.
0
Znazałem artykuł, który kiedyś czytałem i z tego w ogóle narodził się u mnie taki pomysł: https://www.codeproject.com/Articles/1029838/Build-Your-Own-Database
Jak byście skategoryzowali ten twór? Jak można nazwać taką bazę?
0
Nazwa: saffronDB
2
Kleppman swojej książce "Przetwarzanie danych w dużej skali" opisuje np. Jak zaimplementować silnik bazy typu klucz - wartość.
1
@szafran98: Znam lepszą drogę. Zamiast pisać i się ograniczać się własną niewiedzą zacznij studiować kod bazy, która najbardziej Ciebie interesuje, próbuj uwzględnić możliwość wsparcia Twórców.
Ja na przykład w wolnych chwilach studiuje projekty niemodyfikowalnych baz i widzę to jako dobry kompromis między wiedzą jaka wyciągam, a czasem jaki muszę w istniejący projekt włożyć.
Na plus jest również to, że poznanie bazy to również zrozumienie kompromisów jakich twórcy bazy musieli dokonać, tego typu rzecz znacznie łatwiej jest zrozumieć jeśli możesz się do nich zwrócić z pytaniem.
4
tutaj materiały z amerykanskiej uczelni (w polskich takich rzeczy nie ma ;))
https://www.youtube.com/c/CMUDatabaseGroup/playlists
https://www.youtube.com/playlist?list=PLSE8ODhjZXjYplQRUlrgQKwIAV3es0U6t
1
tutaj jest trochę ciekawego materiału: https://cstack.github.io/db_tutorial/ - gość implementuje SQLLite po swojemu;
1
Masz parę problemów do rozwiązania:
- zapis/odczyt danych z dysku, organizacja ich przechowywania, żeby te operacje były efektywne, cache, dane w pamięci
- indeksowanie danych
- transakcyjność (nie da się tego pominąć, bo chociaż na poziomie pojedynczego rekordu musisz zapewnić atomiczność)
Idąc w SQL (i ogólnie relacyjne bazy danych), jest do napisania parser SQL, optymalizator zapytań. Właśnie optymalizator, czyli mechanizm, który do intencji wyrażonej zapytaniem dostosuje sposób jego realizacji jest największym wyzwaniem.
Dość "prosto" za to da się napisać bazę danych, taką jak, jeżeli mnie marketing google nie zmylił, https://cloud.google.com/firestore
Czyli baza danych czysto obiektowa, przyjmuje i zwraca dokumenty w postaci Json, wyszukiwanie tylko i wyłącznie po indeksach, optimistic locking.