Кажется, что цель imap - удерживать точки для отдельных inodes, чтобы запись могла выполняться очень быстро (может ли кто-нибудь объяснить, как это тоже работает?), Но мне было интересно, какой смысл иметь imap, которые содержат указатели другим имапам было. Не только это, но они существуют на нескольких уровнях ...
Карта iNode (иногда искаженная для imap, хотя IMAP - это протокол электронной почты) - это указатель на iNode (кажется, у вас это уже есть). Это используется при ведении журнала (в основном, файловых системах журнала) в качестве уровня абстракции. В основном, когда вы хотите найти данный iNode файловой системы, слой перевода ищет карты iNode для этого местоположения и возвращает текущий iNode, на который фактически должна указывать файловая система. Затем это место читается, чтобы найти файл.
Некоторые файловые системы могут их складывать. Когда одна логическая файловая система iNode записывается несколько раз без очистки журнала / журнала, тогда каждая запись будет использовать новое физическое местоположение на диске, включая iNode, указывающий на это местоположение. Каждая устаревшая карта iNode обновляется, чтобы указать на новую карту iNode и, в конечном итоге, на текущий iNode.
Причина этого не в скорости, а в последовательности. Во время записи на диске выбирается новое местоположение, выполняется запись, затем старое местоположение обновляется и указывает на новое местоположение. При объединении журнала / журнала файловая система обновляется, чтобы указать на последнее местоположение, а старые местоположения освобождаются. Таким образом, если в любой момент произойдет сбой питания, вы никогда не потеряете данные, файловая система указывает либо на старую версию файла, либо на новую, но не на что-либо еще (например, наполовину записанный файл или поврежденные данные, либо в трава).
Это довольно типичный способ работы со структурами, которые указывают на другие структуры и могут радикально отличаться по размеру. Файловая система уже управляет блоками фиксированного размера дискового пространства в разделе. Таким образом, вы обычно используете этот размер (или кратное ему) в качестве размера вашей единицы.
Если у вас есть достаточно предметов, чтобы вы могли удерживать их в блоке, сделайте это. Если блок переполняется, вы заменяете один элемент в этом блоке указателем на вновь выделенный блок, который содержит указатель, который вы заменили, и новый указатель.
Этот метод выбран потому, что:
Хорошо работает с кешированием. К блокам самого высокого уровня часто обращаются и они остаются в кеше.
Требуется только отслеживать свободное пространство в единицах размера блока, поэтому он хорошо работает с управлением свободным пространством на основе растровых изображений.
Он хорошо масштабируется, при этом среднее время поиска примерно пропорционально логарифму количества элементов. (Теоретически, если вы храните 32 указателя в блоке, вы можете получить доступ к 32 ^ n указателям с n поисками.)
Хорошо балансирует в динамике. При добавлении или удалении указателей можно выполнять довольно простые операции, чтобы дерево оставалось сбалансированным. (Вы не хотите получить длинное тощее дерево. Вы хотите, чтобы оно было толстым и коротким. На самом деле это очень легко сделать.)