Ищем карту со строковым ключом с эффективным поиском и постоянством диска

Question

У меня есть структура данных, в которой ключом является строка, ссылающаяся на целое значение. Я не могу поместить все ключи String в память. Моя самая важная задача - выполнить быстрый поиск. Если бы я собирался реализовать это сам (без инструментов или библиотек), я думал о реализации b-дерева, где узлы - это байтовое значение utf-8 строки. Глубина будет соответствовать позиции в строке. Однако в какой-то момент дерево необходимо сохранить на диске, поскольку все это не помещается в память. Я могу представить много оптимизаций к этому, что у меня не будет времени, чтобы написать. Прежде чем начать, мне было интересно, есть ли уже такие инструменты, как это? Возможно, lucene может сработать, но я не уверен, так как мне нужно точное соответствие (не размытое). Есть идеи? Спасибо.

Answer 1

Попробуйте Redis . Предоставляет постоянные структуры данных.

Answer 2

См. HTree или BTree из проекта JDBM .

Они не реализуют интерфейс Map, но предлагают аналогичные API.

Answer 3

может быть, это слишком просто - почему бы вам не использовать такую ​​стратегию хеширования, как md5 или sha1? Очевидно, что время хэширования будет учитываться, и это не решит вашу проблему, если вам нужно знать фактическое значение строки, но, возможно, вы не знаете.