Напомню о том, что цель проекта Boson — это разработка встроенного движка базы данных документов JSON, написанный на C++. Основные возможности:

• Стандартное хранилище JSON-документов в формате ключ/значениями с постоянным хранением на диске. Размер документов до 4Gb.

• Быстрый поиск документов по ID с использованием индекса B+ дерева.

• Поддержка курсоров для линейного обхода записей.

• База данных в одном файле, без временных файлов.

• Простое, чистое и легкое в использовании API.

• Самодостаточный и не требующий настройки.

В предыдущих двух статьях мы прошли шаги от кэширования файлового ввода/вода (часть I) до построенного на его базе хранилища записей произвольной длины (часть II) с проверкой целостности, возможностью получения записей списком и повторным использованием свободного места. Теперь мы переходим к завершающей части и "сердцу" СУБД - индексу.

Зачем нужен индекс: предположим, что в базе есть 1 млрд не отсортированных записей документов, тогда поиск конкретного документа по ID потребует O(n) операций, то есть до 1 млрд операций в худшем случае. Однако, если бы документы в базе были бы отсортированы по ID, то поиск в сортированной базе, тем же бинарным поиском занял бы O(log n) занял бы 30 операций. Что, теоретически, на базе в 1 млрд записей будет в 33.3 млн раз быстрее.

Замечательная мысль, но осталось понять как в случае вставки документов с произвольным ID записи в базе всегда оставались отсортированными без необходимости "раздвигать" данные в базе при каждой вставке или обновлении записи. Это уже не так тривиально.

Для решения этой проблемы в 1972 году Rudolf Bayer и Edward McCreight была впервые представлена идея B-деревьев, которые являются основой для B+ деревьев - это расширение концепции B-деревьев, в которых все ключи на уровне листьев объединены в связанный список (Linked List), что делает их более эффективными для операций последовательного доступа. И, конечно, алгоритм B+ деревьев даёт выдающуюся производительность: поиск - O(log N), вставка - O(log N), удаление - O(log N).

Для начала немного погрузимся в теорию о том как устроены B+ деревья и какие операции нужны чтобы поддерживать дерево в целостном и сбалансированном виде:

B+ дерево состоит из внутренних узлов и листовых узлов. Внутренние узлы хранят только ключи для направления поиска, в то время как сами данные содержатся в листовых узлах:

• Внутренние узлы (Inner Node): Содержат ключи и указатели на дочерние узлы, но не хранят реальные данные. Каждый внутренний узел может содержать от ⌈M/2⌉ до M-1 ключей и M дочерних узлов. Каждый ключ в узле разделяет дочерние узлы: левый дочерний узел содержит ключи, меньшие ключа родительского узла, а правый дочерний узел содержит ключи, большие или равные ключу родительского узла.

• Листовые узлы (Leaf Node): Хранят пары ключей и указателей на данные. Связаны между собой в двусвязный список для эффективных диапазонных запросов. Каждый листовой узел может также содержать от ⌈M/2⌉ до M-1 ключей и M-1 значений.

Чтобы при произвольных вставках, удалениях и изменениях записей поддерживалась сбалансированность и отсортированность B+ дерева, выполняются следующие операции:

1. Операция поиска: Для поиска определенного ключа в B+ дереве начинают с корневого узла. Сравнивают целевой ключ с ключами в текущем узле, чтобы определить соответствующий дочерний узел. Если целевой ключ меньше, переходят к левому дочернему узлу; если больше или равен, переходят к правому дочернему узлу. Этот процесс повторяется, пока не будет достигнут нужный листовой узел, где и завершается поиск. Поскольку B+ дерево сбалансировано, сложность поиска составляет O(log n).

2. Операция вставки: Вставка ключа начинается с поиска подходящего листового узла с использованием процедуры поиска. Затем ключ вставляется в листовой узел в правильном отсортированном положении. Если узел превышает свою максимальную вместимость (M-1 ключей), происходит разделение. Узел делится на два, и половина ключей переходит в новый дочерний узел. Средний ключ поднимается в родительский узел. Если родительский узел также переполняется, это может вызвать дальнейшие разделения, которые могут распространиться до корня, потенциально увеличивая высоту дерева.

3. Операция удаления: Удаление ключа начинается с поиска целевого ключа в соответствующем листовом узле. Ключ удаляется, но если это приводит к тому, что узел содержит меньше ключей, чем минимум (⌈M/2⌉), требуется корректировка. Дерево может заимствовать ключ у соседнего узла, если у него больше минимального количества ключей. Если заимствование невозможно, узел сливается с соседним, и ключ из родительского узла удаляется или корректируется соответственно. Этот процесс слияния может распространяться вверх по дереву, если необходимо, чтобы сохранить баланс дерева.

