Jakie są różnice między algorytmami używającymi struktur danych a algorytmami korzystającymi z baz danych?

10

Pytanie ogólne

Jakie są różnice między algorytmami używającymi struktur danych a algorytmami korzystającymi z baz danych?

Jakiś kontekst

To pytanie mnie denerwuje od jakiegoś czasu i nie byłem w stanie znaleźć na to przekonującej odpowiedzi.

Obecnie pracuję nad pogłębieniem zrozumienia algorytmów, które oczywiście w dużym stopniu obejmują struktury danych. Są to podstawowe struktury, takie jak Torba, Kolejka, Stos, Kolejka priorytetowa i Sterta.

Korzystam również z baz danych na co dzień do przechowywania danych, które zostały przetworzone i przesłane przez użytkownika końcowego lub przetworzone przez program. Pobieram i przesyłam dane za pośrednictwem DAL, który ma własne struktury danych, które są generowane na podstawie tabel w bazie danych.

Moje pytania pojawiają się, gdy mam opcję sortowania danych za pomocą bazy danych, aby odesłać je do mnie w kolejności rosnącej / malejącej lub pobrać i załadować dane do mojej logiki, przetworzyć te dane w kolejce priorytetowej i sortować sterty wszystko. Innym może być wyszukiwanie rekordów za pomocą bazy danych zamiast ładowania ich podzbiorów i korzystanie z czegoś takiego jak wyszukiwanie binarne w celu znalezienia rekordu lub rekordów, którymi jestem zainteresowany.

Moim zdaniem starałbym się wykonać jak najwięcej operacji na końcu bazy danych przed wysłaniem, ponieważ komunikacja jest droga. To sprawia, że ​​zastanawiam się, kiedy używasz algorytmów i struktur danych ściśle zdefiniowanych w ramach własnej logiki, a nie do przetwarzania danych w bazie danych?

Oto pytania ...

pytania

  1. Jakie są różnice między strukturami danych a bazami danych?
  2. Kiedy używamy algorytmów wykorzystujących struktury danych zdefiniowane wyłącznie w ramach własnej logiki, a nie bazy danych?
  3. @Harvey post: Kiedy metody w bazie danych stają się mniej wydajne w użyciu niż metody we własnej logice?
    • @mirculixx post: Co sprawia, że ​​metoda jest wydajna?
  4. @Harvey post: W jaki sposób przetwarzanie danych ze strukturami danych jest szybsze niż w bazie danych?

Wyjaśnienia

  1. @Grant post: Bazy danych, z którymi normalnie pracuję, są relacyjne i te pytania wynikają z ich pracy. Myślę jednak, że te pytania dotyczą wszystkich ram trwałości (kiedy mówię o ramach, mam na myśli je w najbardziej ogólnym znaczeniu).

Wiem, że odpowiedzi bez określonego kontekstu są trudne. Jedzenie do przemyślenia, porady lub punkty do dyskusji to przede wszystkim to, czego szukam i byłbym bardzo wdzięczny!

hulkmeister
źródło
Datomic.com baza danych jest bliżej użytkownika niż tradycyjne relacyjnych. Czy patrzysz tylko na tradycyjne bazy danych?
Job
@ Job Nie, relacyjne bazy danych nie są jedyną rzeczą, którą rozważam tutaj. Chodzi bardziej o zrozumienie różnicy między strukturami danych w logice a strukturami danych w bazie danych / jednostce trwałości.
hulkmeister
Zasadniczo powiedziałbym - użyj bazy danych, jeśli możesz, ale jeśli stanie się ona zbyt wolna, skorzystaj ze struktur danych. Powielanie danych (np. Buforowanie) jest złe, ponieważ musisz je zsynchronizować, więc unikaj tego, chyba że nie możesz.
Job
Wysyłasz dane do bazy danych tylko po to, aby je posortować? Lubisz jeździć po okolicy, aby zmienić zdanie?

Odpowiedzi:

18

Struktury danych to w przeważającej części:

  1. Rezydent pamięci,
  2. Przemijający,
  3. Ograniczony rozmiar,
  4. Niepowodzenie ponownego wejścia bez dodania mechanizmów współbieżności, takich jak blokady lub niezmienność,
  5. Niezgodny z ACID ,
  6. Szybko, jeśli zostanie starannie wybrany.

Bazy danych to w przeważającej części:

  1. Związany z dyskiem,
  2. Trwały,
  3. Duży,
  4. Bezpiecznie współbieżne,
  5. Zgodny z ACID, z możliwościami transakcyjnymi ,
  6. Wolniej niż struktury danych

Struktury danych mają być przekazywane z jednego miejsca do drugiego i wykorzystywane wewnętrznie w programie. Kiedy ostatni raz wysłałeś dane ze strony internetowej na serwer sieciowy przy użyciu bazy danych lub wykonałeś obliczenia na bazie danych, która była całkowicie rezydentna w pamięci?

