В связи с неуклонным приближением необходимости хранения гиперграфовых на диске...
...у меня начала подниматься проблема: как же хранить-то?
Общее направление движения у меня следующее:
1) я делаю прототип графовой БД - с демонстрацией, зачем же это нужно;
2) я делаю хранение графов в некоторой виртуальной памяти - получаю возможность внешнего хранения;
3) я делаю транзакционную память к этой виртуальной памяти; - получаю возможность параллельной работы нескольких процессов
4) я делаю распределённую транзакционную память - с толстыми деревьями и прочим, чтобы процессы были распределены;
5) я делаю отказоустойчивую транзакционную память - чтобы можно было убрать узел и заменить его на новый, который бы подхватил недостающие ему данные.
(для проектов "по вечерам и выходным" это более, чем амбициозные планы)
Итак, мне надо как-то хранить большую память - многие гигабайты. Разумно будет хранить отдельные блоки памяти, адресуясь поблочно.
Обращаться надо быстро, по возможности.
Один из вариантов - разновидность B-tree. Доступ к любому элементу - O(logN), основание логарифма достаточно большое. Эта структура данных в статическом варианте не зависит от размера кэша. Экспоненциальный вариант (когда размер блока уменьшается вдвое при увеличении расстояния от корня дерева), к тому же, является динамически нейтральным к кэшу. Но сложен в исполнении - это комбинация сразу нескольких структур данных.
Есть такая структура данных, называется splay tree. Это тоже дерево двоичного поиска, только совсме динамическое. В отличии от обычных деревьев, после поиска "дерево наизнанку" меняет свою структуру, перенося интересный элемент в корень структуры. Таким образом, поиск нужного элемента становится менее, чем логарифмическим. Это свойство используется для построения разного рода кэшей.
Тут меня в голову ударила идея. А почему бы не скрестить "Б-дерево" и "дерево наизнанку"? Почему корень splay tree должен иметь всего один элемент?
Если удастся скрестить эти две структуры данных, то получится лучшее из двух миров: частое обращение к каким-то элементам будет подтягивать их к вершине (там O(block_size) ключей), формируя своего рода кэш. Блоки второго уровня (в которых хранится уже O(block_size2 ключей)) будут играть роль L2 кэша и тп, и тд. Получается иерархия памяти с постоянным увеличением задержки доступа и объёма.
Консультация с подвернувшимися под руку специалистами по структурам данных выявила полное отсутствие разработок на эту тему и некоторые проблемы в скрещивании подходов. Например, в гипотетическом splay B-tree нарушается требование балансировки. Плюс, надо поддерживать уровни заполнения блоков (количество ключей должно быть между block_size и block_size/2), что выглядит достаточно сложно, на данный момент. Наверняка ещё что найдётся.
Но сама идея мне нравится.
Общее направление движения у меня следующее:
1) я делаю прототип графовой БД - с демонстрацией, зачем же это нужно;
2) я делаю хранение графов в некоторой виртуальной памяти - получаю возможность внешнего хранения;
3) я делаю транзакционную память к этой виртуальной памяти; - получаю возможность параллельной работы нескольких процессов
4) я делаю распределённую транзакционную память - с толстыми деревьями и прочим, чтобы процессы были распределены;
5) я делаю отказоустойчивую транзакционную память - чтобы можно было убрать узел и заменить его на новый, который бы подхватил недостающие ему данные.
(для проектов "по вечерам и выходным" это более, чем амбициозные планы)
Итак, мне надо как-то хранить большую память - многие гигабайты. Разумно будет хранить отдельные блоки памяти, адресуясь поблочно.
Обращаться надо быстро, по возможности.
Один из вариантов - разновидность B-tree. Доступ к любому элементу - O(logN), основание логарифма достаточно большое. Эта структура данных в статическом варианте не зависит от размера кэша. Экспоненциальный вариант (когда размер блока уменьшается вдвое при увеличении расстояния от корня дерева), к тому же, является динамически нейтральным к кэшу. Но сложен в исполнении - это комбинация сразу нескольких структур данных.
Есть такая структура данных, называется splay tree. Это тоже дерево двоичного поиска, только совсме динамическое. В отличии от обычных деревьев, после поиска "дерево наизнанку" меняет свою структуру, перенося интересный элемент в корень структуры. Таким образом, поиск нужного элемента становится менее, чем логарифмическим. Это свойство используется для построения разного рода кэшей.
Тут меня в голову ударила идея. А почему бы не скрестить "Б-дерево" и "дерево наизнанку"? Почему корень splay tree должен иметь всего один элемент?
Если удастся скрестить эти две структуры данных, то получится лучшее из двух миров: частое обращение к каким-то элементам будет подтягивать их к вершине (там O(block_size) ключей), формируя своего рода кэш. Блоки второго уровня (в которых хранится уже O(block_size2 ключей)) будут играть роль L2 кэша и тп, и тд. Получается иерархия памяти с постоянным увеличением задержки доступа и объёма.
Консультация с подвернувшимися под руку специалистами по структурам данных выявила полное отсутствие разработок на эту тему и некоторые проблемы в скрещивании подходов. Например, в гипотетическом splay B-tree нарушается требование балансировки. Плюс, надо поддерживать уровни заполнения блоков (количество ключей должно быть между block_size и block_size/2), что выглядит достаточно сложно, на данный момент. Наверняка ещё что найдётся.
Но сама идея мне нравится.