Хранение динамических объектов с растущими списками на диске

Question

Хорошо, я до сих пор разрабатывал систему в основной памяти, которая имеет много различных объектов, и каждый объект хранит списки других объектов в системе. Теперь я хочу переместить это в постоянное хранилище. Я не ищу очевидного ответа на вопрос об использовании СУБД, потому что дело в том, что я пишу собственную базу данных для моей системы.

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

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

Количество операций ввода-вывода не так уж страшно, и я постараюсь сохранить локальность частей списка, чтобы исключить ненужные операции ввода-вывода, но есть ли лучший способ сделать это? Правильно ли я пытаться хранить списки отдельно от объекта или мне следует рассмотреть способы хранения их вместе с данными объекта. Я беспокоюсь о том, что по мере роста одного списка он будет переходить в другой, а затем его необходимо фрагментировать, что может усложниться. Любые предложения приветствуются и спасибо заранее.

Answer 1

Ваша идея иметь эти расширяемые списки хороша. Я думаю, что в вашем объяснении отсутствуют некоторые детали (т.е. упорядоченные списки или нет, что вы имеете в виду, пытаясь отделить списки от объектов, может помочь диаграмма этих списков).

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

Дальнейшее улучшение, если вы выполняете поиск по спискам, - это сохранять их отсортированными ... или, по крайней мере, частично отсортированными, чтобы вы могли группировать похожие списки в одном блоке. Это ускорит поиск в списках, если вы часто будете кешировать в памяти, говоря границы каждого блока (узлы со значениями от 1 до 9, 10-25 и т. Д.). Сортировка слиянием, вероятно, лучшая сортировка для списков. Или даже лучше, когда вы вставляете узлы в списки, вставляйте их в правильном месте, чтобы список всегда сортировался. Затем посмотрите с помощью бинарного поиска. Если данные не проиндексированы должным образом и не отсортированы, вы отправляете запросы на диск несколько раз, и в этом случае любой используемый вами поиск даст вам линейное время из-за времени на диске.

Вы также можете кэшировать узлы данных из 10% наиболее популярных узлов / списков.

В зависимости от размера этих списков (и от того, сколько у вас есть чанков), вы можете использовать RAID, чтобы получить возможность параллельного чтения / записи.