#python #linux #complexity-theory #ext4
#python #linux #сложность-теория #ext4
Вопрос:
Кто-нибудь знает, какова сложность функции os.path.exists в python с файловой системой ext4?
Ответ №1:
Базовая структура каталогов, используемая Ext4 (и Ext3), точно такая же, как в Ext2. Ext3 добавляет ведение журнала, Ext4 улучшает это ведение журнала. Ведение журнала не имеет отношения к вашему вопросу.
Изначально Ext2 использовался для хранения этого в виде списка, но это, конечно, было неэффективно для больших каталогов. Итак, он был изменен на измененную версию B-дерева под названием HTree. В отличие от стандартного B-дерева, HTree имеет постоянную глубину и использует хэш-карту для каждого узла, поэтому сложность поиска составляет O (1).
Схема Ext2, которую мы назвали «HTree», использует 32-разрядные хэши для ключей, где каждый хэш-ключ ссылается на диапазон записей, хранящихся в конечном блоке. Поскольку внутренние узлы имеют размер всего 8 байт, HTrees имеют очень высокий коэффициент разветвления (с помощью индексного блока 4K можно ссылаться на более чем 500 блоков), двух уровней индексных узлов достаточно для поддержки более 16 миллионов имен файлов из 52 символов. Для дальнейшего упрощения реализации HTrees имеют постоянную глубину (один или два уровня). Сочетание высокого коэффициента разветвления и использования хэша имени файла плюс специфичного для файловой системы секрета в качестве ключа поиска для HTree позволяет избежать необходимости выполнения реализацией операций балансировки.
Смотрите: http://ext2.sourceforge.net/2005-ols/paper-html/node3.html
Ответ №2:
Велика вероятность, что сложность заключается в том, O(n) что n — это глубина файловой системы (например, / будет иметь n = 1, / что-то n = 2, …)