algorithm - 数据结构中的卫星信息是什么？

Question

摘自 Thomas Cormen 的算法导论:

“为了简单起见，我们假设，就像我们对二叉搜索树和红黑树所做的那样 树，任何与 key 相关的“卫星信息”都存储在同一个树中 节点作为键。实际上，每个键实际上可能只存储一个指向 另一个包含该 key 的卫星信息的磁盘页面。伪代码 在本章中隐含地假设与卫星相关的信息 key ，或指向此类卫星信息的指针，每当 键从一个节点移动到另一个节点。"

因此，我一直在尝试通过 Google 搜索卫星信息一词的含义，但找不到任何内容(有关 NASA 的内容已涵盖)。我仅根据文本的理解是“卫星信息”是指向实际键值所在位置的地址，如指针？我是对的还是误解了？

编辑:它与 key 有何不同？

Answer 1

卫星数据指的是您要存储在数据结构中的任何“有效负载”数据，它不是数据结构结构的一部分。它可以是任何你想要的。它可以是单个值、大量值的集合或指向保存该值的其他某个位置的指针。

例如，这是一个单向链表的列表节点，其卫星数据是一个整数:

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

换句话说，任何给定数据结构的全部值(value)都在于它包含的数据，即您书中术语中的卫星数据。数据结构将另外使用结构数据(如示例中的 next 指针)来执行定义它的算法，但从用户的角度来看，这些本质上是“开销”。

对于关联容器，“键”值起着双重作用:一方面是用户数据，另一方面也是容器结构的一部分。然而，一棵树可以配备额外的卫星数据，在这种情况下，它就变成了从关键数据到卫星数据的“ map ”。

在一个极端情况下，您有一个固定大小的数组，它没有开销，只有有效负载数据，而在另一个极端情况下，您有复杂的结构，如多索引、尝试、Judy 数组或无锁容器维护相对大量的结构数据。