Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > pl.comp.programming > #32138 > unrolled thread

Projektowanie bazki danych

Back to article view | Back to pl.comp.programming

Contents

  Projektowanie bazki danych Borneq <borneq@antyspam.hidden.pl> - 2018-12-22 14:54 +0100
    Re: Projektowanie bazki danych szykcech@gmail.com - 2018-12-22 12:09 -0800
      Re: Projektowanie bazki danych Borneq <borneq@antyspam.hidden.pl> - 2018-12-23 13:49 +0100
        Re: Projektowanie bazki danych Borneq <borneq@antyspam.hidden.pl> - 2018-12-23 17:09 +0100
          Re: Projektowanie bazki danych Borneq <borneq@antyspam.hidden.pl> - 2018-12-24 14:09 +0100
            Re: Projektowanie bazki danych Borneq <borneq@antyspam.hidden.pl> - 2018-12-24 19:16 +0100

#32138 — Projektowanie bazki danych

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ę?

[toc] | [next] | [standalone]

#32139

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

[toc] | [prev] | [next] | [standalone]

#32140

W dniu 22.12.2018 o 21:09, szykcech@gmail.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.

[toc] | [prev] | [next] | [standalone]

#32141

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.

[toc] | [prev] | [next] | [standalone]

#32143

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.

[toc] | [prev] | [next] | [standalone]

#32144

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?

[toc] | [prev] | [standalone]

Back to top | Article view | pl.comp.programming

csiph-web