Ориентированная на производительность конструкция базы данных с основанием (ключ/значение)

Question

Я нахожусь на этапе подготовки графической базы данных (или ключевого значения) для C++, которую многие здесь найдут похожими на такие проекты как http://neo4j.org/.

Поскольку это очень ранней стадии проектирования, мои требования просты, нерафинированное и (я признаю), вероятно, до сих пор довольно наивным:

• Направленный ациклический граф
  • Tree- как структура с несколькими корнями и многими листьями
  • Филиалы могут содержать ссылки на другие отрасли
  • Но нет циклов
  • На графике представлена ​​ключ-значение парой, где ключи и значения представляют собой простые типы (целые числа), по большей части, но некоторые из них могут относиться к более сложным типам, таким как строки
• Запросы
  • Простые запросы обычно возвращают ребра. То есть Какие края, начинающиеся с этого корня, соответствуют (ключевое значение/значение/ключевое значение tupple)?
  • запросов с использованием строк ключей (ключ, ключ, ключ, значение)
• модели доступа и производительности
  • быстрого поиска следует подчеркнуть
  • Добавление ребер
  • Но отсутствие удаления краев/узлов из графика. То есть График будет расти, но он никогда не уменьшится.
  • Оптимизация может быть выполнена на графике для того, чтобы оптимизировать распределение памяти для использования кэша
  • Размера графа в порядке около 1 МБ - 2 ГБ и должны по большей части, пригодной в первичную память

с учетом этих грубых требований, как вызов, что бы ваши основные проблемы быть в отношении: хранение

• памяти: Layout, распределение
  • E.g. Пул блоков фиксированного размера?
  • Назначение памяти алгоритмом кластеризации?
• Быстрые запросы
• Динамическая реорганизация
  • Как обрабатывать добавление ребер/узлов?
  • обновления для оптимизации (например, улучшения памяти макета)
• Параллельный доступ
  • Е.Г. Обработка изменений в макете памяти оптимизирующим потоком?

Ищу хороших отправных точек, из которых для работы, поэтому я более чем счастлив получить ссылки на текущую работу. Самое главное: должен Я думаю об этом не думать о?

Answer 1

Быстрая база данных ключ/значение, которое может быть интересно для справки является TinyCDB http://www.corpit.ru/mjt/tinycdb.html

Answer 2

Но нет циклов

Это тяжелое требование, если вам нужно быстро край вставки. Проверка того, что новый край не вводит цикл, - это O (v + e) ​​в худшем случае (где v - число вершин, e - число ребер). Вероятно, это также исключает параллельную вставку ребер. Подумайте, чтобы это требование было необязательным.

Другой вариант - провести различие между двумя операциями вставки: CheapInsert и ExpensiveInsert. Пусть каждая вершина имеет целое число «ранг» и допускает только дешевые вставки ребер от вершин с более низким до более высокого ранга. Дорогая вставка не будет иметь этого ограничения и автоматически переписывает ранги, если это необходимо. Клиенты могут проверять и изменять ранг любой вершины (до тех пор, пока правило с низким до максимума не будет нарушено). Таким образом, они могут реализовать свою собственную стратегию вставки, возможно, используя некоторые специфические свойства графика, чтобы избежать дорогостоящих вставок.