Myślałem aby w celach edukacyjnych zaprojektować i napisać silnik
miniaturowej bazy danych.
Jest taka ciekawa książka: "Systemy baz danych. Kompletny podręcznik." -
Hector Garcia-Molina, Jeffrey D. Ullman, Jennifer Widom.
Na początku wyszła sprawa endianu. Zdawało by się że to sprawa typowo
uznaniowa - na Intelu lepiej użyć Little Endian, i w zależności od
języka w C++ - Little, w Javie - Big Endian.
Skoro piszę dla Intela w C++ do raczej Little Endian,
ale
mam coś takiego jak klucz główny, w najprostszym przypadku będzie to
liczba 64-bitowa, czyli 8 bajtów, ale klucze mogą być różnej długości i
kluczem może być napis, który odczytujemy od lewej do prawej.
Aby nie było konfliktów z kluczami liczbowymi i napisowymi,trzeba jednak
wybrać Big Endian.

Druga sprawa: dostęp do rekordu jest bardzo szybki o ile jest on w
pamięci, ale wiadomo że wszystkiego nie będzie w pamięci, jak sobie w
takim przypadku radzić?

Trzecia rzecz: zamiast jednego programu Exe, należało by rozbić na
serwer i klienty. Jak by mogły się komunikować zwłaszcza na różnych
komputerach w obrębie sieci lokalnej? Co użyć? może Kafkę?

do góry

Nie znam się na implementacji transakcyjnych baz danych, ale się wypowiem:

> mam coś takiego jak klucz główny, w najprostszym przypadku będzie to
> liczba 64-bitowa, czyli 8 bajtów, ale klucze mogą być różnej długości i
> kluczem może być napis, który odczytujemy od lewej do prawej.
> Aby nie było konfliktów z kluczami liczbowymi i napisowymi,trzeba jednak
> wybrać Big Endian.

Spadek prędkości będzie tylko przy zapisie. Przy pobieraniu danych będzie trzeba też
konwertować parametry zapytań.

> Druga sprawa: dostęp do rekordu jest bardzo szybki o ile jest on w
> pamięci, ale wiadomo że wszystkiego nie będzie w pamięci, jak sobie w
> takim przypadku radzić?

A słyszał Ty o "wyszukiwaniu zewnętrznym" i B-drzewach?!? W starej książce "Algorytmy
w C++" Roberta Sedgewicka wydanej w Polsze 1999 przez wydawnictwo RM jest na końcu
rozdział (16) o tym.

> Trzecia rzecz: zamiast jednego programu Exe, należało by rozbić na
> serwer i klienty. Jak by mogły się komunikować zwłaszcza na różnych
> komputerach w obrębie sieci lokalnej? Co użyć? może Kafkę?

Protokół musisz wybrać lub zaprojektować sam...

W każdym razie: powodzonka - bo bardzo się przyda...

Szyk Cech

do góry

W dniu 22.12.2018 o 21:09, s...@g...com pisze:
> A słyszał Ty o "wyszukiwaniu zewnętrznym" i B-drzewach?!? W starej książce
"Algorytmy w C++" Roberta Sedgewicka wydanej w Polsze 1999 przez wydawnictwo RM jest
na końcu rozdział (16) o tym.

Właśnie czytam o B-drzewch w książce Moliny - najciekawszy rozdział.
Indeks może zmieścić się w pamięci cały, tym niemniej co gdy będziemy
chcieli wykonać
select * from table where warunek_jakis limit 1000
?
Będziemy mieli 1000 wskaźników na rekordy, które mogą być porozrzucane.

Jak zrobić B-drzewo:
otóż mam blok pamięci w a nim kolejno:
key0,ptr0,key1,ptr1,key2,ptr2,...keyn,ptrn,
jeśli wartość będzie pomiędzy key1 a key2 to szukamy bloku ptr1

