トーマス・コーメンによるアルゴリズム入門から引用：
単純にするために、二分探索木や赤黒木と同様に、キーに関連付けられた「サテライト情報」はキーと同じノードに格納されると仮定します。実際には、実際には、各キーは、そのキーのサテライト情報を含む別のディスク ページへのポインタにすぎません. この章の疑似コードは、キーに関連付けられたサテライト情報、またはそのようなサテライト情報へのポインタが、キーが移動するたびにキーと一緒に移動することを暗黙的に想定しています.ノードからノードへ。」
それで、衛星情報という用語の意味をグーグルで検索しようとしましたが、見つかりませんでした（NASAに関するものでカバーされています）。テキストだけに基づく私の理解は、「衛星情報」はポインターのような実際のキー値の場所へのアドレスですか? 私は正しいですか、それとも誤解しましたか？
編集: キーと何が違うのですか?
サテライト データとは、データ構造に格納する必要があり、データ構造の構造の一部ではない「ペイロード」データを指します。それはあなたが望むものなら何でもかまいません。単一の値、値の大規模なコレクション、または値を保持する他の場所へのポインターのいずれかです。
たとえば、サテライト データが単一の整数である単一リンク リストのリスト ノードは次のとおりです。
struct node
{
node * next;
int satellite;
};
言い換えれば、任意のデータ構造の全体的な価値は、そこに含まれるデータにあり、これは本書の用語ではサテライト データです。データ構造は、それを定義するアルゴリズムを実行するために構造データ (例のnextポインターなど) を追加で消費しますが、それらはユーザーの観点からは本質的に「オーバーヘッド」です。
連想コンテナの場合、「キー」値は 2 つの役割を果たします。一方ではユーザー データですが、他方ではコンテナの構造の一部でもあります。ただし、ツリーには追加の衛星データを装備することができます。その場合、ツリーはキー データから衛星データへの「マップ」になります。
一方の極端には、オーバーヘッドがなくペイロード データのみの固定サイズの配列があり、他方の極端には、比較的大量の構造データを保持するマルチインデックス、トライ、Judy 配列、またはロックフリー コンテナーなどの複雑な構造があります。