Опубликовано: Sat, 09 Nov 2024 05:23:15 GMT
Канал: Все статьи подряд / Системное программирование / Хабр

Цель проекта Boson — это разработка встроенного движка базы данных документов JSON, написанный на C++. Основные возможности: стандартное хранилище JSON-документов в формате ключ/значениями с постоянным хранением на диске. Размер документов до 4Gb. Быстрый поиск документов по ID с использованием индекса B+ дерева. Поддержка курсоров для линейного обхода записей. База данных в одном файле, без временных файлов. Простое, чистое и легкое в использовании API. Самодостаточный и не требующий настройки.В предыдущих двух статьях мы прошли шаги от кэширования файлового ввода/вода (часть I) до построенного на его базе хранилища записей произвольной длины (часть II) с проверкой целостности, возможностью получения записей списком и повторным использованием свободного места. Теперь мы переходим к завершающей части и "сердцу" СУБД - индексу.Зачем нужен индекс: предположим, что в базе есть 1 млрд не отсортированных записей документов, тогда поиск конкретного документа по ID потребует O(n) операций, то есть до 1 млрд операций в худшем случае. Однако, если бы документы в базе были бы отсортированы по ID, то поиск в сортированной базе, тем же бинарным поиском занял бы O(log n) занял бы 30 операций. Что, теоретически, на базе в 1 млрд записей будет в 33.3 млн раз быстрее. Читать далее

https://habr.com/ru/articles/856876/