哪些信息浪费在树的2-3个节点上？

Question

假设我有一个2-3树的节点类。每个节点可以存储2个数据元素，最多3个子节点。如果树中有一个节点，则存储1个数据元素，并且没有子节点。浪费在这个节点上的存储是什么？

Answer 1

这取决于您想要存储在树中的数据。假设您希望在树中存储对象、字符串或其他复杂数据类型。然后，您有两个指针(一个是永久对象)，三个是子指针。即使指针未初始化/指向null，节点仍需要空间。所以你的内存使用量是1/5。

示例：

图像中有以下类：

class Node {
    Object data1 = new Data();
    Object data2 = null;
    Node child1 = null;
    Node child2 = null;
    Node child3 = null;
}

创建该类对象时，VM需要为新对象保留内存。所以VM知道这个类中有5个不同的属性。每个属性都是一个对象，因此需要为5个指针留出空间。指针实际上指向的位置并不重要，因为它只是指针中的值。null指针只是指向无效地址的指针(例如0x00000000，但这取决于操作系统)。

所以存储data1和data2的内存是完全相同的。当然，data1指向一个有效的地址，还有另一个对象也需要内存。

那么，当创建对象时，到底会发生什么呢？让我们假设对象是在堆栈上创建的(堆上的对象应该是完全相同的)。VM在堆栈上“推送”每个属性。我不确定确切的顺序，但我会假设它是data1, data2, child1,...，自上而下。在这种情况下，保留5次32位或64位(取决于您的架构)。我就叫他们单词，我记不起正确的表达方式了。每个单词的值现在是一个随机值(存储在这些内存单元中的值)。接下来，为每个单词添加正确的值，因此对于null，0x00000000被写入内存单元格中。对于data1，可以搜索一个空闲地址，然后在那里重新开始。

我希望我想说的是清楚的。