MapDB - поведение подкачки

Question

У меня вопрос об использовании 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"); 

Может кто-нибудь объяснить мне, почему это происходит и как этого можно избежать? У меня есть аналогичный вариант использования в моем проекте.

Заранее спасибо и касается :)

Answer 1

Я столкнулся с аналогичной проблемой в последнее время при индексировании географических объектов в двумерный плитках. Мне пришлось просматривать исходный код MapDB и экспериментировать, чтобы понять, что происходит.

MapDB хранит ваши объекты таким образом, чтобы их можно было легко перебирать (или их поддиапазон) в натуральном порядке. Этот порядок не является чем-то, что вы можете изменить при итерации над значениями, это то, что принимается во внимание при вставке объектов. Это влияет на расположение структуры, в которой они хранятся (a 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). Теперь, как в вашем примере мы изменим вызов подкарта использовать эти оценки кортежи:

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). Порядок одномерен и первый элемент более значителен, чем второй.

Что мы действительно хотим в наших случаях: для каждого значения первого элемента, вытащите подмножество, где второй элемент изменяется непрерывно. Это включает в себя прыжки вокруг дерева каждый раз, когда меняется первый элемент - это не одна длинная непрерывная итерация. Лучший способ я нашел, чтобы выразить это просто обернуть подкарта звонки в цикле, варьируя элемент высокого порядка «вручную»:

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

Насколько я знаю, что это отражает естественную сложность операция: вам нужно снова свернуться в дерево, чтобы начать каждую итерацию по диапазону вторых элементов.