[kochevkv 0]

Всем доброго дня 🙂

 

Есть некая самописная "типа" БД в проекте для микроконтроллера. Суть такая, что каждый тип записей хранится в своем файле и для чтения-записи какой-либо записи данного типа надо знать просто номер. Т.е. в каждом файле хранятся записи только одного размера.

Сейчас появилась проблема, что работа с такой БД очень сильно замедляется при увеличении количества записей, т.к. поиск записи по значениям полей идет чисто последовательным способом, перебором то бишь. Сейчас пытаюсь написать код для индексации этих записей, т.е. так чтобы у объектов были прямые ссылки на номера всяких связанных объектов. Но чувствую что я изобретаю велосипед.

Я слышал что на МК в проект на Си можно портировать SqlLite. Но я совсем чайник в работе с базами данных. Получится ли как-то "прикрутить" SqlLite или что-то подобное к такому способу хранения информации? Чтобы, например, выполнить поиск всех объектов с нужным значением поля и чтобы сделать индексацию для дальнейшего быстрого поиска.

[EdgeAligned 53]

4 минуты назад, kochevkv сказал:

идет чисто последовательным способом, перебором то бишь.

Бинарное дерево? Сортировка и построение бинарного дерева.

[kochevkv 0]

19 minutes ago, EdgeAligned said:

Бинарное дерево? Сортировка и построение бинарного дерева.

Ну дерево то уже есть. Я только не понял как ускорить поиск. Т.е. есть объект с ID1 = 1. Есть несколько веток которые уже имеют ID1 и ID2. Ниже идет еще уровень с ID1, ID2 и ID3. Но чтобы найти следующий элемент на третьем уровне надо прочитать все записи в файле этого уровня пока не встретится нужная комбинация ID1 ID2 и ID3. Я сейчас пишу программу чтобы она объекту ID1 еще добавила номера записей для нижнеуровневых объектов. Т.е. пробежался по файлу один раз, а второй поиск уже по сохраненным индексам. И хотелось бы найти какой-то готовый движок, который это умел бы делать, автоматически обновлял индексы при удалении какой-либо записи или при изменении поля ID любой записи. 

Или вот еще реальная задача - выдать первое ID3 значение которого нет в объектах с заданными ID1 и ID2. Удалили мы объект третьего уровня и появился новый ID3 который освободился.

Изменено 3 августа, 2023 пользователем kochevkv

[EdgeAligned 53]

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

Например, такое дерево:

нужно найти число 10. Начинаем с вершины, сравнивая искомое 10 с верхним узлом: 10 < 14, значит, нужно идти в левую ветвь. Там узел 8. Сравниваем: 10 > 8, значит идем в правую ветвь.. Вновь сравниваем: 10 = 10. Число найдено за 3 итерации поиска. В противоположность этому, последовательный перебор от 1 до 10 займет 10 итераций.

Ищите готовые реализации бинарного дерева, с добавлением и удалением элементов. Если не хотите писать самостоятельно.

[EdgeAligned 53]

Создание бинарного дерева происходит аналогично поиску его элементов. За верхний узел берется значение, равное половине возможного диапазона чисел. В примере выше диапазон чисел от 1 до 27, следовательно верхний узел должен быть равен половине, 14 (в целых числах). Допустим, надо добавить число 19. Оно больше 14, значит, будет помещено в правую ветвь. Затем добавляем число 17. Оно так же больше 14, поэтому переходим к узлу 19, сравниваем с ним, 17 < 19, значит, в левую ветвь узла 19. Ну и так далее. 
Удалять элементы, являющиеся узлами для низлежащих уровней, нельзя - разрушатся связи. Можно только разорвать связь с прикрепленным содержимым (данные) к элементу

[xvr 12]

1 hour ago, kochevkv said:

Я слышал что на МК в проект на Си можно портировать SqlLite.

Его не надо портировать - он вполне кросс платформенный и должен подключитсья к проекту как есть (если повезёт)

1 hour ago, kochevkv said:

Получится ли как-то "прикрутить" SqlLite или что-то подобное к такому способу хранения информации?

SqLite хранит свои базы в файле в своём формате. Поменять способ хранения IMHO нельзя

 

[dio4 4]

Добрый день. Пока не поздно(пока объектов и задач для самописной БД не стало слишком много), переходите к СУБД. SqlLite очень подходит, - нужно всего то (почти) установить библиотеку и клиента для работы в CLI. У меня есть книжка с примерами кода, как что установить и сделать. Хотите? Если да - кидайте вашу почту в личку. Сюда дать не могу - она больше 2 мб.

Изменено 10 августа, 2023 пользователем dio4

[dio4 4]

Если все же нет, могу подсказать реализацию(кодом и книгой) бинарного дерева на С.

[dio4 4]

Нашел для вас на русском (книги у меня на англ).  😀

[EdgeAligned 53]

Кстати, если в таблице БД нет идентификатора (или их несколько), то упорядочить БД можно по хэш-таблицам.