4. Диапазонные запросы: B+ деревья особенно хорошо подходят для диапазонных запросов благодаря связной структуре листовых узлов. Чтобы выполнить диапазонный запрос, начинают с поиска первого ключа в нужном диапазоне, используя процедуру поиска. После нахождения начального ключа переходят по двусвязному списку листовых узлов, пока не достигнут конца диапазона. Эта связная структура делает сканирование последовательности значений эффективным и простым.

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

Операции вставки и удаления могут создавать ситуацию, когда возникает переполнение узла или, наоборот, недостаток элементов. В таких случаях выполняются операции поддерживающие сбалансированность B+ дерева:

1. Разделение (Split) — выполняется когда узел в B+ дереве превышает свою максимальную вместимость (M-1 ключей). Процесс деления заключается в следующем:

   1. Узел делится на два, при этом половина ключей остается в исходном узле, а другая половина переносится в новый узел.

   2. Продвижение ключа вверх (Push Key Up) — средний ключ из исходного узла перемещается в родительский узел. Это обеспечивает обновление родительского узла, чтобы отразить изменения структуры дерева.

   3. Если родительский узел также переполняется, процесс разделения и продвижения ключа вверх может распространяться вверх по дереву, вплоть до корня (root). Если корень разделяется, создается новый корень, увеличивая высоту дерева. То есть дерево по количеству уровней растёт от корня, а не от листьев.
      

   Пример: Если в узле M=5 и он содержит 5 ключей (1, 2, 3, 4, 5), при переполнении узел делится на два: (1, 2) и (4, 5), а ключ 3 продвигается вверх.
   

2. Слияние (Merge) — выполняется когда в результате удаления ключа количество ключей в узле становится меньше минимально допустимого значения (⌈M/2⌉). Процесс слияния включает:

   1. Объединение узла с его соседним узлом (левым или правым), чтобы создать один узел.

   2. Ключ из родительского узла, который разделял эти два узла, перемещается вниз и становится частью объединенного узла.

   3. Если после слияния родительский узел остается с недостаточным количеством ключей, операция слияния может распространиться вверх по дереву.

      Пример: Если два соседних листовых узла содержат ключи (1, 2) и (3, 4), они могут объединиться в один узел (1, 2, 3, 4), и разделяющий ключ из родительского узла удаляется.
      

3. Заимствование у соседнего узла (Borrow from Sibling) — это операция, выполняемая, когда узел содержит меньше минимально допустимого числа ключей (⌈M/2⌉), но его соседний узел (левый или правый) имеет больше ключей, чем минимум.

   1. Ключ из родительского узла перемещается вниз в узел с недостаточным количеством ключей.

   2. Соседний узел передает один из своих ключей в родительский узел для поддержания баланса.

   Пример: Если узел содержит 1 ключ, а его соседний узел содержит 3 ключа, то один ключ может быть передан из соседнего узла, а родительский узел обновляется соответствующим образом.

Эти операции важны для поддержания сбалансированности B+ дерева, чтобы все узлы оставались сбалансированными и все листовые узлы находились на одном уровне, обеспечивая сложность операций O(log n).

Визуализацию как работает этот алгоритм B+ дерева можно посмотреть здесь.

Теперь приступим к реализации самого алгоритма, в данной статье я приведу лишь заголовок, а саму реализацию B+ Tree индекса вы можете посмотреть здесь.

Вот какой заголовочный файл получился у меня при реализации индекса B+ Tree:

namespace Boson {


    constexpr uint64_t TREE_ORDER = 5;
    constexpr uint64_t MAX_DEGREE = TREE_ORDER - 1;
    constexpr uint64_t MIN_DEGREE = TREE_ORDER / 2;
    constexpr uint32_t KEY_NOT_FOUND = -1;

    typedef enum : uint32_t { INNER = 1, LEAF = 2 } NodeType;
    typedef enum : uint32_t { KEYS = 1, CHILDREN = 2, VALUES = 2 } NodeArray;


    //-------------------------------------------------------------------------

    class NodeData {
    public:
        uint64_t parent;
        uint64_t leftSibling;
        uint64_t rightSibling;
        NodeType nodeType;
        uint32_t keysCount;
        union {
            uint32_t childrenCount;
            uint32_t valuesCount;
        };
        uint64_t keys[TREE_ORDER];
        union {
            uint64_t children[TREE_ORDER];
            uint64_t values[TREE_ORDER];
        };

        NodeData();

        void pushBack(NodeArray mode, uint64_t value);
        void insertAt(NodeArray mode, uint32_t index, uint64_t value);
        void deleteAt(NodeArray mode, uint32_t index);
        void resize(NodeArray mode, uint32_t newSize);
    };

