让我将问题放在首位：考虑到我将进一步描述的情况和要求，哪些数据结构将有意义/帮助实现非功能性要求？
我试图查找几个结构，但到目前为止还不是很成功，这可能是由于我缺少一些术语。
，由于我们将在Java中实现任何答案，都应考虑到这一点（例如，没有指针魔术，假设8字节参考等）。
情况
我们有一些大量的值，这些值通过4维键映射（我们称这些尺寸为a，b，c和d）。每个维度的大小都不同，因此我们假设以下内容：
- A：100
- b：5
- C：10000
- D：2
这意味着完全填充的结构将包含1000万个元素。不考虑其尺寸，仅持有参考的空间就像80兆字节一样，因此被认为是用于记忆消耗的下限。
我们可以进一步假设该结构不会完全填充，但要密集。
要求
由于我们经常建立和查询该结构，因此我们有以下要求：
- 构建结构应快速
- 对单个元素和范围的查询（例如[A1-A5，B3，ANY C，D0]）应该是有效的
- 不需要快速删除元素（不会经常发生）
- 内存足迹应低
我们已经考虑了
kd-Trees
建造这样的树需要一些时间，因为它可以变得很深，我们必须接受较慢的查询或采取重新平衡措施。在附加的情况下，内存足迹很高，因为我们需要在每个节点中保存完整的键（虽然有一些方法可以减少它）。
嵌套地图/地图树
使用嵌套地图，我们只能存储每个维度的密钥，以及对下一个维度图或值的引用 - 从这些地图中有效地构建树。为了支持范围的查询，我们将在横穿树时保留可能的钥匙集合并访问这些键。
构造和查询的速度比KD-Trees快得多，但是记忆足迹要高得多（如预期）。
一个大型地图
一种替代方法是保留单个可用密钥的集合并改用单个大型地图。
构造和查询也很快，但是由于每个地图节点都更大（它们需要保存键的所有维度），内存消耗甚至更高。
）。目前我们在想什么
构建尺寸键的插入订单索引映射，即我们将每个传入的钥匙映射到新的整数索引。删除）。
使用这些索引，我们将访问n维数组的树（当然是扁平为1-D阵列） - 又称n-ary树。那棵树会根据需要生长，即，如果我们需要一个新数组，那么就不会创建较大的数组，而是复制我们只创建新块的所有数据。任何需要的非叶子节点都会根据需要创建，在需要时替换根。
让我说明，用2个维度A和B的示例进行。我们将为每个维度分配2个元素，从而产生2x2矩阵（长度为4）。
添加第一个元素A1/B1我们会得到这样的东西：
[A1/B1,null,null,null]
现在我们添加元素A2/B2：
[A1/B1,null,A2/B2,null]
现在我们添加元素A3/B3。由于我们无法将新元素映射到现有数组，我们将创建一个新元素以及一个常见的根源：
[x,null,x,null]
/
[A1/B1,null,A2/B2,null] [A3/B3,null,null,null]
密度填充矩阵的内存消耗应相当较低，具体取决于每个数组的大小（在一个数组中，每个维度有4个维度和4个值，我们将具有长度为256的阵列，因此获得2--的最大树深度。4在大多数情况下）。
这有意义吗？
如果结构将"非常密集"，那么我认为假设它将已满是有意义的。这简化了很多事情。而且，这并不是说您要使用密集填充的矩阵的稀疏矩阵表示节省很多（或任何东西）。
我将首先尝试最简单的结构。它可能不是最有效的记忆效率，但应该是合理的，并且很容易使用。
首先，简单的10,000,000参考。那就是（请原谅C＃，因为我不是真正的Java程序员）：
MyStructure[] theArray = new MyStructure[](10000000);
正如您所说，这将消耗80兆字节。
下一
Dictionary<KeyAType, int> ADict;
Dictionary<KeyBType, int> BDict;
Dictionary<KeyCType, int> CDict;
Dictionary<KeyDType, int> DDict;
当您在{a，b，c，d}上添加一个元素时，您查找字典中的各个键以获取其索引（或在该密钥不存在时添加新索引），然后执行数学将索引计算到数组中。我认为数学是：
DIndex + 2*(CIndex + 10000*(BIndex + 5*AIndex));
在.net中，字典开销大约是每个键24个字节。但是您只有11,007个键，因此词典将消耗250千键。
这应该很快直接查询，并且范围查询应该像单个查找一样快，然后进行一些数组操纵。
我尚不清楚的一件事是，如果您想要一个键，则在每个构建时都能解决相同的索引。也就是说，如果" foo"映射到一个构建中索引1，它将始终映射到索引1？
如果是这样，您可能应该静态地构建字典。我想这取决于您的范围查询是否总是以相同的关键顺序期望。
无论如何，这是一个非常简单且非常有效的数据结构。如果您可以负担81兆字节作为结构的最大尺寸（减去实际数据），那么这似乎是一个不错的起点。您可能会在几个小时内工作。
充其量是您所要做的。而且，如果您最终必须替换它，至少您可以使用一个工作实现，可以用来验证您提出的任何新结构的正确性。
还有其他多维树通常比KD-Trees更好：四分之一，r*树（如R-Tree，但更新的速度）或pH-Tree。pH-Tree就像Quadtree一样，但更有效的空间，尺寸更好，深度限制了值的最大值，即最大" 10000"需要14位，因此深度不会超过14位。p>所有树的Java实现都可以在我的存储库上找到（Quadtree可能有点货）或这里。
编辑以下优化可能被忽略。当然，所描述的查询将进行完整的扫描，但这可能并不像听起来那样糟糕，因为它平均而言会返回整棵树的33％-50％。
可能的优化（未测试，但可能适用于pH-Tree）：
范围查询的一个问题是您的尺寸的选择性不同，这可能会导致树的完整扫描。例如，当查询[0..100] [0..5] [0..10000] [1..1]时，即仅约束最后一个维度（最少选择性）。
为了避免这种情况，尤其是对于pH-树，我会尝试将您的值乘以固定常数。例如，将a，b乘以2000，c乘以1和d乘以5000。这允许所有值范围从0到10000，当仅约束以低选择性约束尺寸时（第二或第四）。