在Java中计算B树的内存使用情况

Question

我已经实现了一个简单的B-树，它将长整型映射为整数。现在，我想使用以下方法（仅适用于32位JVM）估计它的内存使用情况:

class BTreeEntry {

    int entrySize;
    long keys[];
    int values[];
    BTreeEntry children[];
    boolean isLeaf;
    ...
    /** @return used bytes */
    long capacity() {
        long cap = keys.length * (8 + 4) + 3 * 12 + 4 + 1;
        if (!isLeaf) {
            cap += children.length * 4;
            for (int i = 0; i < children.length; i++) {
                if (children[i] != null)
                    cap += children[i].capacity();
            }
        }
        return cap;
    }
}
/** @return memory usage in MB */
public int memoryUsage() {
    return Math.round(rootEntry.capacity() / (1 << 20));
}

但是我尝试了700万条记录，而"memoryUsage"方法报告的值比-Xmx设置允许的值要高得多！例如，它显示1040(MB)，而我设置了-Xmx300！JVM是否能够优化内存布局，例如对于空数组或我的错误是什么？

更新1：好的，引入isLeaf布尔值可以大大减少内存使用量，但仍然不清楚为什么观察到的值比Xmx高。（您仍然可以通过将isLeaf == false用于所有构造函数来尝试此方法）

更新2：嗯，有些事情出了问题。当增加每个叶子的条目数时，人们会认为内存使用量会减少（当对两者进行紧凑处理时），因为较大的数组涉及更少的引用开销（并且btree的高度更小）。但是，如果我使用500而不是每个叶子100个条目，则"memoryUsage"方法报告了一个增加的值。

- Karussell

---

长容量中的3*12的起源是什么？ - Erik

长整型和整型的内存消耗值，你的数据来源是什么？ - PeterMmm

@Erik 3*12 -> 参考了这3个数组。 - Karussell

@PeterMmm 你是什么意思？ - Karussell

Answer 1

哦，麻烦了...一点新鲜空气就解决了这个问题 ;)

当一个条目已满时，它将被分割。在我原始的拆分方法checkSplitEntry中（我想避免浪费内存），我犯了一个很大的内存浪费错误：

// left child: just copy pointer and decrease size to index
BTreeEntry newLeftChild = this;
newLeftChild.entrySize = splitIndex;

这里的问题是旧的子指针仍然可以访问。因此，在我的memoryUsage方法中，我会将某些子项计算两次（特别是当我没有压缩时！）。因此，如果没有这个技巧，一切都应该很好，我的B-Tree甚至会更加内存高效，因为垃圾收集器可以发挥作用！

- Karussell