B-tree

Краткое описание семестрового проекта:

• B-дерево - это особый тип самобалансирующегося дерева поиска, в котором каждый узел может содержать более одного ключа и может иметь более двух дочерних элементов.
• Потребность в B-дереве возникла вместе с ростом потребности в меньшем времени доступа к физическим носителям информации, таким как жесткий диск. Вторичные запоминающие устройства работают медленнее и имеют большую емкость. Существовала потребность в таких типах структур данных, которые минимизировали бы доступ к диску.
• Другие структуры данных, такие как бинарное дерево поиска, avl-дерево, красно-черное дерево и т.д., могут хранить только один ключ в одном узле. Если нужно хранить большое количество ключей, то высота таких деревьев становится очень большой и время доступа увеличивается.
• B-дерево может хранить множество ключей в одном узле и иметь несколько дочерних узлов. Это значительно уменьшает высоту, позволяя ускорить доступ к диску.

Основные свойства B-tree:

1. Для каждого узла x ключи хранятся в порядке возрастания.
2. В каждом узле есть логическое значение x.leaf, которое истинно, если x это лист.
3. Если n это порядок дерева, то каждый внутренний узел может содержать не более n - 1 ключей вместе с указателем на каждого дочернего.
4. Каждый узел, кроме корня, может иметь не более n дочерних элементов и не менее n/2 дочерних.
5. Все листья имеют одинаковую глубину (то есть высоту - h дерева).
6. Корень имеет как минимум 2 дочерних элемента и содержит как минимум 1 ключ.
7. Если n ≥ 1, то для любого n-ключа B-дерева высоты h и минимальной степени t ≥ 2 ,h ≥ log<sub>t</sub> (n+1)/2.

Основные операции: поиск, вставка, удаление.

• Теоретическая сложность операций:
  • Операция поиска выполняется за время O(t log_t n).
  • Операция вставки выполняется за время O(t log_t n).
  • Операция удаления выполняется за время O(t log_t n).

Команда "Lost in space"

Фамилия Имя	Вклад (%)	Прозвище	Роль
Шкалин Вячеслав	80	Человек-full	Код, реализация, бенчмарки, readme
Гайсова Ольга	20	nullptr	Презентация, отчёт

Девиз команды

Как-нибудь справимся!

Структура проекта

Проект состоит из следующих частей:

• src/include - реализация структуры данных (исходный код и заголовочные файлы);
• benchmark - контрольные тесты производительности структуры данных (операции добавления, удаления, поиска);
• dataset - наборы данных для запуска контрольных тестов и их генерация;

Требования

Рекомендуемые требования:

1. С++ компилятор c поддержкой стандарта C++17 (например, GNU GCC 8.1.x и выше).
2. Система автоматизации сборки CMake (версия 3.12.x и выше).
3. Интерпретатор Python (версия 3.7.x и выше).
4. Рекомендуемый объем оперативной памяти - не менее 6 ГБ.
5. Свободное дисковое пространство объемом ~ 1,5 ГБ (набор данных для контрольных тестов).

Сборка и запуск

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

Пример (Windows)

Сборка проекта

Склонируйте проект к себе на устройство через Git for Windows (либо используйте возможности IDE):

git clone https://github.com/Algorithms-and-Data-Structures-2021/semester-work-b-tree-11-004.git

Генерация тестовых данных

Генерация тестового набора данных в формате comma-seperated values (CSV):

Инструкция по запуску скрипта:

Номер шага	Папки и файлы
1) Перейдите в папку генерации набора данных.	dataset
2) Откройте файл.	generate_csv_dataset.cpp
3) Запустите метод.	main()
4) В папке dataset есть папка data, в ней еще 3 папки (remove, find, insert).	data
5) После запуска скрипта, в этих папках появятся файлы для контрольного тестирования.	remove, find, insert

По названию директории /dataset/data/insert можно понять, что здесь хранятся наборы данных для контрольных тестов по добавлению элементов в структуру данных. Названия файлов 100.csv. 5000000.csv и т.д. хранят информацию о размере набора данных (т.е. количество элементов).

Контрольные тесты (benchmarks)

Для запуска контрольных тестов необходимо предварительно сгенерировать или скачать готовый набор тестовых данных (в случае скачивания, заменить исходную папку data на скачанную).

Примечание. Если вы не хотите "захламлять" проект большим объёмом данных, вы можете скачать наборы данных для контрольного тестирования, перейдя по ссылке на Google Drive.

Список контрольных тестов

Название	Описание	Метрики
find_benchmark	поиск элементов в структуре	время
insert_benchmark	добавление элементов в структуру данных	время
remove_benchmark	удаление всех элементов из структуры	время

Инструкция по запуску контрольных тестов:

Номер шага	Папки и файлы
1) Перейдите в папку с контрольными тестами.	benchmark
2) В папке есть 3 файла с контрольными тестами, по названию понятно, какой метод они тестируют. Откройте один из них.	remove_benchmark.cpp, find_benchmark.cpp, insert_benchmark.cpp
3) Запустите метод	main(). Из-за большого объема данных, метод выполняется довольно долго, пожалуйста, подождите какое-то время.
4) В папке result есть 3 файла с метриками. После прогона одного из контрольных тестов, файл, который привязан к определенному бенчмарку, отобразит результаты тестирования.	result, eraseResults.csv, findResults.csv, insertResults.csv

В файлы записываются как 3 числа через запятую:

1. Количество данных в наборе (от 100 до 5 млн)
2. Номер прогона на наборе данных (от 1 до 10)
3. Затраченное время (измеряется в наносекундах)

Источники

• Википедия (RU)
• Википедия (EN)
• Хабр
• Видео для базового объяснения
• Университет ИТМО Викиконспекты
• Англоязычная статья с описанием основных операций