    //-------------------------------------------------------------------------

    class BalancedIndex;
    class LeafNode;
    class InnerNode;

    class Node {
        friend class BalancedIndex;
        friend class LeafNode;
        friend class InnerNode;
    public:
        Node(BalancedIndex& bi, NodeType type);        
        ~Node();
        uint64_t getPosition();
        uint64_t persist();
        NodeType getNodeType();
        uint32_t getKeyCount();
        bool     isRootNode();
        bool     isOverflow();
        bool     isUnderflow();
        bool     canLendAKey();
        uint64_t getKeyAt(uint32_t index);
        void     setKeyAt(uint32_t index, uint64_t key);
        uint64_t getParent();
        void     setParent(uint64_t parentPosition);
        uint64_t getLeftSibling();
        void     setLeftSibling(uint64_t siblingPosition);
        uint64_t getRightSibling();
        void     setRightSibling(uint64_t siblingPosition);
        uint64_t dealOverflow();
        uint64_t dealUnderflow();

    protected:

        BalancedIndex& index;         // reference to index   
        uint64_t position;            // offset in file
        NodeData data;                // node data
        bool isPersisted;             // is data persisted to storage        
    
        Node(BalancedIndex& bi);
        static std::shared_ptr<Node> loadNode(BalancedIndex& bi, uint64_t offsetInFile);
        static void deleteNode(BalancedIndex& bi, uint64_t offsetInFile);

        virtual uint32_t search(uint64_t key) = 0;
        virtual uint64_t split() = 0;
        virtual uint64_t pushUpKey(uint64_t key, uint64_t leftChild, uint64_t rightChild) = 0;
        virtual uint64_t mergeChildren(uint64_t leftChild, uint64_t rightChild) = 0;
        virtual void     mergeWithSibling(uint64_t key, uint64_t rightSibling) = 0;
        virtual uint64_t borrowFromSibling(uint64_t key, uint64_t sibling, uint32_t borrowIndex) = 0;
        virtual void     borrowChildren(uint64_t borrow0er, uint64_t lender, uint32_t borrowIndex) = 0;
        virtual std::shared_ptr<std::string> toString() = 0;
    };

    //-------------------------------------------------------------------------

    class InnerNode : public Node {
        friend class BalancedIndex;
        friend class Node;
        friend class LeafNode;        
    public:
        InnerNode(BalancedIndex& bi);
        InnerNode(BalancedIndex& bi, uint64_t offsetInFile, NodeData& loadedData);
        ~InnerNode();
        uint32_t   search(uint64_t key);
        uint64_t   getChildAt(uint32_t index);
        void       setChildAt(uint32_t index, uint64_t childNode);
        void       insertAt(uint32_t index, uint64_t key, uint64_t leftChild, uint64_t rightChild);
        void       deleteAt(uint32_t index);        
        NodeType   getNodeType();
        std::shared_ptr<std::string> toString();
    protected:
        uint64_t   split();
        uint64_t   pushUpKey(uint64_t key, uint64_t leftChild, uint64_t rightChild);
        void       borrowChildren(uint64_t borrower, uint64_t lender, uint32_t borrowIndex);
        uint64_t   borrowFromSibling(uint64_t key, uint64_t sibling, uint32_t borrowIndex);
        uint64_t   mergeChildren(uint64_t leftChild, uint64_t rightChild);
        void       mergeWithSibling(uint64_t key, uint64_t rightSibling);
    };


    //-------------------------------------------------------------------------

    class LeafNode : public Node {
        friend class BalancedIndex;
        friend class Node;
        friend class InnerNode;
    public:
        LeafNode(BalancedIndex& bi);
        LeafNode(BalancedIndex& bi, uint64_t offsetInFile, NodeData& loadedData);
        ~LeafNode();
        uint32_t search(uint64_t key);
        std::shared_ptr<std::string> getValueAt(uint32_t index);
        void     setValueAt(uint32_t index, const std::string& value);
        bool     insertKey(uint64_t key, const std::string& value);
        bool     insertKey(uint64_t key, uint64_t valuePosition);
        void     insertAt(uint32_t index, uint64_t key, const std::string& value);
        void     insertAt(uint32_t index, uint64_t key, uint64_t valuePosition);
        bool     deleteKey(uint64_t key);
        void     deleteAt(uint32_t index);        
        NodeType getNodeType();
        std::shared_ptr<std::string> toString();
    protected:
        uint64_t split();
        uint64_t pushUpKey(uint64_t key, uint64_t leftChild, uint64_t rightChild);
        void     borrowChildren(uint64_t borrower, uint64_t lender, uint32_t borrowIndex);
        uint64_t mergeChildren(uint64_t leftChild, uint64_t rightChild);
        void     mergeWithSibling(uint64_t key, uint64_t rightSibling);
        uint64_t borrowFromSibling(uint64_t key, uint64_t sibling, uint32_t borrowIndex);
        uint32_t searchPlaceFor(uint64_t key);
    };

