Struktury przechowywania baz danych - Database storage structures

Tabele i indeksy bazy danych mogą być przechowywane na dysku w jednej z wielu form, w tym uporządkowanych/nieuporządkowanych płaskich plików , ISAM , plików sterty , wiader mieszających lub drzew B+ . Każda forma ma swoje szczególne zalety i wady. Najczęściej stosowanymi formami są B-drzewa i ISAM. Takie formularze lub struktury są jednym z aspektów ogólnego schematu używanego przez aparat bazy danych do przechowywania informacji.

Niezamówiony

Magazyn nieuporządkowany zazwyczaj przechowuje rekordy w kolejności ich wstawiania. Takie przechowywanie zapewnia dobrą wydajność wstawiania ( ), ale nieefektywne czasy wyszukiwania ( ). Zazwyczaj te czasy pobierania są jednak lepsze, ponieważ większość baz danych używa indeksów na kluczach podstawowych , co powoduje, że czasy pobierania kluczy lub dla kluczy są takie same jak przesunięcia wierszy bazy danych w systemie pamięci masowej.

Zamówione

Uporządkowany magazyn zazwyczaj przechowuje rekordy w porządku i może wymagać zmiany kolejności lub zwiększenia rozmiaru pliku po wstawieniu nowego rekordu, co skutkuje niższą wydajnością wstawiania. Jednak uporządkowane przechowywanie zapewnia bardziej wydajne wyszukiwanie, ponieważ rekordy są wstępnie sortowane, co powoduje złożoność .

Pliki uporządkowane

Pliki sterty

Pliki sterty to listy nieuporządkowanych rekordów o zmiennej wielkości. Chociaż mają podobną nazwę, pliki sterty znacznie różnią się od stert w pamięci . Sterty w pamięci są uporządkowane, w przeciwieństwie do plików sterty.

  • Najprostsza i najbardziej podstawowa metoda
    • wstawka wydajna, nowe rekordy dodawane na końcu pliku, zapewniające porządek chronologiczny
    • pobieranie skuteczne, gdy uchwytem do pamięci jest adres pamięci
    • wyszukiwanie nieefektywne, ponieważ wyszukiwanie musi być liniowe
    • usunięcie odbywa się poprzez oznaczenie wybranych rekordów jako „usuniętych”
    • wymaga okresowej reorganizacji, jeśli plik jest bardzo ulotny (często zmieniany)
  • Zalety
    • wydajny przy zbiorczym ładowaniu danych
    • wydajne dla stosunkowo małych relacji, ponieważ unika się kosztów ogólnych indeksowania
    • wydajne, gdy wyszukiwanie obejmuje dużą część przechowywanych rekordów
  • Niedogodności
    • nieskuteczne w przypadku selektywnego wyszukiwania przy użyciu wartości kluczy, zwłaszcza jeśli są duże
    • sortowanie może być czasochłonne
    • nie nadaje się do lotnych stołów

Wiadra haszujące

  • Funkcje haszujące obliczają adres strony, na której ma być przechowywany rekord na podstawie jednego lub więcej pól w rekordzie
    • funkcje mieszające wybrane w celu zapewnienia równomiernego rozmieszczenia adresów w przestrzeni adresowej
    • „Zajętość” to zazwyczaj 40% do 60% całkowitego rozmiaru pliku
    • unikalny adres nie jest gwarantowany, dlatego wymagane są mechanizmy wykrywania kolizji i rozwiązywania kolizji
  • Otwórz adresowanie
  • Przepełnienie łańcuchowe/nieprzykute
  • Plusy i minusy
    • wydajny dla dokładnych dopasowań na polu kluczowym
    • nie nadaje się do wyszukiwania zasięgu, co wymaga sekwencyjnego przechowywania
    • oblicza miejsce przechowywania rekordu na podstawie pól w rekordzie
    • funkcje skrótu zapewniają równomierne rozpowszechnianie danych
    • możliwe są kolizje, dlatego wymagane jest wykrywanie i przywracanie kolizji

B+ drzew

Są to najczęściej stosowane w praktyce.

  • Czas potrzebny na dostęp do dowolnego rekordu jest taki sam, ponieważ przeszukiwana jest ta sama liczba węzłów
  • Indeks jest indeksem pełnym, więc plik danych nie musi być zamawiany
  • Plusy i minusy
    • wszechstronna struktura danych – dostęp sekwencyjny i losowy
    • dostęp jest szybki
    • skutecznie obsługuje dokładne dopasowanie, zakres, klucz części i wzór.
    • pliki ulotne są obsługiwane wydajnie, ponieważ indeks jest dynamiczny – rozszerza się i kurczy wraz ze wzrostem i kurczeniem tabeli
    • gorzej przystosowany do względnie stabilnych plików – w tym przypadku ISAM jest bardziej wydajny

Orientacja na dane

Większość konwencjonalnych relacyjnych baz danych używa pamięci „zorientowanej na wiersze”, co oznacza, że ​​wszystkie dane związane z danym wierszem są przechowywane razem. W przeciwieństwie do tego, DBMS zorientowany kolumnowo przechowuje wszystkie dane z danej kolumny razem, aby szybciej obsługiwać zapytania w stylu hurtowni danych . Bazy danych korelacji są podobne do baz danych opartych na wierszach, ale stosują warstwę pośrednią, aby mapować wiele wystąpień tej samej wartości na ten sam identyfikator liczbowy.

Zobacz też