Как устроен алгоритм B-tree
Что проверяют
Понимаете ли вы, зачем дереву много ключей в узле и почему именно эта структура стоит под индексами баз и файловых систем. Следом часто спрашивают, чем B-дерево отличается от B+-дерева и от двоичного дерева поиска.
Как отвечать
Начните с мотивации: диск и SSD читаются страницами, и дорого не сравнение ключей, а каждый поход за страницей. B-дерево делает узел размером со страницу и кладёт в него десятки и сотни ключей, поэтому дерево получается широким и низким.
- устройство: ключи в узле отсортированы, между ними ссылки на детей. У дерева порядка m каждый узел, кроме корня, заполнен хотя бы наполовину, все листья на одной глубине;
- поиск: внутри узла бинарный поиск, дальше спуск в нужного ребёнка. Высота порядка логарифма N по основанию m, для миллионов записей это три-четыре уровня;
- вставка: всегда в лист. Переполненный узел делится пополам, средний ключ уходит в родителя. Если делится корень, дерево растёт на уровень вверх и остаётся сбалансированным;
- удаление: ключ из внутреннего узла заменяют предшественником или преемником из листа. Если узел стал слишком пустым, занимают ключ у соседа или сливают узлы;
- B+-дерево: данные только в листьях, листья связаны списком. Так устроены индексы PostgreSQL и InnoDB, и диапазонный запрос сводится к проходу по листьям.
Мостик к Python: SQLite из модуля sqlite3 хранит и таблицы, и индексы в B-деревьях. Своего B-дерева в стандартной библиотеке нет, для отсортированной коллекции в памяти берут bisect или пакет sortedcontainers.
Где спотыкаются
Расшифровывают B как binary. Это разные структуры: у двоичного дерева два потомка и большая высота, на диске оно проигрывает.
Оценивают сложность как O(log n) и на этом останавливаются. Главное преимущество в основании логарифма, то есть в числе обращений к страницам.
Не могут объяснить, почему дерево не перекашивается. Ответ в том, что оно растёт от корня через разделение узлов, а не вниз от листьев.