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

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

Хеш / B: дерево

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

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

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

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

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

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

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

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

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

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