Просто чтобы подтвердить мое утверждение о том, что для любого сегмента, содержащего до 1 000 000 записей, достаточно обычного TreeMap, вот очень простой тестовый пример, который дает несколько цифр (внимание: это не микробенчмарк, это просто чувствую масштабность этой проблемы).
Я использовал случайно сгенерированные UUID для имитации ключей (если бы вы заменили дефисы слешами, вы бы даже получили вид структуры каталогов). После этого я поместил их в обычный java.util.TreeMap и наконец запросил их с помощью map.subMap(fromKey, toKey).
public static void main(String[] args) {
TreeMap<String, Object> map = new TreeMap<String, Object>();
int count = 1000000;
ArrayList<String> uuids;
{
System.out.print("generating ... ");
long start = System.currentTimeMillis();
uuids = new ArrayList<String>(count);
for (int i = 0; i < count; i++) {
uuids.add(UUID.randomUUID().toString());
}
System.out.println((System.currentTimeMillis() - start) + "ms");
}
{
System.out.print("inserting .... ");
long start = System.currentTimeMillis();
Object o = new Object();
for (int i = 0; i < count; i++) {
map.put(uuids.get(i), o);
}
System.out.println((System.currentTimeMillis() - start) + "ms");
}
{
System.out.print("querying ..... ");
String from = "be400000-0000-0000-0000-000000000000";
String to = "be4fffff-ffff-ffff-ffff-ffffffffffff";
long start = System.currentTimeMillis();
long matches = 0;
for (int i = 0; i < count; i++) {
Map<String, Object> result = map.subMap(from, to);
matches += result.size();
}
System.out.println((System.currentTimeMillis() - start) + "ms (" + matches/count
+ " matches)");
}
}
и вот пример вывода с моей машины (1 000 000 ключей, 1 000 000 запросов диапазона):
generating ... 6562ms
inserting .... 2933ms
querying ..... 5344ms (229 matches)
Вставка 1 ключа заняла в среднем 0,003 мс (хотя, конечно, больше к концу), тогда как запрос поддиапазона с 229 совпадениями занимал 0,005 мс на запрос. Это довольно нормальное представление, не так ли?
После увеличения числа до 10 000 000 ключей и запросов цифры выглядят следующим образом:
generating ... 59562ms
inserting .... 47099ms
querying ..... 444119ms (2430 matches)
Для вставки 1 ключа в среднем потребовалось 0,005 мс, а для запроса поддиапазона с 2430 совпадениями - 0,044 мс на запрос. Даже несмотря на то, что запросы стали в 10 раз медленнее (в конце концов, он перебирает все совпадения, которые всегда равны O (n)), производительность все равно не так уж и плоха.
Поскольку S3 является облачным сервисом, я бы предположил, что в любом случае он в значительной степени ограничен сетевыми возможностями. Следовательно, нет необходимости в крайне сложной структуре данных для получения требуемой производительности. Тем не менее, в моем тестовом примере отсутствуют некоторые функции, в частности, параллелизм и постоянство. Тем не менее, я думаю, что я показал, что правильной древовидной структуры достаточно для этого варианта использования. Если вы хотите сделать что-то необычное, поэкспериментируйте с блокировкой чтения-записи поддерева и, возможно, замените .subMap (fromKey, toKey);