0

我有一个关于使用 MapDB 的问题，尤其是关于查询子图的问题。我从https://github.com/jankotek/MapDB/blob/release-1.0/src/test/java/examples/TreeMap_Composite_Key.java的官方示例中获取代码片段。这个例子很容易理解。出于测试目的，我互换了“城镇”和“街道”的关键部分，并submap以同样的方式调整了调用。不幸的是，现在地图不受submap呼叫限制。而是返回整个地图（200 个条目）。以下是改编后的代码片段（在上面提到的示例之外）

// Initializing map
for (final String town : towns) {
  for (final String street : streets) {
    for (final int houseNum : houseNums) {
        final Fun.Tuple3<String, String, Integer> address = Fun.t3(street, town,
                houseNum);
        final int income = r.nextInt(50000);
        map.put(address, income);
    }
  }
}
...
final Map<Fun.Tuple3, Integer> housesInCong = map.subMap(
  Fun.t3(null, "Cong", null), Fun.t3(Fun.HI, "Cong", Fun.HI));

//housesInCong.size() == 200 (should be 40)
System.out.println("There are " + housesInCong.size()+ " houses in Cong");

有人可以向我解释为什么会发生这种情况以及如何避免这种情况吗？我的项目中有一个类似的用例。

在此先感谢和问候:)

4

1 回答 1

0

我最近在二维图块中索引地理对象时遇到了类似的问题。我不得不浏览 MapDB 源代码并做一些实验来了解发生了什么。

MapDB 正在存储您的对象，以便以自然顺序对它们（或它们的子范围）进行迭代。该顺序不是您在迭代值时可以更改的东西，它是在插入对象时考虑的东西。它会影响它们存储在（b-tree）中的结构的布局。

MapDB 包含的元组类具有字典顺序。也就是说，它们像字典中的单词一样被排序：比较它们的第一个元素以查看哪个元组大于另一个元组。如果两个第一个元素相等，我们通过移动到第二个元素来打破平局，然后是第三个。您也可以说它们的行为类似于位置数字系统，您要比较的所有数字都具有相同的位数。

例如，让我们看一下元组中的所有元素都是一位整数的情况。我们首先插入三个一位整数的所有可能组合。如果我们这样过滤：

map.subMap(Fun.t3(2, null, null), Fun.t3(4, Fun.HI, Fun.HI));

我们将遍历元组 (2,0,0), (2,0,1) (2,0,2) ... (3,9,9)。现在，就像在您的示例中一样，我们更改子图调用以使用这些边界元组：

map.subMap(Fun.t3(null, 2, null), Fun.t3(Fun.HI, 4, Fun.HI));

在这里，我们将遍历元组 (0,2,0), (0,2,1) (0,2,2) ... (9,3,9)。排序是一维的，第一个元素比第二个元素更重要。

在我们的案例中，我们真正想要的是：对于第一个元素的每个值，拉出一个 subMap，其中第二个元素不断变化。这涉及每次第一个元素更改时在树内跳转——这不是一个长时间的连续迭代。我发现表达这一点的最好方法是将 subMap 调用包装在一个 for 循环中，“手动”改变高阶元素：

for (int x = minX; x <= maxX; x++) {
    SortedSet<Tuple3<Integer, Integer, Integer>> xSubset = set.subSet(
        new Tuple3(x, minY, null  ), true, // inclusive lower bound, null tests lower than anything
        new Tuple3(x, maxY, Fun.HI), true  // inclusive upper bound, HI tests higher than anything
    );
    for (Tuple3<Integer, Integer, Long> item : xSubset) {
        int x = item.a;
        int y = item.b;
        int z = item.c;
        // ...
    }
}

据我所知，这反映了操作的自然复杂性：您需要重新深入到树中，以便在第二个元素的范围内开始每次迭代。

于 2015-03-02T11:15:07.870 回答