Globale to miecze skarbów do przechowywania danych. Drzewa. Część 1
Prawdziwe miecze bazy danych - globale - są znane od dawna, ale wciąż niewielu wie, jak skutecznie z nich korzystać lub w ogóle nie posiada tej superbroni.
Jeśli użyjesz globali do rozwiązywania problemów, w których są naprawdę dobrzy, możesz osiągnąć znakomite wyniki. Albo w produktywności, albo w uproszczeniu rozwiązania problemu (1, 2).
Globale to specjalny sposób przechowywania i przetwarzania danych, zupełnie inny niż tabele w SQL. Pojawiły się w 1966 roku w języku ŚWINKA) (rozwój ewolucyjny - Skrypt obiektowy pamięci podręcznej, dalej COS) w bazie medycznej i nadal tam jest aktywnie wykorzystywane, a także przeniknął do innych obszarów, w których wymagana jest niezawodność i wysoka wydajność: finanse, handel itp.
Globale w nowoczesnych systemach DBMS obsługują transakcje, rejestrowanie, replikację i partycjonowanie. Te. można z nich zbudować nowoczesne, niezawodne, rozproszone i szybkie systemy.
Globale nie ograniczają Cię do modelu relacyjnego. Dają swobodę tworzenia struktur danych zoptymalizowanych pod kątem konkretnych zadań. W przypadku wielu aplikacji inteligentne wykorzystanie globali może być naprawdę tajną bronią, zapewniającą wydajność, o której twórcy aplikacji relacyjnych mogą jedynie marzyć.
Globale jako sposób przechowywania danych mogą być stosowane w wielu nowoczesnych językach programowania, zarówno wysokiego, jak i niskiego poziomu. Dlatego w tym artykule skupię się konkretnie na globalach, a nie na języku, z którego kiedyś pochodziły.
2. Jak działają globale
Najpierw zrozummy, jak działają globale i jakie są ich mocne strony. Na globale można patrzeć z różnych punktów widzenia. W tej części artykułu spojrzymy na nie jak na drzewa. Lub jak hierarchiczne hurtownie danych.
Mówiąc prościej, global jest trwałą tablicą. Tablica, która jest automatycznie zapisywana na dysku.
Trudno sobie wyobrazić coś prostszego do przechowywania danych. W kodzie (w językach COS/M) różni się od zwykłej tablicy asocjacyjnej jedynie symbolem ^ przed nazwą.
Aby zapisać dane w trybie globalnym, nie trzeba uczyć się języka zapytań SQL, polecenia do pracy z nimi są bardzo proste. Można się ich nauczyć w godzinę.
Zacznijmy od najprostszego przykładu. Drzewo jednopoziomowe z 2 gałęziami. Przykłady są napisane w COS.
Set ^a("+7926X") = "John Sidorov"
Set ^a("+7916Y") = "Sergey Smith"
Podczas wstawiania informacji do globala (polecenie Ustaw) automatycznie dzieją się 3 rzeczy:
Zapisywanie danych na dysku.
Indeksowanie. W nawiasie znajduje się klucz (w literaturze angielskiej „indeks dolny”), a na prawo od równości znajduje się wartość („wartość węzła”).
Sortuj. Dane są sortowane według klucza. W przyszłości podczas przechodzenia przez tablicę pierwszym elementem będzie „Sergey Smith”, a drugim „John Sidorov”. Otrzymując listę użytkowników z globala, baza danych nie traci czasu na sortowanie. Co więcej, możesz zażądać wyniku posortowanej listy, zaczynając od dowolnego klucza, nawet nieistniejącego (wyjście rozpocznie się od pierwszego prawdziwego klucza, który następuje po nieistniejącym kluczu).
Wszystkie te operacje dzieją się niesamowicie szybko. Na moim domowym komputerze uzyskiwałem wartości do 750 000 wstawek/s w jednym procesie. W procesorach wielordzeniowych wartości mogą osiągnąć dziesiątki milionów wstawki/sek.
Oczywiście sama prędkość wstawiania nie mówi zbyt wiele. Możesz na przykład bardzo szybko zapisać informacje w plikach tekstowych - w ten sposób plotki Przetwarzanie wiz działa. Ale w przypadku globali otrzymujemy w rezultacie ustrukturyzowany indeksowany magazyn, z którym można łatwo i szybko pracować w przyszłości.
Największą zaletą globali jest szybkość, z jaką można wstawiać nowe węzły.
Dane w skali globalnej są zawsze indeksowane. Przemierzanie ich, zarówno na jednym poziomie, jak i w głąb drzewa, jest zawsze szybkie.
Dodajmy jeszcze kilka gałęzi drugiego i trzeciego poziomu do globala.
Set ^a("+7926X", "city") = "Moscow"
Set ^a("+7926X", "city", "street") = "Req Square"
Set ^a("+7926X", "age") = 25
Set ^a("+7916Y", "city") = "London"
Set ^a("+7916Y", "city", "street") = "Baker Street"
Set ^a("+7916Y", "age") = 36
Oczywistym jest, że w oparciu o globale można budować drzewa wielopoziomowe. Co więcej, dostęp do dowolnego węzła jest niemal natychmiastowy dzięki automatycznemu indeksowaniu podczas wstawiania. Na każdym poziomie drzewa wszystkie gałęzie są sortowane według kluczy.
Jak widać, informacje można przechowywać zarówno w kluczu, jak i wartości. Całkowita długość klucza (suma długości wszystkich indeksów) może osiągnąć Bajtów 511i wartości 3.6 MB dla pamięci podręcznej. Liczba poziomów w drzewie (liczba wymiarów) wynosi 31.
Kolejny ciekawy punkt. Możesz zbudować drzewo bez określania wartości węzłów wyższych poziomów.
Set ^b("a", "b", "c", "d") = 1
Set ^b("a", "b", "c", "e") = 2
Set ^b("a", "b", "f", "g") = 3
Puste okręgi to węzły, którym nie przypisano żadnej wartości.
Aby lepiej zrozumieć globale, porównajmy je z innymi drzewami: drzewami ogrodowymi i drzewami nazw systemów plików.
Porównajmy drzewa na globalach z najbardziej znanymi nam strukturami hierarchicznymi: ze zwykłymi drzewami rosnącymi w ogrodach i na polach, a także z systemami plików.
Jak widzimy w przypadku drzew ogrodowych, liście i owoce znajdują się tylko na końcach gałęzi.
Systemy plików - informacje przechowywane są jedynie na końcach gałęzi, które są pełnymi kwalifikowanymi nazwami plików.
A oto globalna struktura danych.
Różnice:
Węzły wewnętrzne: informacje globalne mogą być przechowywane w każdym węźle, a nie tylko na końcach gałęzi.
Węzły zewnętrzne: Globalny musi mieć określone wartości na końcach gałęzi, podczas gdy FS i drzewa ogrodowe nie.
Jeśli chodzi o węzły wewnętrzne, możemy powiedzieć, że struktura globalna jest nadzbiorem struktury drzew nazw w systemach plików i drzewach ogrodowych. Te. bardziej elastyczne.
Ogólnie rzecz biorąc, globalny jest uporządkowane drzewo z możliwością przechowywania danych w każdym węźle.
Aby lepiej zrozumieć działanie globali, wyobraź sobie, co by się stało, gdyby twórcy systemów plików zastosowali podejście podobne do globali do przechowywania informacji?
Usunięcie pojedynczego pliku w katalogu spowoduje automatyczne usunięcie katalogu, a także wszystkich nadrzędnych katalogów zawierających tylko jeden właśnie usunięty katalog.
Katalogi nie byłyby potrzebne. Byłyby po prostu pliki z podtekstami i pliki bez podtekstów. W porównaniu do zwykłego drzewa, każda gałąź stałaby się owocem.
Rzeczy takie jak pliki README.txt mogą nie być potrzebne. Wszystko, co należało powiedzieć o zawartości katalogu, można zapisać w samym pliku katalogu. W przestrzeni ścieżek nazwa pliku jest nie do odróżnienia od nazwy katalogu, więc można było obejść się tylko z plikami.
Szybkość usuwania katalogów z zagnieżdżonymi podkatalogami i plikami wzrosłaby dramatycznie. Wiele razy na Habré pojawiały się artykuły o tym, jak długo i trudno jest usunąć miliony małych plików (1, 2). Jeśli jednak utworzysz system pseudoplików na skalę globalną, zajmie to sekundy lub ich ułamki. Kiedy testowałem usuwanie poddrzew na komputerze domowym, usunięto 1–96 milionów węzłów z dwuwarstwowego drzewa na dysku twardym (nie dysku SSD) w ciągu 341 sekundy. Co więcej, mówimy o usunięciu części drzewa, a nie tylko całego pliku z globalami.
Usuwanie poddrzew to kolejna mocna strona globali. Nie potrzebujesz do tego rekurencji. Dzieje się to niewiarygodnie szybko.
W naszym drzewie można to zrobić za pomocą polecenia Zabić.
Kill ^a("+7926X")
Aby lepiej zrozumieć, jakie działania są dla nas dostępne w przypadku globali, udostępnię krótką tabelę.
Podstawowe polecenia i funkcje do pracy z globalami w COS
Zestaw
Ustawianie gałęzi dla węzła (jeśli jeszcze nie zdefiniowano) i wartości węzłów