13
$\begingroup$

I'm a bit confused on what exactly the meaning of a 'key' is in computer science. I understand key-value pairs, primary keys, etc... But I can't find a definition of what the term 'key' means by itself.

As far as I can tell it just means a piece of data. In CLRS, data associated with tree nodes are referred to as 'keys'. Data to search a hash table is called a 'key'. Is this what a 'key' is?

$\endgroup$
  • 18
    $\begingroup$ There is not one specific technical definition. The use of the word is usually inspired by its normal, English definition, e.g. merriam-webster.com/dictionary/key Or rather I should say "definitions". In general, your expectation should be that there isn't a unifying technical definition for common English words that are used in multiple contexts even within a single field of study. $\endgroup$ – Derek Elkins Apr 23 at 19:52
  • 4
    $\begingroup$ It could even be one of those things on your keyboard :-) $\endgroup$ – jamesqf Apr 24 at 3:50
  • $\begingroup$ It's actually the same in normal English - key figure = the primary person in the story, key piece of evidence = the primary evidence that lead to solving a case, key = the primary mechanism to unlock a door etc. It means "the main way to access something" in English. It's not specific to CS $\endgroup$ – slebetman Apr 24 at 13:24
  • $\begingroup$ There are also "keys" in the cryptographic sense, which I would consider to be different from the data lookup examples you have mentioned. $\endgroup$ – 200_success Apr 24 at 18:19
  • $\begingroup$ @slebetman While 'key' indeed has many uses in the English language, there are many usages that are have a precise definition that is very much specific to (a subfield of) CS. $\endgroup$ – Discrete lizard Apr 25 at 7:29
29
$\begingroup$

In the most general sense, a key is a piece of information required to retrieve some data. However, this meaning plays out differently depending on exactly what situation you're dealing with.

In the contexts you mention, a key is a unique identifier for the complete data used to retrieve it from some location in the structure. Each key is associated with only one item, so it can be used to find a particular set of data. The data structure will usually be organized in such a way that finding the key is much more efficient than a linear search through all of the data. Sometimes the key is actually part of the data and stored along with it (like primary keys in the database); other times, it is segregated from the data itself (like in a hash map). The data structure will also often perform extra processing on the key (and only the key) to support its efficient searching algorithm (such as in a hash map, the key is converted into a hash code, or a database will index the primary keys using a B-tree).

In cryptography, a key is used in a sense more akin to physical keys used on locks. They're pieces of data required to obtain the original from the encrypted data (to "unlock" the data, so to speak).

$\endgroup$
  • 3
    $\begingroup$ To prevent possible confusion: in the book CLRS, keys are usually not considered to be unique, as they don't have to be for many data structures. $\endgroup$ – Discrete lizard Apr 23 at 19:52
  • $\begingroup$ Then, in general, a key is data to navigate a data structure? That makes sense to me, like a physical key is used to retrieve something from a locked box. $\endgroup$ – TheMax Apr 23 at 20:57
  • $\begingroup$ @TheMax I would not say that definition suits cryptography, as there's no "navigation" to be done. It does suit your list of examples, but I don't see it as a parallel to a physical key in those cases. $\endgroup$ – jpmc26 Apr 23 at 21:08
  • $\begingroup$ @jpmc26 that description is spot on, consider bitwise XOR of a key against data, $\endgroup$ – mckenzm Apr 24 at 6:37
  • $\begingroup$ On scales we see today, hashes used for synthetic keys may indeed not be unique, and may need tie breakers or compounding. $\endgroup$ – mckenzm Apr 24 at 6:39
12
$\begingroup$

A key in the context of data structures (such as in the book CLRS) is a value (often an integer) that is used to identify a certain component of a data-structure. Often, keys determine how the underlying data is stored or manipulated. For example, in binary search trees we have that for every node, the key of that node is larger than the keys in the left sub-tree and smaller than those in the right subtree. This property makes it easier to search for a given key (or determine there is no node with such a key).

In practice, our 'actual' data is often not a key, but something larger and more relevant that a single number. This data is called satellite data and can be mostly ignored when dealing with manipulations on data structures, as long as the satellite data moves whenever the key gets moved (otherwise, you lose track of your data).


The concept of a key is similar in the context of databases, but there it is often required that a key is unique. A primary key has to be unique, for example. This requirement is often nessecary in the context of data-structures, but is sometimes made for simplicity.

In cryptography, a key usually refers to an (often secret, but not always!) parameter that is needed to encrypt or decrypt with a given en- or decryption algorithm. The keys used to encrypt and decrypt have to be 'related' (in symmetric cryptography, the need to be the same) for the process to encryption or decryption to be successful.

$\endgroup$
  • $\begingroup$ What is the difference between satellite data and keys then? From what I understand, satellite data is data organized by the data structure that is not part of the actual structure. So can I say a keys and satellite data are both data in the structure, but keys are part of the structure and satellite data is not? $\endgroup$ – TheMax Apr 23 at 19:18
  • 1
    $\begingroup$ @TheMax In a way, yes. The precise content of the satellite data is irrelevant for the operations on the data-structure (but likely relevant for the application using the data structure). This decoupling of key and data makes it easier for to design efficient data-structures. $\endgroup$ – Discrete lizard Apr 23 at 19:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.