什么是数据结构的卫星信息？ [英] What is satellite information in data structures?

问题描述

摘自算法导论托马斯Cormen：

Taken from Introduction to Algorithms by Thomas Cormen:

的为了简单起见，我们假设，因为我们有二叉搜索树和红黑 树木，任何的卫星信息与键关联被存储在相同 节点的关键。在实践中，人们可能实际上与每个键只是一个指向存储 另一个磁盘页面，其中包含卫星信息的关键。伪code 本章中隐含的假设是与相关的卫星信息 键，或指针以这样的卫星信息，行驶过程中，关键只要 关键是从节点移到节点。的

"To keep things simple, we assume, as we have for binary search trees and red-black trees, that any "satellite information" associated with a key is stored in the same node as the key. In practice, one might actually store with each key just a pointer to another disk page containing the satellite information for that key. The pseudocode in this chapter implicitly assumes that the satellite information associated with a key, or the pointer to such satellite information, travels with the key whenever the key is moved from node to node."

所以，我一直在试图谷歌的长期卫星信息的含义，但我找不到任何（涵盖东西约NASA）。我的理解的基础上单独的文字是，卫星信息是一个地址，像一个指针的实际键值的位置？我是正确还是我误会了？

So I've been trying to Google the meaning of the term satellite information but I can't find any (covered by things about NASA). My understanding based on the text alone is that "satellite information" is an address to the location of the actual key value like a pointer? Am I correct or did I misunderstand it?

编辑：？是什么使得它从一个关键的不同

What makes it different from a key?

推荐答案

卫星数据指的是要存储在数据结构和它的任何有效载荷数据的没有的一部分的结构的数据结构。它可以是任何你想要的。它可以是一个单一的值，大的值的集合中，或一个指针到持有值某些其他位置。

Satellite data refers to any "payload" data which you want to store in your data structure and which is not part of the structure of the data structure. It can be anything you want. It can be a single value, a large collection of values, or a pointer to some other location that holds the value.

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

For example, here's a list node for a singly linked list whose satellite data 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 which it contains, which is the satellite data in your book's terminology. The data structure will additionally consume structural data (like the next pointer in the example) to perform the algorithms which define it, but those are essentially "overhead" from the user's perspective.

有关关联容器时，键值执行双重作用：一方面它是用户数据，但另一方面它也与容器的结构的一部分。然而，树可以配备额外的卫星数据，在这种情况下，它变成一个从密钥数据的地图卫星数据

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

在一个极端，你有一个固定大小的阵列，其具有的没有的开销，只有有效载荷数据，而在另一个极端，你有复杂的结构，如multiindexes，尝试，朱迪阵列或lockfree容器，保持同等大量的结构性数据。

At one extreme you have a fixed-size array which has no overhead and only payload data, and on the other extreme you have complicated structures like multiindexes, tries, Judy arrays, or lockfree containers which maintain a comparably large amount of structural data.

这篇关于什么是数据结构的卫星信息？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！