В IRC, мы говорим о новых форматах индекс для блока цепи. Так как большинство вещей, которые мы хотим, чтобы индекс, являются случайными, это становится волосатым.

Я имею в виду дерева структуры списков. Он должен иметь очень хорошую производительность даже в самом худшем случае, и быть очень безопасными при неудачах IO.

На практике это коллекция 4К куски. Каждый блок начинается с заголовком, каким-то, вероятно, очень простым. Как минимум, каждый кусок должен указать, какой тип кусок это и кусок ID сделает его очень легко держать журнал (см. Ниже) 4k был выбран потому, что он является родным размером блока современных жестких дисков. Это также родной размер страницы виртуальной памяти в большом количестве процессоров. Память отображается файл ввод-вывод должен быть быстрым, не считая синхронизируется.

Первый кусок будет дерево кусок. После заголовка, он имеет 64 указателей, каждый из 32 бит в длину. Эти указатели на номера куска внутри индексного файла. Первый указатель для самой левой ветви двоичного дерева, что соответствует 000000, второй 000001, третьему 000010 и т.д. подстановочным очень быстро, просто изолировать 6 бит, которые имеют важное значение, необходимо умножить на 4 и добавить заголовок размер. Это также может быть другой тип ломтика, "корневой кусок" с дополнительными метаданными, но будет в основном действовать как дерево кусок.

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

Если указатель на список кусок, что кусок имеет список не более чем 62 или 63 указателей (это зависит от размера заголовка) в полном составе блока, каждый указатель имеет длину 64 бита, только смещение байта. Списки не обязательно сортируют, но к тому времени, когда вы там, это всего лишь вопрос нескольких десятков сравнений.

Каждый раз, когда вставка может вызвать список кусок ударить высокую оценку воды, это вызывает REORG. 64 новые список ломтей и новое дерево кусок написаны и элементы из старого списка куска распределены среди новых списков. После того, как те сделаны и синхронизируются, родительское дерево фрагмент будет перезаписан с указателем на новое дереве блок. Тогда старый кусок помечается доступен. Так как куски все тот же размер, структура не будет фрагментировать. В худшем случае это сбой как раз перед обновлением старого куска, который оставил бы 65 детей-сирот. Сбор мусора должен быть тривиальным, хотя и свободный список куска прост в обслуживание.

Для дополнительной безопасности, пишет может быть сделано с журнальным куском или два, например, запас кусок # 2 в качестве постоянного журнала, и в любое время вы должны писать, писать там первым, а затем записать реальный кусок. Для повышения производительности, вы, вероятно, хотите десятки или сотни журнальных кусков. Если у них есть идентификаторы, в любое время открыть файл, вы можете просто повторить, что вы найдете там. Нулевой весь журнал, когда вы сделали с ним, так что будущие записи могут просто начать в начале журнала и перейти в (записи) порядке.

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

Когда система ввода-вывода связан, буфер может даже иметь другие виды использования. Например, при использовании для blockchain, во время начальной загрузки, буфер цепь может быть позволена расти до необычных размеров, и все в основном в памяти, с законченными куски написано только при полном заполнении. В случае аварии, только самые последние несколько десятков индексов будут потеряны. Когда узел был пойман, он может затем воспроизвести буферы, начиная с самого старого фрагмента, и только освобождая их после того, как их содержание было полностью привержен к основной конструкции. Это может привести к дыре в структуре, но только один раз, и дефрагментация будет легко.