MapDB -子映射行为

Question

我有一个关于使用MapDB的问题，特别是关于查询子映射的问题。我从https://github.com/jankotek/MapDB/blob/release-1.0/src/test/java/examples/TreeMap_Composite_Key.java的官方示例中摘取了代码片段。这个例子很容易理解。出于测试目的，我互换了关键部分“镇”和“街”，并以相同的方式调整了submap调用。不幸的是，现在地图不再受submap调用的限制。相反，返回整个map (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");

谁能给我解释一下为什么会发生这种情况，以及如何避免这种情况？我的项目中也有类似的用例。

提前致谢并致以敬意:)

Answer 1

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

MapDB存储您的对象，以便很容易按照它们的自然顺序迭代它们(或它们的一个子范围)。该顺序不是您在迭代值时可以更改的内容，而是在插入对象时需要考虑的内容。它会影响存储它们的结构( b-tree)的布局。

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

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

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)。现在，与您的示例一样，我们将submap调用更改为使用这些边界元组：

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;
        // ...
    }
}

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