szczegóły implementacyjne:
optymalną wielkością dla bloku będzie 4 kiB, jest to wielkość która
pokrywa się z wielkością sektora dyskowego czy 2^n sektorów, klastrem
dyskowym oraz z wielkością wymiany pamięć-dysk Intela.
Wielkość wskaźników to 8 bajtów, klucze w najprostszej postaci to też 8
bajtów (mógłby być przypadek, że klucz to pole char(40), można się zająć
tym później)
4096 bajtowy blok miałby 8 bajtowy nagłówek, reszta podzielona była by
na sloty (klucz,pointer). Wynika że maksymalnie tych slotów mogło by być
255, czyli dobrze się składa, bo ilość slotów zapiszemy w 1 bajcie w
nagłówku.
Teraz należy przy dodawaniu pomyśleć, aby b-drzewo było mniej więcej
wyważone.

do góry

W dniu 23.12.2018 o 13:49, Borneq pisze:
> Jak zrobić B-drzewo:
> otóż mam blok pamięci w a nim kolejno:
> key0,ptr0,key1,ptr1,key2,ptr2,...keyn,ptrn,
> jeśli wartość będzie pomiędzy key1 a key2 to szukamy bloku ptr1

Natrafiłem na ciekawą stronkę:
https://www.cs.usfca.edu/~galles/visualization/BTree
.html
nie bardzo widzę różnicę dla
Preemtive Split / Merge (Even max degree only)
dla przykładów które zrobiłem, było identycznie.

do góry

W dniu 23.12.2018 o 17:09, Borneq pisze:
> Natrafiłem na ciekawą stronkę:
> https://www.cs.usfca.edu/~galles/visualization/BTree
.html
> nie bardzo widzę różnicę dla
> Preemtive Split / Merge (Even max degree only)
> dla przykładów które zrobiłem, było identycznie.

Dla większych przykładów widać różnicę dla preemptive,
ale weźmy
0725
0816
0767
0557
0205
0558
0905
0441
0976
dla max degree = 3 (nieparzysty stopień, więc nie można preemptive)
oczekiwałbym że najniższy poziom - liście to będą wskaźniki do danych,
więc wszystkie klucze powinny być w liściach? a co gdy chcę znaleźć dane
dla kluczy 0767,557 czy 0905?
Coś jeszcze B-tree jest niejasne.

do góry

W dniu 24.12.2018 o 14:09, Borneq pisze:
> W dniu 23.12.2018 o 17:09, Borneq pisze:
>> Natrafiłem na ciekawą stronkę:
>> https://www.cs.usfca.edu/~galles/visualization/BTree
.html

Przyglądam się zaawansowanej implementacji:
https://github.com/myui/btree4j
prefiksowane B-drzewa są w :
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10
.1.1.800.1242&rep=rep1&type=pdf
ALE:
oszczędność jest ważna tylko do liści, bo wyższe poziomy będą naprawdę
miniaturowe.
Dla jednego bloku liścia klucze mogą różnić się bardzo mało:
np. od abcaa do abcaz, wtedy klucz abca dotyczyłby całego bloku, a
klucze byłyby samymi literami a,b,c,...z
jednak: nie mogą to być pojedyncze litery, ponieważ klucz może być
abcac5225245hg i tak większość klucza musiała by być w indeksie, aby
była możliwość stwierdzenia czy klucz taki istnieje.
Można zamiast klucza trzymać hasz klucza, wtedy można stwierdzić brak
istnienia klucza w bloku,ale aby stwierdzić że na pewno istnieje trzeba
by przeczytać dane.
A jak się ma sprawa wskaźników?: inaczej niż klucze, mogą sąsiadować
całkiem różne, oddalone od siebie, choć dobrze by było aby wszystkie
odnosiły się do tego samego megabajta, wtedy nie trzeba by dla jednego
bloku wykonywać kilkaset razy seek().
I tu jest właśnie problem: Mam duży plik i wrzucam w losowej kolejności
dane, wrzucam na koniec i uaktualniam B-drzewo.
Teraz operacja dodawania nowej kolumny: czy trzeba wszystkie dane rozsuwać?
Może tak: jedna kolumna - jeden plik?

do góry