Plik siatki

W informatyce plik siatki lub siatka kubełkowa to metoda dostępu do punktu , która dzieli przestrzeń na nieokresową siatkę , w której jedna lub więcej komórek siatki odnosi się do małego zestawu punktów. Pliki siatki ( symetryczna struktura danych ) zapewniają wydajną metodę przechowywania tych indeksów na dysku w celu wykonywania złożonych wyszukiwań danych.

Zapewnia siatkę o n wymiarach, gdzie n reprezentuje liczbę kluczy, których można użyć do odniesienia do pojedynczego punktu.

Pliki Grid same w sobie nie zawierają żadnych danych, ale zamiast tego zawierają odniesienia do właściwego zasobnika .

Używa

Plik siatki jest zwykle używany w przypadkach, gdy do jednej wartości można odwoływać się za pomocą wielu kluczy.

Plik siatki zaczął być używany, ponieważ „tradycyjne struktury plików, które zapewniają wielokluczowy dostęp do rekordów, na przykład odwrócone pliki, są rozszerzeniami struktur plików pierwotnie zaprojektowanych do dostępu jednym kluczem. Wykazują różne braki, w szczególności w przypadku wieloklawiszowego dostępu do bardzo dynamicznych plików ”.

W tradycyjnej jednowymiarowej strukturze danych (np. hash ) wyszukiwanie według jednego kryterium jest zwykle bardzo proste, ale wyszukiwanie drugiego kryterium może być znacznie bardziej złożone.

Pliki grid reprezentują specjalny rodzaj haszowania, w którym tradycyjny hash jest zastępowany przez katalog grid.

Przykłady

Baza danych spisu ludności

Rozważmy bazę danych zawierającą dane ze spisu powszechnego. Pojedynczy rekord reprezentuje jedno gospodarstwo domowe, a wszystkie rekordy są pogrupowane w zasobniki. Wszystkie rekordy w zasobniku mogą być indeksowane według miasta (które jest takie samo dla wszystkich rekordów w zasobniku) oraz ulic w tym mieście, których nazwy zaczynają się na tę samą literę.

Plik siatki może posłużyć do stworzenia wydajnego indeksu dla tej struktury, w której rekordy występują w grupach po 26, z których każdy odnosi się do nazw ulic w mieście zaczynających się na jedną z liter alfabetu. Ta struktura może być traktowana jako tablica , tabela lub siatka z dwoma wymiarami, które będziemy nazywać osiami x i y.

Można uznać, że oś x to miasto, a oś y to każda z liter alfabetu lub alternatywnie pierwsza litera każdej ulicy.

Każdy rekord w tej strukturze jest nazywany komórką. Każda komórka będzie zawierała wskaźnik do odpowiedniego zasobnika w bazie danych, w którym przechowywane są rzeczywiste dane. W celu zapisania nazwy miasta może być wymagana dodatkowa komórka lub nagłówek rekordu. Inne zgrupowane z nim komórki będą musiały zawierać tylko wskaźnik do odpowiedniego segmentu, ponieważ pierwsza komórka odpowiada nazwom ulic zaczynającym się na „A”, druga na „B” i tak dalej.

Bazę danych można dodatkowo rozszerzyć, aby zawierała pole kontynentu w celu rozszerzenia spisu na inne kontynenty. Spowodowałoby to, że rekordy w tym samym zasobniku odpowiadały gospodarstwom domowym na ulicy rozpoczynającej się na tę samą literę, w tym samym mieście, na tym samym kontynencie.

Komórki w pliku siatki składałyby się wówczas z nagłówka miasta i sześciu (po jednej na każdy kontynent, z wyłączeniem Antarktydy ) grup 26 komórek odnoszących się do ulic o tej samej literze początkowej, w tym samym mieście, na tym samym kontynencie i można teraz traktować jako tablicę trójwymiarową.

Zalety

Ponieważ pojedynczy wpis w pliku siatki zawiera wskaźniki do wszystkich rekordów indeksowanych według określonych kluczy:

  • Nie są wymagane żadne specjalne obliczenia
  • Pobierane są tylko właściwe rekordy
  • Może być również używany do zapytań z jednym kluczem wyszukiwania
  • Łatwe rozszerzenie na zapytania dotyczące n kluczy wyszukiwania
  • Znaczna poprawa czasu przetwarzania zapytań z wieloma kluczami
  • Ma górną granicę dostępu do dwóch dysków dla dostępu do danych.

Niedogodności

Jednak ze względu na charakter pliku grid, który daje mu zalety, istnieją również pewne wady:

  • Narzuca przestrzeń nad głową
  • Narzut na wydajność przy wstawianiu i usuwaniu

Powiązane struktury danych

  • plik siatki wielowarstwowej
  • pliki bliźniaczych siatek
  • plik BANG

Zobacz też

Pobrano z „ https://en.wikipedia.org/w/index.php?title=Grid_file&oldid=1026932934 ”