dbms-task1 Задание 1. Б-дерево. Если вкратце: Размеры ключей и значений нефиксированные. (ограничение сверху: key.size + data.size + metadata <= chunk_size) В предельном случае превратится в бинарное дерево. Вместо критерия t-1 взят критерий заполненности ~50%. Возможно отклонение в меньшую сторону. Например: есть блок и 3 ключа, занимающие 40% 40% 40% = 120%. Этот блок надо делить (разделение потомка). Тогда средний ключ уйдет вверх, а в новом левом и правом потомке ушедшего ключа будет заполненность ~40%. Как-то так.

Задание 2. Размер кэша предпологается больше одного chunk_size. В случае когда размер кэша 0 или 1 chunk_size, возникает ошибка. Реализованный алгоритм LRU. Отключить кэширование можно закоментив в файле "headers/settings.h" строку "#define WITH_CACHE". Блоки связаны в линейный список. После этого надо перекомпилировать .so-файл через make. Есть другая вариация кэширования, где поиск по линейному списку осуществляется через дополнительное АВЛ-дерево. При маленьком размере кэша (~10x относительно блока), преимущество в скорости у поиска в линейном списке. При большом размере - у поиска через АВЛ-дерево. Это обусловлено тем, что когда количество блоков в кэше немного, быстрее проитерировать по листу, чем рекурсивно вызывать фунцию поиска в АВЛ-деревe. Когда количество блоков много - , соответственно, наоборот. Выключить режим кэширования с АВЛ-деревом можно закоментив строку "#define WITH_AVL" в файле "headers/settings.h". Однако на практике размер кэша намного больше размера блока, поэтому не имеет смысла его выключать. Обновление 14.11.2014. Добавлен вариант, где вместо avl дерева используется utihash