    //-------------------------------------------------------------------------


    class IndexHeader {
    public:
        uint64_t treeOrder;       // Tree order
        uint64_t rootPosition;    // Root node position in the storage file
        uint64_t recordsCount;    // Total records count
        uint64_t indexCounter;    // Index key counter
    };


    class BalancedIndex {
        friend class Node;
        friend class LeafNode;
        friend class InnerNode;
        friend class BosonAPI;
    public:
        BalancedIndex(RecordFileIO& rf);
        ~BalancedIndex();       

        uint64_t size();

        bool insert(uint64_t key, const std::string& value);
        bool update(uint64_t key, const std::string& value);
        std::shared_ptr<std::string> search(uint64_t key);
        bool erase(uint64_t key);

        std::pair<uint64_t, std::shared_ptr<std::string>> first();
        std::pair<uint64_t, std::shared_ptr<std::string>> last();
        std::pair<uint64_t, std::shared_ptr<std::string>> next();
        std::pair<uint64_t, std::shared_ptr<std::string>> previous();

        void printTree();        

    protected:

        uint64_t getNextIndexCounter();
        RecordFileIO& getRecordsFile();
        std::shared_ptr<LeafNode> findLeafNode(uint64_t key);                
        void updateRoot(uint64_t newRootPosition);
        void persistIndexHeader();
        void printTreeLevel(std::shared_ptr<Node> node, int level);

    private:
        RecordFileIO& recordsFile;
        IndexHeader indexHeader;
        std::shared_ptr<Node> root;

        std::shared_ptr<LeafNode> cursorNode;
        uint32_t cursorIndex;
        bool isTreeChanged;
    };


}

Напишем реализацию NodeData, Node, InnerNode, LeafNode, BalancedIndex и проверим как строится B+ дерево...

Каждый алгоритм и его техническая реализации в отдельности не представляли большой сложности (бинарный поиск, двусвязные списки, деревья, рекурсии многие знают со школы), пока всё это делалось в оперативной памяти и по отдельности. Однако, чтобы отладить и заставить это работать на диске (вместо new/delete нужно было использовать аналог хранения на диске - RecordFileIO), всё вместе и слаженно - это был вызов, который занял почти месяц на осознание и разработку. Тут видимо уже мои интеллектуальные ограничения. Очень сильно выручили умные указатели (smart pointers) чтобы проуправлять постоянной загрузкой и выгрузкой узлов из памяти и сохранением их на диске не создав утечку памяти. Спасибо разработчикам языка C++.

Итак посмотрим, как работает реализация. Сработало. На логах в консоли можно разглядеть структуру дерева, и ссылки на позиции в файле базы данных:

Завершив реализацию посмотрим как это примерно работает. Для статьи и удобства разглядывания скриншота взял малое количество записей, в реальных тестах проверял на больших объемах. Вставим N записей, последовательно вытащим их (проверим, что поиск работает), удалим N записей, вставим заново N записей (проверив что свободное место используется), удалим и посмотрим как отработало.

Теперь когда все три основных слоя базы данных реализованы (cache, storage и index), можно реализовать простой API и завершить этот образовательный проект.

namespace Boson {

    class BosonAPI {
    public:

        BosonAPI();
        ~BosonAPI();

        bool open(char* filename, bool readOnly = false);
        bool close();

        uint64_t size();
        bool isExists(uint64_t key);

        uint64_t insert(std::string value);
        bool insert(uint64_t key, std::string value);
        std::shared_ptr<std::string> get(uint64_t key);
        bool erase(uint64_t key);

        std::pair<uint64_t, std::shared_ptr<std::string>> first();
        std::pair<uint64_t, std::shared_ptr<std::string>> last();
        std::pair<uint64_t, std::shared_ptr<std::string>> next();
        std::pair<uint64_t, std::shared_ptr<std::string>> previous();

        double getCacheHits();

        void printTreeState();

    private:
        CachedFileIO* cachedFile;
        RecordFileIO* recordFile;
        BalancedIndex* balancedIndex;
        bool isReadOnly;
    };

}

Вот и всё! Цель проекта достигнута. Исходный код Boson вы можете посмотреть здесь. Спасибо что дочитали до конца!

Disclaimer: важно понимать, что это лишь учебный пример реализации СУБД движимый моим любопытством и поделиться впечатлениями от исследования. Для применения Boson в ваших реальных проектах необходимо реализовать защиту для многопоточности (locks) и на уровне хранилища/процессов. И нужно ли это делать - вопрос. Посмотрим.