Зачем использовать хеширование для создания путей к большим коллекциям файлов?

Question

Я заметил несколько случаев, когда приложение или база данных сохраняли коллекции файлов / BLOB-объектов, используя для определения пути и имени файла. Я полагаю, что предполагаемый результат - это ситуация, когда путь никогда не становится слишком глубоким, или папки становятся слишком полными - слишком много файлов (или папок) в папке, создающей более медленный доступ.

РЕДАКТИРОВАТЬ: Примерами часто являются цифровые библиотеки или репозитории, хотя самый простой пример, который я могу придумать (который можно установить примерно через 30 секунд), - это база данных / документов цитирования Zotero.

Зачем это?

РЕДАКТИРОВАТЬ: спасибо Mat за ответ - есть ли у этого метода использования хеша для создания пути к файлу имя? Это шаблон ? Я хотел бы прочитать больше, но мне ничего не удалось найти в

Цифровой библиотеке ACM

Answer 1

Hash / B: Дерево

Преимущество хэша состоит в том, что он быстрее просматривается, когда вы собираетесь использовать для поиска только оператор "=".

Если вы собираетесь использовать такие вещи, как "<" или ">" или что-то еще, кроме "=", вы захотите использовать B: Tree, потому что он сможет выполнять такой поиск.

Структура каталогов

Если у вас есть сотни тысяч файлов для хранения в файловой системе, и вы поместите их все в один каталог, вы достигнете точки, когда индекс каталога будет настолько толстым, что для добавления / удаления потребуется несколько минут. файл из этого каталога, и вы можете даже добраться до точки, когда индекс не помещается в памяти, и вы не сможете добавить / удалить или даже коснуться каталога.

Вы можете быть уверены, что для метода хеширования foo foo ("что-то") всегда будет возвращать одно и то же, скажем, "grbezi". Теперь вы используете часть этого хеша для хранения файла, скажем, в gr / be / что-то. В следующий раз, когда вам понадобится этот файл, вам нужно будет просто вычислить хеш, и он будет доступен напрямую. Кроме того, вы получаете тот факт, что с хорошей хеш-функцией распределение хешей в хеш-пространстве довольно хорошее, и для большого количества файлов они будут равномерно распределены внутри иерархии, таким образом распределяя нагрузку.

Answer 2

Я думаю, нам нужно немного поближе взглянуть на то, что вы пытаетесь сделать. В общем, хеш и B-дерево абстрактно предоставляют две общие операции: «вставить элемент» и «поиск элемента». Хеш выполняет их, асимптотически , за O (1) времени, пока хеш-функция хорошо себя ведет (хотя в большинстве случаев очень плохо ведущий себя хеш против конкретной рабочей нагрузки может быть столь же плохим, как O (n) .) Дерево АБ, для сравнения, требует O (log n) времени как для вставок, так и для поиска. Так что если это единственные операции, которые вы выполняете , хеш-таблица является более быстрым выбором (и значительно проще, чем реализация B-дерева, если вы должны написать ее самостоятельно.)

Кикер появляется, когда вы хотите добавить операции. Если вы хотите сделать что-нибудь, что требует упорядочения (что означает, скажем, чтение элементов в порядке расположения ключей), вам нужно сделать другие вещи, самое простое - скопировать и отсортировать ключи, а затем получить доступ к ключам, используя эту временную таблицу. Проблема заключается в том, что временная сложность сортировки составляет O (n log n) , поэтому, если вам придется делать это очень часто, хеш-таблица больше не имеет преимущества в производительности.

Answer 3

В частности, в Zotero используются уникальные восьмизначные буквенно-цифровые идентификаторы; они не являются хешем чего-либо, связанного с базовым файлом, и они фактически соответствуют ключу вложения в базе данных Zotero (также используется для доступа к файлу и его метаданным с помощью API Zotero). Ключ гарантированно уникален в локальном экземпляре Zotero (ну, для библиотек с количеством элементов менее 2821109907457), и он соединяется с ключом библиотеки, чтобы создать глобально уникальный ключ для вложения в более крупном мире Zotero. Ключи используются в файловой системе в значительной степени для обхода именных конфликтов и специальных символов.

Насколько я понимаю, многие из UUID, которые вы видите в мире библиотек и хранилищ, схожи в оправдании - они менее подвержены столкновениям, чем автоинкрементные числовые идентификаторы, делая многие вещи намного проще, но они не в отличие от надлежащих хэшей SHA1, используемых в качестве идентификаторов коммитов в git, обязательно хеш.

Answer 4

Хэши также придают уникальность пути. Очень мало именных столкновений.

Answer 5

Хеш проверяется быстрее, чем обход B-дерева. Так что, если частые проверки существования сделаны, этот метод может быть полезен. Кроме этого, я не очень понимаю ситуацию, потому что хеш-таблицы не сохраняют порядок или иерархии. Следовательно, сохранение структуры каталогов в них не представляется возможным, если каталоги нужно просматривать по отдельности.