Персистентные стратегии для деревьев основной памяти B + - PullRequest
Новая
       20

Персистентные стратегии для деревьев основной памяти B +

4 голосов
/ 25 марта 2011

Я пытаюсь разработать индекс основной памяти для пар ключ-значение с использованием C ++.Мне нужно убедиться, что индекс восстанавливается после сбоя.Я использую реализацию CSB + -Tree (лицензия BSD), которую я нашел здесь Основная проблема, с которой я сталкиваюсь, - это сохранение данных отношения родитель-потомок после повторного создания узлов.Я искал различные стратегии для сохранения и восстановления «древовидной структуры» на / с диска.Вот некоторые из них:

  1. Сохранение объектов узлов в предзаказе и запись NULLS для пустых дочерних указателей.
  2. Предоставление IDS узлам и сохранение идентификатора узла вместо указателя при записи на диск, а затем разрешение указателей во время повторного создания экземпляра с использованием идентификаторов.
  3. Использование значений смещения файла (адреса в физической памяти) вместо адресов основной памяти дочерних узлов при сохранении.Это может означать, что я должен спасти с листа.

Я также посмотрел несколько библиотек сериализации.Google ProtocolBuffers и Boost Serialization.

Теперь «узлы» в реализациях имеют ряд переменных-указателей. Некоторые из них являются указателями на другие узлы, тогда как другие являются указателями на «значения ключа».Приведенный ниже код является упрощенной версией, чтобы сохранить сущность. 

struct NodeHead  
{  
    NodeHead *null; // null indicates internal node  
    char *children; // ptr to children  
    NodeEntry entries[1]; // entry array  
}

struct NodeEntry  
{  
    uint16_t offset;   // offset to NodeHead of the key in byte  
    uint8_t next;   // index of the next entry; 0xff means null  
    uint8_t num;    // [0]: number of entries in use  
};

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

1 Ответ

0 голосов
/ 18 апреля 2011

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

...