Boson — разработка СУБД «с нуля» (итог)
Напомню, о том что цель проекта 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+ Tree
B+ дерево состоит из внутренних узлов и листовых узлов. Внутренние узлы хранят только ключи для направления поиска, в то время как сами данные содержатся в листовых узлах:
Внутренние узлы (Inner Node): Содержат ключи и указатели на дочерние узлы, но не хранят реальные данные. Каждый внутренний узел может содержать от ⌈M/2⌉ до M-1 ключей и M дочерних узлов. Каждый ключ в узле разделяет дочерние узлы: левый дочерний узел содержит ключи, меньшие ключа родительского узла, а правый дочерний узел содержит ключи, большие или равные ключу родительского узла.
Листовые узлы (Leaf Node): Хранят пары ключей и указателей на данные. Связаны между собой в двусвязный список для эффективных диапазонных запросов. Каждый листовой узел может также содержать от ⌈M/2⌉ до M-1 ключей и M-1 значений.
Чтобы при произвольных вставках, удалениях и изменениях записей поддерживалась сбалансированность и отсортированность B+ дерева, выполняются следующие операции:
Операция поиска: Для поиска определенного ключа в B+ дереве начинают с корневого узла. Сравнивают целевой ключ с ключами в текущем узле, чтобы определить соответствующий дочерний узел. Если целевой ключ меньше, переходят к левому дочернему узлу; если больше или равен, переходят к правому дочернему узлу. Этот процесс повторяется, пока не будет достигнут нужный листовой узел, где и завершается поиск. Поскольку B+ дерево сбалансировано, сложность поиска составляет O (log n).
Операция вставки: Вставка ключа начинается с поиска подходящего листового узла с использованием процедуры поиска. Затем ключ вставляется в листовой узел в правильном отсортированном положении. Если узел превышает свою максимальную вместимость (M-1 ключей), происходит разделение. Узел делится на два, и половина ключей переходит в новый дочерний узел. Средний ключ поднимается в родительский узел. Если родительский узел также переполняется, это может вызвать дальнейшие разделения, которые могут распространиться до корня, потенциально увеличивая высоту дерева.
Операция удаления: Удаление ключа начинается с поиска целевого ключа в соответствующем листовом узле. Ключ удаляется, но если это приводит к тому, что узел содержит меньше ключей, чем минимум (⌈M/2⌉), требуется корректировка. Дерево может заимствовать ключ у соседнего узла, если у него больше минимального количества ключей. Если заимствование невозможно, узел сливается с соседним, и ключ из родительского узла удаляется или корректируется соответственно. Этот процесс слияния может распространяться вверх по дереву, если необходимо, чтобы сохранить баланс дерева.
Диапазонные запросы: B+ деревья особенно хорошо подходят для диапазонных запросов благодаря связной структуре листовых узлов. Чтобы выполнить диапазонный запрос, начинают с поиска первого ключа в нужном диапазоне, используя процедуру поиска. После нахождения начального ключа переходят по двусвязному списку листовых узлов, пока не достигнут конца диапазона. Эта связная структура делает сканирование последовательности значений эффективным и простым.
Операция обновления: Обновление значения ключа включает поиск ключа в соответствующем листовом узле с использованием поиска. После нахождения ключа связанное значение изменяется. Если значение требует перемещения из-за ограничений по вместимости записей, может быть выделена новая запись в хранилище без изменения ключа.
Операции вставки и удаления могут создавать ситуацию, когда возникает переполнение узла или, наоборот, недостаток элементов. В таких случаях выполняются операции поддерживающие сбалансированность B+ дерева:
Разделение (Split) — выполняется когда узел в B+ дереве превышает свою максимальную вместимость (M-1 ключей). Процесс деления заключается в следующем:
Узел делится на два, при этом половина ключей остается в исходном узле, а другая половина переносится в новый узел.
Продвижение ключа вверх (Push Key Up) — средний ключ из исходного узла перемещается в родительский узел. Это обеспечивает обновление родительского узла, чтобы отразить изменения структуры дерева.
Если родительский узел также переполняется, процесс разделения и продвижения ключа вверх может распространяться вверх по дереву, вплоть до корня (root). Если корень разделяется, создается новый корень, увеличивая высоту дерева. То есть дерево по количеству уровней растёт от корня, а не от листьев.
Пример: Если в узле M=5 и он содержит 5 ключей (1, 2, 3, 4, 5), при переполнении узел делится на два: (1, 2) и (4, 5), а ключ 3 продвигается вверх.
Слияние (Merge) — выполняется когда в результате удаления ключа количество ключей в узле становится меньше минимально допустимого значения (⌈M/2⌉). Процесс слияния включает:
Объединение узла с его соседним узлом (левым или правым), чтобы создать один узел.
Ключ из родительского узла, который разделял эти два узла, перемещается вниз и становится частью объединенного узла.
Если после слияния родительский узел остается с недостаточным количеством ключей, операция слияния может распространиться вверх по дереву.
Пример: Если два соседних листовых узла содержат ключи (1, 2) и (3, 4), они могут объединиться в один узел (1, 2, 3, 4), и разделяющий ключ из родительского узла удаляется.
Заимствование у соседнего узла (Borrow from Sibling) — это операция, выполняемая, когда узел содержит меньше минимально допустимого числа ключей (⌈M/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 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 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 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 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 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 search(uint64_t key);
bool erase(uint64_t key);
std::pair> first();
std::pair> last();
std::pair> next();
std::pair> previous();
void printTree();
protected:
uint64_t getNextIndexCounter();
RecordFileIO& getRecordsFile();
std::shared_ptr findLeafNode(uint64_t key);
void updateRoot(uint64_t newRootPosition);
void persistIndexHeader();
void printTreeLevel(std::shared_ptr node, int level);
private:
RecordFileIO& recordsFile;
IndexHeader indexHeader;
std::shared_ptr root;
std::shared_ptr cursorNode;
uint32_t cursorIndex;
bool isTreeChanged;
};
} Напишем реализацию NodeData, Node, InnerNode, LeafNode, BalancedIndex и проверим как строится B+ дерево (на логах в консоли можно разглядеть структуру дерева, и ссылки на позиции в файле базы данных…
С февраля 2023 года (публикации второй части статьи) прошло полтора года, руки не доходили, но в октябре 2024 смог выделять по 2 часа в день и за месяц получилось реализовать Persisted B+ Tree.
Каждый алгоритм и его техническая реализации в отдельности не представляли большой сложности (бинарный поиск, двусвязные списки, деревья, рекурсии многие знают со школы), пока всё это делалось в оперативной памяти и по отдельности. Однако, чтобы отладить и заставить это работать на диске (вместо new/delete нужно было использовать аналог хранения на диске — RecordFileIO), всё вместе и слаженно — это был вызов, который занял почти месяц на осознание и разработку. Тут видимо уже мои интеллектуальные ограничения. Очень сильно выручили умные указатели (smart pointers) чтобы проуправлять постоянной загрузкой и выгрузкой узлов из памяти и сохранением их на диске не создав утечку памяти. Спасибо разработчикам языка C++.
Итак посмотрим, как работает реализация. Сработало:
Это распечатка реальной структуры B+ дерева базы данных с 55 записями (чтобы влезло в скриншот)
Завершив реализацию посмотрим как это примерно работает. Для статьи и удобства разглядывания скриншота взял малое количество записей, в реальных тестах проверял на больших объемах. Вставим 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 get(uint64_t key);
bool erase(uint64_t key);
std::pair> first();
std::pair> last();
std::pair> next();
std::pair> previous();
double getCacheHits();
void printTreeState();
private:
CachedFileIO* cachedFile;
RecordFileIO* recordFile;
BalancedIndex* balancedIndex;
bool isReadOnly;
};
} Вот и всё! Цель проекта достигнута. Исходный код Boson вы можете посмотреть здесь. Спасибо что дочитали до конца!
Disclaimer: важно понимать, что это лишь учебный пример реализации СУБД движимый моим любопытством и поделиться впечатлениями от исследования. Для применения Boson в ваших реальных проектах необходимо реализовать защиту для многопоточности (locks) и на уровне хранилища/процессов. И нужно ли это делать — вопрос. Посмотрим.
