B+ Drzewa I Drzewa LSM to dwie podstawowe struktury danych, gdy mówimy o elementach składowych Bazy danych. Drzewa B+ są używane, gdy potrzebujemy mniej czasu na wyszukiwanie i wstawianie, a z drugiej strony drzewa LSM są używane, gdy mamy zbiory danych intensywnie zapisując i odczyty nie są zbyt wysokie.

Ten artykuł nauczy Cię o Zaloguj drzewo scalania strukturalnego znany jako Drzewo LSM . Drzewa LSM to struktura danych leżąca u podstaw wielu wysoce skalowalnych rozproszonych baz danych typu klucz-wartość NoSQL, takich jak DynamoDB, Cassandra i ScyllaDB firmy Amazon.

Drzewa LSM

Prosta wersja LSM Trees składa się z 2 poziomów drzewiastej struktury danych:

• Memtable i znajduje się całkowicie w pamięci (powiedzmy T0)
• SStables przechowywane na dysku (powiedzmy T1)

Proste drzewo LSM

Nowe rekordy są wstawiane do komponentu memtable T0. Jeżeli wstawienie powoduje, że komponent T0 przekroczy określony próg rozmiaru, ciągły segment wpisów zostanie usunięty z T0 i scalony z T1 na dysku.

Przepływ pracy LSM

LSM wykorzystuje przede wszystkim 3 koncepcje optymalizacji operacji odczytu i zapisu:

• Posortowana tabela ciągów (SSTables) : Dane są sortowane w kolejności posortowanej tak, że przy każdym czytaniu ich złożoność czasowa będzie w najgorszym przypadku wynosić O(Log(N) ), gdzie N jest liczbą wpisów w tabeli bazy danych.

  1. SSTable

• Memtable :
  • Struktura w pamięci
  • Przechowuje dane w sposób posortowany
  • Działa jako pamięć podręczna zapisu zwrotnego
  • Po osiągnięciu określonego rozmiaru jego dane są przesyłane jako SSTable do bazy danych
  • Ponieważ liczba SSTable wzrasta na dysku, a jeśli jakiś klucz nie jest obecny w rekordach
    • Czytając ten klucz, musimy przeczytać wszystkie tabele SST, co zwiększa złożoność czasu odczytu.
    • Aby rozwiązać ten problem, na scenę wchodzi filtr Blooma.
    • Filtr Blooma to zajmująca mało miejsca struktura danych, która może nam powiedzieć, czy w naszych rekordach brakuje klucza, z dokładnością 99,9%.
    • Aby skorzystać z tego filtru, możemy dodać do niego nasze wpisy podczas ich zapisywania i sprawdzić klucz na początku żądań odczytu, aby efektywniej obsługiwać żądania, gdy pojawią się na pierwszym miejscu.

Reprezentacja memtablelna

• Zagęszczanie :
  • Ponieważ przechowujemy dane na dysku jako SSTable, powiedzmy, że takowe istnieją N SSTable i rozmiar każdego stołu to M
  • Wtedy najgorszy przypadek Czytać złożoność czasowa wynosi O( N* Log(M) )
  • Tak więc, gdy liczba tabel SST wzrasta Przeczytaj Złożoność czasowa również wzrasta.
  • Ponadto, gdy właśnie opróżniamy tabele SST w bazie danych, ten sam klucz jest obecny w wielu tabelach SST
  • Tutaj pojawia się zastosowanie zagęszczarki
  • Compactor działa w tle, łączy SSTables i usuwa wiele wierszy z tym samym, dodaje nowy klucz z najnowszymi danymi i przechowuje je w nowym połączonym/skompaktowanym SSTable.

3.1. SSTables przeniesione na dysk

3.6. Zagęszczarka zagęściła 2 stoły SSTable do 1 stołu SSTable

Wniosek:

• Zapisy są przechowywane w drzewie pamięci (Memtable). W razie potrzeby aktualizowane są także wszelkie pomocnicze struktury danych (filtry Bloom i indeks rzadki).
• Kiedy to drzewo stanie się zbyt duże, jest przerzucane na dysk z kluczami w posortowanej kolejności.
• Kiedy przychodzi odczyt, sprawdzamy go za pomocą filtra Blooma. Jeżeli filtr Blooma wskaże, że wartość nie istnieje, wówczas informujemy klienta, że ​​nie udało się znaleźć klucza. Jeśli filtr Bloom oznacza, że ​​wartość jest obecna, zaczynamy iterację SSTables od najnowszej do najstarszej.
• Złożoność czasowa LSM
  • Czas czytania: O(log(N)) gdzie N jest liczbą rekordów na dysku
  • Czas zapisu: O(1) jak zapisuje w pamięci
  • Usuń czas: O(log(N)) gdzie N jest liczbą rekordów na dysku
• Drzewa LSM można modyfikować w celu uzyskania bardziej wydajnych struktur danych przy użyciu więcej niż 2 filtrów. Niektóre z nich to bLSM, Diff-Index LSM.