Systemy baz danych wykorzystują struktury danych w ramach ich wewnętrznej implementacji. To kwestia wielkości i zakresu; używasz struktur danych w swoim programie, ale system baz danych jest programem sam w sobie.

Robert Harvey
źródło
Jeśli chodzi o uwagę strony internetowej na serwer internetowy, zgadzam się, że nie używałbyś tam bazy danych, ale widzę możliwość istnienia serwletu do obsługi lub tłumaczenia tych danych w celu zachowania ich w bazie danych. To między warstwą środkową a warstwą danych sytuacja staje się nieco zagmatwana. Aby uprościć pytanie, kiedy metody w bazie danych stają się mniej korzystne w użyciu niż metody w logice?
hulkmeister
1
To chleb i masło DAL, prawda? Istnieją DAL, aby ułatwić przechodzenie między obiektami i rekordami bazy danych. DAL są dobre dla około 80 do 90 procent tego, co chcesz zrobić z bazą danych, ale dla pozostałych 10 do 20 procent możesz wrócić do surowego SQL lub procedur przechowywanych, ponieważ jest to bardziej wydajne.
Robert Harvey
W twoim przykładzie sortowania / filtrowania masz rację, że prawdopodobnie chcesz wykonać tego rodzaju przetwarzanie na serwerze bazy danych. Ale najprawdopodobniej nadal otrzymasz wynik tego przetwarzania jako jakąś formę struktury danych.
Robert Harvey
Podane przez ciebie punkty były bardzo pouczające. Jednak wciąż coś mnie dręczy w metodach (lub algorytmach), które działają bezpośrednio z bazą danych lub tylko ze strukturami danych ściśle w obrębie logiki lub obu tych metod. Patrzę na punkt 6 obu list, które odłożyłeś, i pojawia się pytanie, jak jedna jest szybsza od drugiej? Zawsze uważałem, że praca z danymi u źródła jest najszybszym sposobem na załatwienie różnych spraw. Możesz aktualizować w swoim poście - przeczytam go ponownie.
hulkmeister
1
Bazy danych działają wolniej z wielu powodów. Niezależnie od buforowania, musisz odczytać dane z dysku, używając instrukcji SQL, którą należy skompilować, mając plan wykonania często obejmujący wiele tabel. Proces jest znacznie bardziej złożony. Ponadto generalnie nadal musisz przesłać wynik za pośrednictwem drutu, gdzie zamieniasz dane na struktury danych, abyś mógł z nimi pracować.
Robert Harvey
6

Jakie są różnice między strukturami danych a bazami danych?

Na poziomie abstrakcyjnym nie ma - baza danych jest strukturą danych.

Na określonym poziomie bazy danych zazwyczaj mają na celu utrwalenie danych, zwykle w formacie zoptymalizowanym pod kątem wstawiania, aktualizacji, pobierania, łączenia lub w innym celu (lub kombinacji).

Np. Jeśli porównasz tabelę w RDBMS z tablicą danych, różnica może wynikać z czasu działania algorytmu, ilości kodu, który musisz napisać, ilości pamięci potrzebnej do uruchomienia algorytmu lub elastyczność pracy / dostępu do danych spoza programu / algorytmu.

Kiedy używamy algorytmów wykorzystujących struktury danych zdefiniowane wyłącznie w ramach własnej logiki, a nie bazy danych?

Z tendencją kłóciłbym się

a) korzystać z bazy danych, jeśli chcesz utrwalić dane w sposób dostępny poza czasem wykonania lub celem określonego algorytmu.

b) używać własnej struktury danych (w pamięci), jeśli liczy się szybkość działania lub trwałość nie jest wymagana

Np. Jeśli twój algorytm przetwarza rekordy klientów, możesz chcieć przechowywać te rekordy klientów (powiedz, aby znaleźć wszystkich klientów w danym obszarze) do późniejszego wykorzystania przez inny program / algorytm i do zupełnie innego celu (powiedz, aby znaleźć najbardziej wartościowych klientów ). W takim przypadku użycie bazy danych do utrwalenia danych jest prawdopodobnie dobrym pomysłem.

Należy jednak pamiętać, że istnieje koncepcja baz danych w pamięci, które niekoniecznie utrwalają dane ze względu na wydajność. Np. Redis lub HANA .

Kiedy metody w bazie danych stają się mniej wydajne w użyciu niż metody we własnej logice?

Odpowiedź zależy w dużej mierze od okoliczności i używanej bazy danych (rodzaju). Zmieniłbym pytanie na „co sprawia, że ​​metoda jest skuteczna?” Następnie staje się ćwiczeniem oceny metod (= algorytm), których użyłbyś dla własnej struktury danych w porównaniu z metodami używanymi przez bazę danych. Zobacz także następny punkt.

