Indeksy i przechowywanie

20 pojęć w 12 podgrupach, z prostymi definicjami i źródłami.

Indeksy gestosc · 2

01indeks gęstyIndeks zawierający wpis dla każdej wartości klucza wyszukiwania występującej w pliku danych.
02indeks rzadkiIndeks zawierający wpisy tylko dla niektórych wartości klucza (np. po jednym na blok), wymagający przeszukania sekwencyjnego między wpisami.

01indeksPomocnicza struktura danych przyspieszająca wyszukiwanie wierszy po wartościach wybranych kolumn, kosztem dodatkowej przestrzeni i narzutu przy modyfikacjach.

01indeks bitmapowyIndeks reprezentujący występowanie każdej wartości kolumny jako wektor bitów po wierszach; wydajny dla kolumn o małej liczbie różnych wartości i zapytań logicznych.

01indeks pokrywającyindeks z dołączonymi kolumnami (covering index)Indeks zawierający wszystkie kolumny potrzebne do odpowiedzi na zapytanie, dzięki czemu można je obsłużyć bez sięgania do tabeli bazowej.
02indeks złożonyindeks wielokolumnowyIndeks zbudowany na uporządkowanej liście wielu kolumn, w którym efektywność zapytań zależy od kolejności kolumn w kluczu.

01indeks klastrującyindeks zgrupowany (clustered index)Indeks, którego porządek logiczny odpowiada fizycznemu rozmieszczeniu wierszy na nośniku, dzięki czemu rekordy o bliskich kluczach leżą obok siebie.
02indeks niezgrupowanyindeks nieklastrujący (unclustered index)Indeks, którego kolejność wpisów jest niezależna od fizycznego rozmieszczenia rekordów danych; wpisy wskazują na rozproszone lokalizacje wierszy.

01czynnik blokowaniaLiczba rekordów mieszczących się w pojedynczym bloku przechowywania, determinująca koszt dostępu wyrażony liczbą operacji wejścia-wyjścia.
02stertaplik sterty (heap file)Organizacja pliku, w której rekordy są przechowywane bez narzuconego porządku, w kolejności wstawiania, a wyszukiwanie wymaga skanu pełnego.
03strona danychblok (page/block)Najmniejsza jednostka odczytu i zapisu między dyskiem a pamięcią operacyjną, grupująca rekordy w blok o stałym rozmiarze.

01kolumnowa organizacjaprzechowywanie kolumnowe (columnar storage)Sposób fizycznego składowania, w którym wartości każdej kolumny zapisuje się ciągle obok siebie, sprzyjając skanom analitycznym i kompresji.
02wierszowa organizacjaprzechowywanie wierszowe (row store)Sposób fizycznego składowania, w którym wszystkie pola jednego rekordu zapisuje się razem, sprzyjając operacjom na pojedynczych wierszach.

01B-drzewoB+-drzewo (B+-tree) — wariant z danymi tylko w liściachZrównoważone drzewo wyszukiwań o wysokim współczynniku rozgałęzienia, w którym wszystkie liście są na tej samej głębokości; bazowa struktura indeksów dyskowych.

01haszowanie rozszerzalneextendible hashingDynamiczna technika haszowania powiększająca katalog kubełków przez podwajanie wraz ze wzrostem danych, bez przebudowy całej struktury.
02indeks haszującyIndeks odwzorowujący klucz przez funkcję mieszającą na kubełek, dający wyszukiwanie po równości w czasie blisko stałym, lecz bez wsparcia zapytań zakresowych.

01filtr BloomaProbabilistyczna struktura bitowa testująca przynależność elementu do zbioru; daje fałszywie pozytywne, lecz nigdy fałszywie negatywne odpowiedzi.

01drzewo LSMLSM (Log-Structured Merge-Tree)Struktura przechowywania zorientowana na zapis, buforująca zmiany w pamięci i okresowo scalająca je w niezmienne, posortowane pliki na dysku.
02kompakcjascalanie (compaction)Scalanie wielu posortowanych plików w strukturach LSM w mniejszą liczbę plików, usuwające nadpisane i skasowane wpisy oraz odzyskujące przestrzeń.

01bufor stronicmenedżer buforów (buffer pool)Obszar pamięci operacyjnej buforujący strony danych z dysku, zarządzany polityką wymiany w celu minimalizacji operacji wejścia-wyjścia.