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!

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.

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

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.

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.