Реализация B + Tree
Я любитель структур данных. Одна из моих любимых вещей - копаться в новой (для меня) структуре данных и пытаться ее реализовать. На этой неделе мы рассмотрим структуру данных, с которой я играл раньше, но которая мне всегда нравилась и которая, как я думаю (надеюсь?), Понравится и всем остальным: B + деревья!
Но сначала давайте подведем итоги шестой недели ...
Итоги недели # 6
В рамках 6-го еженедельного задания по программированию мы взялись за шум Перлина. Цель заключалась в том, чтобы создать изображение, изображающее шум Перлина, распределенный по холсту, чего я никогда раньше не делал. Я был рад попробовать!
Помимо меня, еще один человек принял вызов: Лассе Эберт, регулярно участвующий в еженедельных соревнованиях по программированию. Его решение снова было в Elixir, и он даже переработал свою библиотеку изображений PPM с недели №4. За успешную генерацию 2D-шума Перлина он получает одно очко! Отличная работа, Лассе. Проверьте это на GitHub.
Для своей собственной реализации я пересмотрел язык, который любил давно, но который мне редко удается использовать: C. (Я странно выгляжу, когда говорю, что люблю язык программирования C, но это абсолютно верно. Указатель арифметика, управление памятью, непонятный синтаксис ... писать код на языке C - такая ура.) Я пробовал различные подходы к созданию шума Перлина (некоторые даже были успешными!), но затем я начал анализировать эталонную реализацию Кена Перлина (на Java), чтобы увидеть, как она работает, и завершил реализацию порта C. Я заставил работать 3D-шум Перлина, а также раскраску ландшафта (и другие, такие как огонь и облака), прибив три твердые точки. Проверьте это на GitHub.
Я думаю, что шум Перлина - это то, что войдет в мой набор инструментов для «развлекательного программирования». С ним очень весело играть.
Еженедельное задание по программированию №7
Деревья B + являются основой файловых систем и баз данных. Буква B означает сбалансированный, и в этом отношении у них есть немало общего (по крайней мере, концептуально) с самобалансирующимися деревьями двоичного поиска, с которыми вы, возможно, играли в первом еженедельном задании по программированию. (Фактически, B-деревья - без плюса - являются обобщением самобалансирующихся двоичных деревьев, поддерживающих сколь угодно много дочерних узлов.)
Разница, однако, в том, что в то время как в двоичном дереве каждый узел может иметь до двух дочерних элементов, эти деревья B + могут иметь гораздо больше дочерних элементов на узел. Фактически, вы часто хотите, чтобы эти деревья имели большое «разветвление» (количество дочерних элементов на узел), потому что это увеличивает их эффективность при использовании с операциями ввода-вывода.
(По этой причине они популярны в файловых системах и базах данных, где дисковый ввод-вывод - это название игры, и вы хотите минимизировать частоту этого.)
Кроме того, в то время как двоичное дерево (и дерево B) хранит значение для каждого ключа в соответствующем узле, дерево B + хранит значения только в листьях. Внутренние узлы просто действуют как каталоги, указывая вам на последующие узлы в иерархии и, в конечном итоге, на листовой узел.
Так! Наша задача на этой неделе - создать дерево B +. И снова мы будем опираться на статью в Википедии как на каноническое описание структуры данных и связанных с ней алгоритмов.
Нормальный режим
Для нормального режима и одной точки необходимо реализовать следующее:
- Базовое дерево B + с настраиваемой арностью (количество детей на узел).
- Алгоритм вставки, позволяющий добавить в дерево новую пару ключ / значение.
- Алгоритм поиска, позволяющий найти значение для именованного ключа.
- Вы можете выбрать любой тип данных для ключа и значения. Даты = ›строки, чтобы можно было опрашивать людей по дате рождения? Целые числа = ›геолокации, чтобы можно было запрашивать города по населению? Тебе решать.
Сложный режим
Когда вы удовлетворяете нормальному режиму, вы можете стрелять в сложный режим. Здесь вы можете заработать по одному дополнительному баллу за реализацию дополнительных функций:
- Алгоритм удаления для удаления заданного ключа (и связанного с ним значения) из дерева.
- настраиваемая функция сортировки, позволяющая сортировать данные различными способами.
- Настраиваемые типы данных "ключ-значение". Разрешите строить B +-дерево с разными типами ключей и значений!
- При поиске дочерних узлов узла (для любой операции) используйте двоичный поиск для повышения эффективности. Это делает более возможным создание деревьев с разветвлением от сотни и более.
- Эффективная массовая загрузка, позволяющая инициализировать дерево из списка данных. (Обратите внимание, что, как описано в статье Википедии, простое добавление элементов по одному в пустое дерево имеет довольно низкую производительность, поэтому не делайте этого.)
- Свяжите листовые узлы вместе в связанный список, чтобы быстро перебирать значения в отсортированном порядке.
- Сделайте как настоящий индекс базы данных и храните каждый узел в отдельном «блоке» (настраиваемого размера) внутри файла на диске. Корневой узел будет первым блоком, а дочерние указатели будут указывать, где в файле находятся соответствующие им блоки. (Такое расположение может потребовать изменений в вашей базовой реализации, поскольку каждая операция внезапно должна учитывать структуру самого файла!) ДВА ТОЧКИ для этого.
Чтобы похвастаться (но не лишними баллами), снимайте заветную награду «Удиви меня»! Сделайте что-нибудь творческое со своей реализацией. Это не обязательно должно быть тяжелее (обязательно), чем нормальный режим, но он должен отличаться каким-то «вау» фактором. Посмотрите, что вы можете придумать!
Это испытание продлится до субботы, 17 сентября, в 12:00 по московскому времени (18:00 по всемирному координированному времени).
Срок выполнения этого задания истек, но вы все равно можете попробовать свои силы! В любое время отправьте ссылку на свое решение в комментариях. Если вы продолжаете, задача на следующей неделе - Реализовать простой синтаксический анализатор и интерпретатор. Увидимся там!
