radixdb — это небольшая статическая (read-only) key-value база данных, реализованная на языке C с применением структуры данных PATRICIA (компактного radix-trie). Она предназначена для хранения набора строковых ключей с соответствующими значениями и обеспечивает эффективные операции точного поиска и поиска по наибольшему префиксу. База создаётся заранее с помощью утилиты, после чего используется в режиме только для чтения.
Проект radixdb известен своей минималистичностью и специализацией на задачах, где важны компактность представления, быстрые запросы и необходимость сопоставления с длиной префикса. Поскольку структура не поддерживает динамических изменений (вставок или удалений после создания), она подходит для приложений, где множество ключей фиксировано и не модифицируется в процессе работы.
Исходный код и утилиты проекта включают генератор базы, утилиты для получения значения по ключу, для запроса по наибольшему совпадающему префиксу, а также вспомогательные инструменты для отладки и анализа. Подход основан на бинарном PATRICIA-дереве, где сравнение ведётся на уровне битовых позиций, что позволяет избежать необходимости балансировки и сохранить глубину дерева, пропорциональную длине ключей, а не числу элементов.
- radixdbmk — генерация файла базы из списка ключей и значений в текстовом формате
- radixdbget — точный поиск значения по заданному ключу
- radixdbmatch — поиск по наибольшему префиксу, то есть возвращение записи с ключом, который является самым длинным префиксом запроса
- radixdbdump — вывод содержимого базы в читаемом виде (ключи и значения)
- radixdbstats — статистика по структуре, например, количество узлов, длины ключей, распределения
- radixdb2dot — преобразование внутренней структуры в формат Dot (graphviz) для визуализации