What is satellite information in data structures?

Question

Adapted from an introduction to Thomas Cormen's algorithms:

“To keep things simple, suppose, as for binary search trees and red-black trees, that any“ satellite information ”associated with a key is stored in the same node as a key. In practice, you could only store with each key a pointer to another page of the disk containing satellite information for this key.The pseudo-code in this chapter assumes that satellite information associated with a key or a pointer to such satellite information moves with the key whenever the key is moved from node to node. "

So, I'm trying to use the meaning of the word "satellite" for Google, but I can not find it (as for NASA). My understanding, based only on the text, is that "satellite information" is the address for the location of the actual key value, such as a pointer? Did I get it wrong?

EDIT: what sets it apart from the key?

Answer 1

Satellite data refers to any “payload” that you want to keep in your data structure and which is not part of the data structure structure. That could be all you want. It can be one value, a large set of values, or a pointer to another location that contains the value.

For example, here is the node list for a singly linked list, the satellite data of which is a single integer:

struct node { node * next; int satellite; }; 

In other words, the whole value of any given data structure lies in the data that it contains, which is satellite data in your book terminology. The data structure will additionally consume structural data (for example, the next pointer in the example) to execute the algorithms that define it, but this is essentially "overhead" from the user's point of view.

For associative containers, the key value has a double role: on the one hand, this is user data, but on the other hand, it is also part of the container structure. However, the tree can be equipped with additional satellite data, in which case it becomes a “map” from the key data to the satellite data.

On the one hand, you have a fixed-size array that has no overhead and only useful data, and on the other hand you have complex structures, such as multiindexes, try, Judy arrays or non-blocking containers that support a relatively large amount of structural data.