Co to jest „klucz” w informatyce?

Jestem trochę zdezorientowany, co dokładnie oznacza „klucz” w informatyce. Rozumiem pary klucz-wartość, klucze podstawowe itp. Ale nie mogę znaleźć definicji tego, co oznacza pojęcie „klucz” samo w sobie.

O ile mogę to stwierdzić, oznacza to po prostu kawałek danych. W CLRS dane powiązane z węzłami drzewa są nazywane „kluczami”. Dane do przeszukiwania tabeli skrótów nazywane są „kluczem”. Czy to jest „klucz”?

terminology

— TheMax
źródło

Nie ma jednej konkretnej definicji technicznej. Użycie tego słowa jest zwykle inspirowane jego normalną angielską definicją, np. Merriam-webster.com/dictionary/key A raczej powinienem powiedzieć „definicja s ”. Ogólnie rzecz biorąc, należy oczekiwać, że nie będzie jednolitej definicji technicznej dla popularnych angielskich słów, które są używane w wielu kontekstach, nawet w ramach jednego kierunku studiów.

— Derek Elkins opuścił

Może to być nawet jedna z tych rzeczy na twojej klawiaturze :-)

— jamesqf 24.0419

Tak samo jest w normalnym języku angielskim - kluczowa postać = główna osoba w historii, kluczowy dowód = główny dowód, który prowadzi do rozwiązania sprawy, klucz = podstawowy mechanizm odblokowania drzwi itp. Oznacza to „główną drogę uzyskać dostęp do czegoś ”po angielsku. To nie jest specyficzne dla CS

— slebetman

Istnieją również „klucze” w sensie kryptograficznym, które uważam za różne od wspomnianych przykładów wyszukiwania danych.

— 200_success 24.04.2019

@slebetman Chociaż „klucz” rzeczywiście ma wiele zastosowań w języku angielskim, istnieje wiele zastosowań, które mają precyzyjną definicję bardzo specyficzną dla (podpola) CS.

— Dyskretna jaszczurka

Odpowiedzi:

W najogólniejszym znaczeniu klucz to pewna informacja potrzebna do odzyskania niektórych danych. Jednak to znaczenie działa inaczej w zależności od konkretnej sytuacji, z którą masz do czynienia.

W wspomnianych kontekstach klucz jest unikalnym identyfikatorem kompletnych danych używanych do pobrania go z pewnego miejsca w strukturze. Każdy klucz jest powiązany tylko z jednym elementem, więc można go użyć do znalezienia określonego zestawu danych. Struktura danych jest zwykle zorganizowana w taki sposób, że znalezienie klucza jest znacznie bardziej wydajne niż liniowe przeszukiwanie wszystkich danych. Czasami klucz jest faktycznie częścią danych i jest przechowywany wraz z nim (jak klucze podstawowe w bazie danych); innym razem jest on oddzielony od samych danych (jak na mapie hash). Struktura danych często wykonuje dodatkowe przetwarzanie klucza (i tylko klucza) w celu obsługi wydajnego algorytmu wyszukiwania (np. W mapie skrótu, klucz jest konwertowany na kod skrótu lub baza danych indeksuje klucze podstawowe za pomocą B-drzewo).

W kryptografii klucz jest używany w sensie bardziej zbliżonym do kluczy fizycznych używanych w zamkach. Są to fragmenty danych wymagane do uzyskania oryginału z zaszyfrowanych danych (aby „odblokować” dane, że tak powiem).

— jpmc26
źródło

Aby zapobiec możliwym nieporozumieniom: w książce CLRS klucze zwykle nie są uważane za unikalne, ponieważ nie muszą tak być w przypadku wielu struktur danych.

— Dyskretna jaszczurka

Zatem generalnie kluczem są dane do nawigacji w strukturze danych? Ma to dla mnie sens, tak jak fizyczny klucz służy do pobierania czegoś z zamkniętego pudełka.

— TheMax

@ TheMax Nie powiedziałbym, że definicja odpowiada kryptografii, ponieważ nie ma potrzeby „nawigacji”. Odpowiada twojej liście przykładów, ale w tych przypadkach nie widzę go jako równoległego do klucza fizycznego.

— jpmc26

@ jpmc26, ten opis jest na miejscu, rozważ bitową XOR klucza względem danych,

— mckenzm 24.04.19

W skalach, które widzimy dzisiaj, skróty używane do kluczy syntetycznych mogą nie być unikalne i mogą wymagać przerywników remisów lub łączenia.

— mckenzm

Klucz w kontekście struktury danych (takie jak w CLR book) jest wartość (często oznacza liczbę całkowitą), który jest używany do identyfikowania określonego elementu o strukturze danych. Często klucze określają sposób przechowywania lub manipulowania danymi bazowymi. Na przykład w drzewach wyszukiwania binarnego mamy, że dla każdego węzła klucz tego węzła jest większy niż klucze w lewym poddrzewie i mniejszy niż klucze w prawym poddrzewie. Ta właściwość ułatwia wyszukiwanie danego klucza (lub stwierdzenie, że nie ma węzła z takim kluczem).

W praktyce nasze „rzeczywiste” dane często nie są kluczem, ale czymś większym i bardziej odpowiednim niż pojedyncza liczba. Dane te nazywane są danymi satelitarnymi i można je w większości zignorować podczas manipulacji strukturami danych, o ile dane satelitarne poruszają się za każdym razem, gdy klucz zostanie przesunięty (w przeciwnym razie tracisz dane).

Pojęcie klucza jest podobne w kontekście baz danych, ale tam często wymagane jest, aby klucz był unikalny . Klucz podstawowy musi być na przykład unikalny. Wymóg ten jest często niepotrzebny w kontekście struktur danych, ale czasami jest wprowadzany dla uproszczenia.

W kryptografii klucz zwykle odnosi się do (często tajnego, ale nie zawsze!) Parametru, który jest potrzebny do szyfrowania lub deszyfrowania za pomocą danego algorytmu szyfrowania lub deszyfrowania. Klucze używane do szyfrowania i deszyfrowania muszą być „powiązane” (w kryptografii symetrycznej potrzeba być taka sama), aby proces szyfrowania lub deszyfrowania zakończył się powodzeniem.

— Dyskretna jaszczurka
źródło

Jaka jest zatem różnica między danymi satelitarnymi a kluczami? Z tego, co rozumiem, dane satelitarne to dane uporządkowane według struktury danych, która nie jest częścią faktycznej struktury. Czy mogę więc powiedzieć, że klucze i dane satelitarne są danymi w strukturze, ale klucze są częścią struktury, a dane satelitarne nie?

— TheMax

@ TheMax W pewnym sensie tak. Dokładna zawartość danych satelitarnych nie ma znaczenia dla operacji na strukturze danych (ale prawdopodobnie jest istotna dla aplikacji wykorzystującej strukturę danych). To oddzielenie klucza i danych ułatwia projektowanie wydajnych struktur danych.

— Dyskretna jaszczurka