W jaki sposób przetwarzanie danych ze strukturami danych jest szybsze niż w bazie danych?

Znowu zależy to od specyfiki. Zasadniczo przetwarzanie danych znajdujących się w pamięci, bezpośrednio dostępnych dla procesu uruchamiającego algorytm, jest szybsze niż wysłanie żądania do innego procesu (na tym samym komputerze lub w sieci) i poproszenie go o odesłanie wyników . Jednak jeśli dane już znajdują się w bazie danych, wysłanie do niej polecenia - powiedzmy instrukcję SQL, aby połączyć dwie tabele i obliczyć jakąś funkcję agregującą - i pobranie tylko niewielkiego podsumowania lub podzbioru danych może być znacznie bardziej wydajne niż pierwsze przesłanie wszystkich dane i lokalne obliczanie wyników (przy użyciu własnych struktur danych).

miraculixx
źródło
1

Dostęp do dysku jest przede wszystkim tym, co jest najdroższe w tej operacji, częściej niż dostęp do sieci (http://serverfault.com/questions/238417/are-networks-now-faster-than-disks). O ile baza danych nie znajduje się w sieci co najmniej 1 Gb / s i tej samej sieci co serwer WWW / aplikacji, wydajność sieci nie będzie miała tak dużego znaczenia, jak wydajność dysku w przypadku większych zestawów danych. Lub jeśli twoje dane znajdują się na bardzo szybkich dyskach półprzewodnikowych, które będą szybsze niż typowy dostęp do sieci. Ponadto bazy danych zwykle zapewniają mechanizm IPC, taki jak potoki nazwane, zamiast używania protokołu TCP / IP, jeśli baza danych znajduje się na tym samym serwerze, co serwer aplikacji.

Jeśli możesz zachować większość struktury danych w pamięci między żądaniami, będzie to na ogół twój najszybszy zakład. Jeśli nie możesz, trudno jest pokonać dobrą strukturę bazy danych ze znormalizowanymi tabelami i odpowiednimi indeksami do wyszukiwania i aktualizacji wydajności na czymkolwiek innym niż małe zestawy rekordów, szczególnie w systemie z milionami rekordów.

Relacyjne bazy danych zwykle używają drzewa B + lub jego wariantu pod maską i mają wiele optymalizacji, takich jak wyrównanie danych na dyskach i pule buforów dla często używanych rekordów. To sprawia, że ​​przodują w szybkim przetwarzaniu dużych zestawów danych, zwłaszcza jeśli chodzi o agregację lub filtrowanie.

Peter Smith
źródło
Powiedz mi, czy mam rację. Stosując to, co powiedziałeś, ilekroć myślę o pracy z danymi, jeśli mogę zachować zestaw roboczy w pamięci podręcznej, jest to szybsze. W przeciwnym razie, spróbuj użyć bazy danych, aby dostarczyć te wyniki, lub znaleźć sposób na więcej zapytań do bazy danych?
hulkmeister
@ hulkmeister tak ogólnie, chyba że zestaw danych jest bardzo mały lub baza danych jest zdalna do twojej lokalizacji w wolnej sieci.
Peter Smith
0

Co rozumiesz przez bazę danych? Czy masz na myśli relacyjną bazę danych, taką jak MySQL lub SQL Server? Relacyjna baza danych to struktura metadanych, która obsługuje pewien podzbiór operacji zdefiniowanych przez model relacyjny . Teoria modelu relacyjnego, którą w większości opracował Edgar Codd w latach 60.

Model relacyjny ma bardzo ogólny cel i jest elastyczny, ale oznacza to, że nie może wykorzystać żadnej struktury danych ani wzorców dostępu. Struktury danych są przydatne, gdy wiesz coś o danych i sposobie dostępu do nich. Na przykład, jeśli wiesz, że ostatnie dane, które umieścisz w strukturze danych, będą pierwszymi danymi, których chcesz użyć, możesz użyć stosu.

Relacyjną bazę danych nazwałem strukturą metadanych, ponieważ jest to na ogół dość duży pakiet oprogramowania, który wykorzystuje wiele struktur danych, takich jak stosy, kolejki, drzewa i listy, do tworzenia abstrakcyjnej struktury danych tabeli relacyjnej.

Charles E. Grant
źródło
Przepraszam, potrzebuję tylko wyjaśnienia, co oznacza „trochę zwiędły” w odniesieniu do ostatniego akapitu?
hulkmeister
@hulkmeister, przepraszam, że powinno to być „duże”, a nie „trochę”. model relacyjny jest bardzo abstrakcyjny i dość złożony. Zapewnienie implementacji, która faktycznie działa odpowiednio, szczególnie takiej, która zapewnia ACID ((Atomowość, Spójność, Izolacja, Trwałość) wymaga użycia bardzo wyrafinowanego kodu działającego w tle
Charles E. Grant